#缘起

最近头脑发热,突然想研究下怎么判断一个坐标点是否在一个多边形内,这个问题解决之后就可以根据一个坐标点计算出这个点所在的行政区划。

#算法
从网上找了一下,发现了一个很巧妙的算法,算法如下:

* 把整个平面分为两个部分(x>0&&y==0||y>0部分和x<0&&y==0||y<0部分)
* 顺序扫描多边形每一个顶点,当某个顶点和前一个顶点处于不同部分时,判断一下从前一个点到该点的方向相对于原点是顺时针还是逆时针(用叉积判断),如果是顺时针r++,否则r--(r初始为0)
* 如果结果r==2||r==-2,则原点在该多边形内部,否则不是。

#python实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def is_point_in(x, y, points):
count = 0
x1, y1 = points[0]
x1_part = (y1 > y) or ((x1 - x > 0) and (y1 == y)) # x1在哪一部分中
x2, y2 = '', '' # points[1]
points.append((x1, y1))
for point in points[1:]:
x2, y2 = point
x2_part = (y2 > y) or ((x2 > x) and (y2 == y)) # x2在哪一部分中
if x2_part == x1_part:
x1, y1 = x2, y2
continue
mul = (x1 - x)*(y2 - y) - (x2 - x)*(y1 - y)
if mul > 0: # 叉积大于0 逆时针
count += 1
elif mul < 0:
count -= 1
x1, y1 = x2, y2
x1_part = x2_part
if count == 2 or count == -2:
return True
else:
return False


if __name__ == '__main__':
points = [[117.1510864068032,40.0705150448258],[117.2866776871509,40.10934259697606], ... ]
y = 39.99
x = 116.468006
for i in xrange(10000):
is_point_in(x + i * 0.01, y + i * 0.01, points)

##执行时间:

``` bash

time python point.py

real 0m8.746s
user 0m8.680s
sys 0m0.034s

执行了10,000次,耗时8.746秒,太慢了有木有, 改成go试试

#golang实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

package main

import (
//"fmt"
)


func is_point_in(x float64, y float64, points [][]float64) bool {
count := 0
x1, y1 := points[0][0], points[0][1]
x1_part := (y1 > y) || ((x1 - x > 0) && (y1 == y))
var a = []float64{x1, y1}
p := append(points, a)
for i := range p {
if (i == 0) {
continue
}
point := p[i]
x2, y2 := point[0], point[1]
x2_part := (y2 > y) || ((x2 > x) && (y2 == y))
if (x2_part == x1_part){
x1, y1 = x2, y2
continue
}
mul := (x1 - x)*(y2 - y) - (x2 - x)*(y1 - y)
if mul > 0 {
count += 1
} else {
if( mul < 0) {
count -= 1
}
}
x1, y1 = x2, y2
x1_part = x2_part
}

if (count == 2 || count == -2){
return true
} else {
return false
}
}

func main() {
points := [][]float64{{117.1510864068032,40.0705150448258},{117.2866776871509,40.10934259697606}, ... ,}
y := 39.99
x := 116.468006
for i:=1; i < 10000; i++ {
_ = is_point_in(x + float64(i)*0.01, y + float64(i) * 0.01, points)
}
}

##执行时间:

1
2
3
4
5
6
7

go build point.go
time ./point

real 0m0.038s
user 0m0.035s
sys 0m0.005s

执行了10,000次,耗时0.038秒

#总结

go版本比python版本快200多倍,代码行数python 35行, go 51行(有些括号独占一行),是时候换go了…..

#参考资料: