algorithm - 定义地理围栏并查看点是否在其内部/外部的算法

Question

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

谢谢你。

Answer 1

Here is the c code algorithm that is simple to understand:

http://alienryderflex.com/polygon/

Answer 2

圆很容易（至少如果你假设一个局部平坦的表面） - 只是到一个点的绝对距离。

如果您需要速度，通常的方法是级联，您首先检查一个圆，或者围绕该点检查一个正方形，然后是凸多边形，然后是更详细的多边形（如果需要）。

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

ps 请参阅如何测试一个点是否在 2D 整数坐标中的凸多边形内？

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")

谢谢你！

Answer 4

绕组数法

但最重要的是，出于几何正确性和效率的原因，在确定多边形中是否包含点时，应始终首选缠绕数算法。

Answer 5

看看四叉树、空间索引、四叉树和 r-tree。