判断点是否在区域内的算法

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.角度具有方向.如果角度向后,则角度为负值.这就像计算绕组数一样.

提供的输入数据[[-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