我对 python 中的多边形点（约旦曲线定理）的改编是否正确？
Is my adaptation of point-in-polygon (jordan curve theorem) in python correct?
问题
我最近发现需要确定我的点是否在多边形内。所以我了解了 C++ 中的 this 方法并将其改编为 python。但是，我认为我正在研究的 C++ 代码不太正确？我相信我已经修复了它，但我不太确定所以我希望比我聪明的人可以帮助我对此有所了解？
定理超级简单，思路是这样的，给定第n个闭合多边形，你画一条任意线，如果你的点在里面，你的线将与边相交奇数次。否则，你将是均匀的并且它在多边形之外。非常酷。
我有以下测试用例：
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)
如果我按如下方式定义上面的内容，则两者都为假：
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_y 而不是 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 方法的作用吗？另外，如果我为 polygon_x 重新定义 temp_x 和为 polygon_y 重新定义 temp_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)。我还针对 "corrected" 算法 (9,9) 测试了点，它仍然在里面。简而言之，我试图找到一个反例，说明为什么我的修复不起作用，但我做不到。如果这有效，我需要了解该方法在做什么，并希望有人可以帮助向我解释一下？
无论如何，如果我是对的或错的，如果有人能帮助更好地阐明这个问题，我将不胜感激。我什至愿意以更有效的方式解决 n 多边形问题，但我想确保我正确理解代码。作为一名编码员，我对一种不太合理的方法感到不舒服。
非常感谢您聆听我以上的想法。非常欢迎任何建议。
您误解了链接的 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) ).代码将决定它是在多边形内部还是外部可能归结为浮点舍入和运算符在 < 或 <= 之间的选择。在这种情况下，可以考虑任一答案 "correct"。
当您稍后在问题中重新排序坐标时（顺便将 11 更改为 10），您将领结变成了正方形。现在 (6, 6) 测试完全在形状内部，因此如果您不将 y 坐标分配给第二个 temp 变量，代码将正常工作。
问题
我最近发现需要确定我的点是否在多边形内。所以我了解了 C++ 中的 this 方法并将其改编为 python。但是，我认为我正在研究的 C++ 代码不太正确？我相信我已经修复了它，但我不太确定所以我希望比我聪明的人可以帮助我对此有所了解？
定理超级简单，思路是这样的，给定第n个闭合多边形，你画一条任意线，如果你的点在里面，你的线将与边相交奇数次。否则，你将是均匀的并且它在多边形之外。非常酷。
我有以下测试用例：
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)
如果我按如下方式定义上面的内容，则两者都为假：
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_y 而不是 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 方法的作用吗？另外，如果我为 polygon_x 重新定义 temp_x 和为 polygon_y 重新定义 temp_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)。我还针对 "corrected" 算法 (9,9) 测试了点，它仍然在里面。简而言之，我试图找到一个反例，说明为什么我的修复不起作用，但我做不到。如果这有效，我需要了解该方法在做什么，并希望有人可以帮助向我解释一下？
无论如何，如果我是对的或错的，如果有人能帮助更好地阐明这个问题，我将不胜感激。我什至愿意以更有效的方式解决 n 多边形问题，但我想确保我正确理解代码。作为一名编码员，我对一种不太合理的方法感到不舒服。
非常感谢您聆听我以上的想法。非常欢迎任何建议。
您误解了链接的 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) ).代码将决定它是在多边形内部还是外部可能归结为浮点舍入和运算符在 < 或 <= 之间的选择。在这种情况下，可以考虑任一答案 "correct"。
当您稍后在问题中重新排序坐标时（顺便将 11 更改为 10），您将领结变成了正方形。现在 (6, 6) 测试完全在形状内部，因此如果您不将 y 坐标分配给第二个 temp 变量，代码将正常工作。