我如何判断一个点是否在一条线下方？

Question

我该如何判断一个点是在一条线的下面还是上面呢？

我有以下的数据：

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

我需要用Python写一个小程序，来检测点是在这条线的哪一边。

谢谢！

Answer 1

假设你有两个点A和B，现在你想知道第三个点C在哪个半平面里。这里的“上”和“下”这两个说法其实很模糊，所以你需要一个参考点，比如原点（0,0）。要确保这个参考点和A、B不在同一条直线上。

现在你可以想象出一个三角形（A, B, C）。通过计算行列式，你可以得到这个三角形的有符号面积（详细信息可以查看这里，或者这里）。这里最重要的是记住这个面积的符号。

接下来的步骤是：对于一个给定的点D，计算三角形（A, B, D）的有符号面积。如果这个结果的符号和你之前计算的三角形的面积符号相同，那么C和D就在（A, B）的同一侧。如果符号不同，那么C和D就在这条线的两侧。如果三角形（A, B, D）的面积是0，那么A、B和D是共线的。注意：可以使用Python内置的cmp函数来比较三角形的面积。

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

你可以试试用叉乘——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')来表示向量会很不错。

幸运的是，我找到了计算二维向量的叉乘。