判断点是否在多边形内

问题描述

地图应用上，会经常判断用户是否在 xx 内(车站／商场／机场等)，即判断一个点是否位于多边形区域内。

解决算法 － 射线法

思想： 从待判断的点向某一个方向引射线，计算和多边形交点的个数，如果个数是偶数或者0，则点在多边形外，如果是奇数，则在多边形内。

特殊情况：

  1. 射线经过顶点
  2. 点在边上

思路流程

1.首先获得数据集在横坐标和纵坐标的最大/小值，判断测试点是否在该四边形内。快速排除，提高效率。

1
2
3
4
5
6
7
8
9
10
for i in range(1, pointLen):
	if points[i].lng > top.lng:
		top = points[i]
	elif points[i].lng < down.lng:
		down = points[i]
		
	if points[i].lat > right.lat:
		right = points[i]
	elif points[i].lat < left.lat:
		left = points[i]

2.接下来，取相邻的两个点与测试点，判断测试点是否为顶点

1
2
3
# 点与多边形顶点重合
if (p.lng == p1.lng and p.lat == p1.lat) or \
	(p.lng == p2.lng and p.lat == p2.lat):

3.判断测试点是否在两个相邻点的纵坐标范围之内，

1
2
if (p2.lat < p.lat and p1.lat >= p.lat) or \
					(p1.lat < p.lat and p2.lat >= p.lat)

4.判断测试点是否在相邻点的连线之间

5.判断测试点是否穿过线段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
if (p2.lat < p.lat and p1.lat >= p.lat) or \
		(p1.lat < p.lat and p2.lat >= p.lat):
		print("on both sides")
		# 线段上与射线y坐标相同的点的x 的坐标
		if p1.lat == p2.lat:
			x = (p1.lng + p2.lng)/2
		else:
			x = p2.lng - (p2.lat - p.lat)*(p2.lng - p1.lng)/(p2.lat - p1.lat) 
		# 点在多边形的边上
		if x == p.lng:
			print("on the edge")
			inpolygonList.append(p)
			break
		# 射线穿过多边形的边界
		if x > p.lng:
			print("throw")
			flag = not flag
		else:
			pass
	else:
		pass

完整代码

已上传至 github，欢迎下载。

https://github.com/pangrou/machine-learning/tree/master/python练习