我在Python中对多边形点（约旦曲线定理）的改编是否正确？

Question

问题

我最近发现需要确定我的点是否在多边形内部。所以我学习了C++中的这种方法并将其改编到Python中。但是，我认为我正在研究的 C++ 代码不太正确？我相信我已经解决了这个问题，但我不太确定，所以我希望比我聪明的人可以帮助我解决这个问题？

这个定理非常简单，其想法是这样的，给定一个闭合多边形，你画一条任意的线，如果你的点在里面，你的线将与边缘相交奇数次。否则，你将是均匀的并且它在多边形之外。非常酷。

我有以下测试用例：

    polygon_x = [5, 5, 11, 10]
    polygon_y = [5, 10, 5, 10]
    test1_x = 6
    test1_y = 6

    result1 = point_in_polygon(test1_x, test1_y, polygon_x, polygon_y)
    print(result1)

    test2_x = 13
    test2_y = 5
    result2 = point_in_polygon(test2_x, test2_y, polygon_x, polygon_y)
    print(result2)

如果我将其定义如下，则上面的内容都会为 false：

            if polygon_x[i] < polygon_x[(i+1) % length]:
                temp_x = polygon_x[i]
                temp_y = polygon_x[(i+1) % length]
            else:
                temp_x = polygon_x[(i+1) % length]
                temp_y = polygon_x[i]

这是错误的！我应该先为true然后result1再false为result2。很明显，有些东西很时髦。

除了上面的内容之外，我在 C++ 中阅读的代码是有意义的。此外，它未能通过我的测试用例，这让我认为temp_y 应该用polygon_yand not来定义polygon_x。果然，当我这样做时，我的测试用例(6,6)通过了。当我的点在线上时它仍然会失败，但只要我在多边形内，它就会通过。预期行为。

采用Python的多边形代码

    def point_in_polygon(self, target_x, target_y, polygon_x, polygon_y):
        print(polygon_x)
        print(polygon_y)
        #Variable to track how many times ray crosses a line segment
        crossings = 0
        temp_x = 0
        temp_y = 0
        length = len(polygon_x)

        for i in range(0,length):

            if polygon_x[i] < polygon_x[(i+1) % length]:
                temp_x = polygon_x[i]
                temp_y = polygon_y[(i+1) % length]
            else:
                temp_x = polygon_x[(i+1) % length]
                temp_y = polygon_y[i]

            print(str(temp_x) + ", " + str(temp_y))

            #check
            if target_x > temp_x and target_x <= temp_y and (target_y < polygon_y[i] or target_y <= polygon_y[(i+1)%length]):
                eps = 0.000001

                dx = polygon_x[(i+1) % length] - polygon_x[i]
                dy = polygon_y[(i+1) % length] - polygon_y[i]

                k = 0
                if abs(dx) < eps:
                    k = 999999999999999999999999999
                else:
                    k = dy/dx

                m = polygon_y[i] - k * polygon_x[i]
                y2 = k*target_x + m

                if target_y <= y2:
                    crossings += 1
        print(crossings)
        if crossings % 2 == 1:
            return True
        else:
            return False

概括

有人可以向我解释一下temp_x和temp_y方法在做什么吗？另外，我重新定义temp_xforpolygon_x和temp_yfor的修复polygon_y方法是否正确？我对此表示怀疑。这就是原因。

发生了什么temp_x，temp_y对我来说不太有意义。因为i = 0，显然polygon_x[0] < polygon_x[1]是false，所以我们得到temp_x[1] = 5和temp_y[0] = 5。那是(5,5)。这恰好是我的一对。然而，假设我向算法提供的点是无序的（按轴，成对完整性始终是必须的），如下所示：

x = [5, 10, 10, 5]
y = [10,10, 5, 5]

在这种情况下，当 时i = 0，我们得到temp_x[1] = 10和temp_y[0] = 10。好吧，巧合(10,10)。我还针对“更正的”算法测试了点(9,9)，它仍然在里面。简而言之，我试图找到一个反例，解释为什么我的修复不起作用，但我不能。如果这有效，我需要了解该方法正在做什么，并希望有人可以帮助向我解释它？

不管怎样，如果我是对还是错，如果有人能帮助更好地阐明这个问题，我将不胜感激。我什至愿意以更有效的方式解决 n 多边形问题，但我想确保我正确理解代码。作为一名程序员，我对一种不太有意义的方法感到不舒服。

非常感谢您聆听我上面的想法。任何建议都非常受欢迎。

Answer 1

您误解了链接的 C++ 代码中的x1和x2值的用途，并且这种误解导致您在 Python 中选择了不合适的变量名称。这两个变量都包含x值，因此temp_y是一个非常具有误导性的名称。更好的名称可能是min_x和，因为它们是构成多边形边的顶点值max_x的最小值和最大值。x更清晰的代码版本可以写成：

for i in range(length):
    min_x = min(polygon_x[i], polygon_x[(i+1)%length])
    max_x = max(polygon_x[i], polygon_x[(i+1)%length])

    if x_min < target_x <= x_max:
        # ...

这可能比 C++ 风格的代码效率稍低，因为同时调用min和max都会对值进行两次比较。

您对点顺序的评论表明存在进一步的误解，这可能解释了您在设置temp_y为 的值时看到的意外结果polygon_x。多边形列表中坐标的顺序很重要，因为边从一个坐标对到列表周围的下一个坐标对（最后一对坐标连接到第一对坐标以闭合多边形）。如果对它们重新排序，多边形的边缘将会改变。

您在代码中给出的示例坐标（polygon_x = [5, 5, 11, 10]和polygon_y = [5, 10, 5, 10]）不描述正常类型的多边形。相反，你会得到一个（稍微不平衡的）领结形状，两个对角边缘像X中间一样相互交叉。但这对于该算法来说实际上并不是问题。

但是，您要测试的第一个点恰好位于其中一个对角边（环绕列表的边，从最后一个顶点(10, 10)到第一个顶点(5, 5)）。代码是否决定它是在多边形内部还是外部可能取决于浮点舍入以及<or之间的运算符选择<=。在这种情况下，任何一个答案都可以被认为是“正确的”。

当您稍后在问题中重新排序坐标时（顺便将 an 更改11为 a 10），您将领结变成了正方形。现在(6, 6)测试完全在形状内部，因此如果您不y为第二个temp变量分配坐标，代码将正常工作。