算法定义地理围栏并判断一个点是否在/外部。

Question

我正在寻找一种算法，通过它我可以创建一个地理围栏，并检查设备是否进入/离开围栏。我已经研究了点在多边形算法（射线投射和绕数），但是有没有算法也适用于圆形和任意不规则形状呢？重要的限制是时间效率。

谢谢。

- Nilgiri

Answer 1

这里是一个易于理解的C代码算法：

http://alienryderflex.com/polygon/

- Josh C

Answer 2

圆形很容易（至少在假定为局部平面的情况下）-只需从一个点开始计算绝对距离。

如果你需要速度，通常的方法是级联检查，其中你首先检查一个圆形或点周围的正方形，然后检查凸多边形，最后必要时再检查更详细的多边形。

如果这个不规则形状不是多边形，你如何定义它？

参见如何测试一个点是否在二维整数坐标的凸多边形内？

- Martin Beckett

---

注意：通常情况下，它不是一个正方形，而是一个矩形，经常被称为“边界框”。 - David Conrad

@DavidConrad - 是的，我过于简化了。或者说它确实是一个正方形，你只需要改变你的坐标；-) - Martin Beckett

当然。 :) 我只是想给OP提供“边界框”这个术语和更多信息，这可能对搜索有用，并且觉得这不值得单独回答，所以我把它放在这里，作为对你的回答的评论。干杯！ - David Conrad

Answer 3

我找到了这个 Python 的解决方案。据我所知，这个方案是可行的。

from shapely.geometry import Point, Polygon
import matplotlib.path as mpltPath
from functools import reduce
import operator
import math
coords = [[ 12.934158,77.609316], [ 12.934796,77.609852],[ 12.934183,77.610646], [ 12.933551,77.610100], [12.934158,77.609316]]

#sorting the geofence coords in clockwise direction
center = tuple(map(operator.truediv, reduce(lambda x, y: map(operator.add, x, y), coords), [len(coords)] * 2))
coords = sorted(coords, key=lambda coord: (-135 - math.degrees(math.atan2(*tuple(map(operator.sub, coord, center))[::-1]))) % 360)

#Testing if a point inside or outside
poly = Polygon(coords)
point = Point(12.933556,77.609854)
print(coords)
if(point.within(poly)):
    print("Inside")
else:
    print("Outside")

谢谢！

- R Nanthak

Answer 4

绕数法

但总的来说，为了保证几何正确性和效率，判断一个点是否在多边形内应该始终优先选择使用绕数算法。

- LucasM

Answer 5

看看四叉树，空间索引，四叉键和R树。

- Micromega