如何检查点是否在线下？

Question

如何检查点是否在线下？

我有以下数据：

Line [ {x1,y1}, {x2,y2} ]
Points {xA,yA}, {xB,yB} ...

我需要在python中编写一个小算法来检测线的一侧和另一侧的点。

谢谢

Answer 1

您可以尝试使用交叉产品 - http://en.wikipedia.org/wiki/Cross_product。

v1 = {x2-x1, y2-y1}   # Vector 1
v2 = {x2-xA, y2-yA}   # Vector 1
xp = v1.x*v2.y - v1.y*v2.x  # Cross product
if xp > 0:
    print 'on one side'
elif xp < 0:
    print 'on the other'
else:
    print 'on the same line!'

您需要校准每个方面的内容。如果您希望它在“下方”或“上方”，则需要确保线上的点水平排序。

我没有测试过这个。

编辑我最初放入点积公式。 ：○

幸运的是我找到了Calculating a 2D Vector's Cross Product。

Answer 2

您可以尝试使用交叉产品，但诀窍是如何选择形成矢量的点，在这里我选择距离点最近的点，假设我得到了pointA（你可以公平地循环点来计算从循环点到Line的距离） ）：

v1 = {x2-x1, y2-y1}   # Vector 1
v2 = {xA-x1, yA-y1}   # Vector 2
cross_product = v1.x*v2.y - v1.y*v2.x
if cross_product > 0:
    print 'pointA is on the counter-clockwise side of line'
elif xp < 0:
    print 'pointA is on the clockwise side of line'
else:
    print 'pointA is exactly on the line'

Answer 3

假设你已经给了2分A，B并且你想知道哪个halfplane第三个C位。术语“下方”和“上方”作为标准非常模糊，因此您需要一个参考点，例如原点。请确保此参考点与A和B不共线。

你现在拥有的是一个三角形（A，B，C）。使用行列式，您可以计算有符号区域（see here或here）。这里唯一有趣的是记住这个标志。

下一步：对于给定点D，计算三角形（A，B，D）的有符号区域。如果结果与参考三角形的区域具有相同的符号 - > C和D位于（A，B）的同一侧。如果符号不同 - > C和D位于线的两侧。如果（A，B，D）的面积为0，则A，B和D是共线的。注意：使用Python内置cmp来比较三角形区域。