算法来判断一个点是否在一个区域内

Question

我最近正在研究一个有算法的项目来判断一个点是否在一个区域内。

区域看起来是这样的：

{"state": "Washington", "border": [[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]} 

这很容易，如果该地区是一个矩形。但是，该地区是不规则的。我的想法之一是检查一个点是否在该区域每条线的“内部”一侧。但是，表现并不好。任何想法？

Answer 1

首先，非常有趣的问题！虽然这可能是一个重复的问题，但我仍然会发布另一个与该帖子不同的可行答案来鼓励这个新人。

这个想法是使用角度的总和来决定目标是内部还是外部。如果目标位于一个区域内，则目标和每两个边界点的角度形式总和将为360.如果目标位于外侧，则总和将不为360.角度具有方向。如果角度向后，角度是负的。这就像计算winding number一样。

提供的输入数据[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]是顺时针的（您可以查看谷歌地图）。因此，我的代码假设正角是顺时针的。

请参阅本作的想法：

以下是实现它的Python代码。

def isInside(self, border, target): 
    degree = 0 
    for i in range(len(border) - 1): 
     a = border[i] 
     b = border[i + 1] 

     # calculate distance of vector 
     A = getDistance(a[0], a[1], b[0], b[1]); 
     B = getDistance(target[0], target[1], a[0], a[1]) 
     C = getDistance(target[0], target[1], b[0], b[1]) 

     # calculate direction of vector 
     ta_x = a[0] - target[0] 
     ta_y = a[1] - target[1] 
     tb_x = b[0] - target[0] 
     tb_y = b[1] - target[1] 

     cross = tb_y * ta_x - tb_x * ta_y 
     clockwise = cross < 0 

     # calculate sum of angles 
     if(clockwise): 
      degree = degree + math.degrees(math.acos((B * B + C * C - A * A)/(2.0 * B * C))) 
     else: 
      degree = degree - math.degrees(math.acos((B * B + C * C - A * A)/(2.0 * B * C))) 

    if(abs(round(degree) - 360) <= 3): 
     return True 
    return False 

Answer 2

下面是一个伪代码：

var point = [x,y] // Point to evaluate 

int i, j, c = 0 
int size = border.count 
for (i = 0, j = size-1; i < size; j = i++) { 
    var ii = border[i] 
    var jj = border[j] 
    if (((ii.[1] > point.[1]) != (jj.[1] > point.[1])) && 
     (point.[0] < (jj.[0]-ii.[0]) * (point.[1]-ii.[1])/(jj.[1]-ii.[1]) + ii.[0])) { 
     c = !c 
    } 
} 
return c 

Answer 3

听起来像是不错的使用情况修改convex hull算法。

1. 从“区域”内的所有点开始（因为尚未创建船体）。然后，当你通过你选择的算法（例如格雷厄姆扫描是O(nlog(n))性能）时，如果点被选为凸包的一部分，它不再位于“区域”内部 - （即，包括凸包不是最终答案的一部分）。
2. 重复，直到你创建凸包。因此，不属于船体的剩余点因此位于该区域内，这是您正在寻找的答案。