如何检查一个点是否在线下方？

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 2
xp = v1[0]*v2[1] - v1[1]*v2[0]  # Cross product (magnitude)
if xp > 0:
    print('on one side')
elif xp < 0:
    print('on the other')
else:
    print('on the same line!')

您需要校准每一侧的内容。如果您希望它位于“下方”或“上方”，您需要确保线上的点水平排序。

我没有测试过这个。

编辑我最初输入了点积公式。 :o

编辑 2 天哪，我将坐标放入集合而不是元组中。如果您运行的是相当现代的 Python 版本，那么对向量使用 namedtuple('point', 'x y') 会很好。

幸运的是，我找到了计算 2D 矢量叉积。

Answer 2

你可以尝试使用叉积，但技巧是如何选择点来形成向量，这里我选择点中最近的点，假设我得到了点A（你可以公平地循环点来计算从循环点到线的距离）：

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 cross_product < 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）。使用行列式，您可以计算签名面积 (请参阅此处，或此处）。这里唯一有趣的是记住这个标志。

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