如何判断一个点在一条直线的左侧还是右侧

Question

我有一组点。我想把它们分成两个不同的集合。为此，我选择两个点（a 和 b），并在它们之间画出一个虚拟的直线。现在我想把线左侧的所有点放入一个集合中，将右侧的点放入另一个集合中。

如何判断任何给定的点 z 是属于左边集合还是右边集合？我尝试计算 a-z-b 之间的角度 - 小于180度的角度位于右手边，大于180度的角度位于左手边 - 但由于ArcCos的定义，计算出的角度总是小于180度。是否有公式可以计算大于180度的角度（或任何其他选择左或右侧的公式）？

- Aaginor

---

右侧或左侧如何定义？A）从P1看向P2或B）在平面上线的左侧或右侧。 - phkahler

澄清一下，针对你问题的第二部分，你可以使用atan2()来计算正确的角度，而不是使用acos()。然而，正如Eric Bainville所指出的那样，使用叉积是解决这个问题的最佳方案。 - dionyziz

下面许多解决方案都不起作用，因为如果交换点a和b（我们用来定义直线的点），它们会给出相反的答案。我提供了一个Clojure的解决方案，在比较第三个点之前将这两个点按字典顺序排序。 - Purplejacket

Answer 1

尝试使用叉积的以下代码。给定一条线段a--b和点c：

public bool isLeft(Point a, Point b, Point c) {
  return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x) > 0;
}

如果公式等于0，则点共线（c与a-b对齐）。

如果直线是水平的，则如果点在直线上方，则返回true。

- jethro

---

@lzprgmr: 不，这是一个叉积，等价于二维矩阵的行列式。考虑由行（a，b）和（c，d）定义的二维矩阵。其行列式为ad-bc。上面的形式将由两个点表示的线转换为一个向量（a，b），然后使用PointA和PointC定义另一个向量以获得（c，d）： (a，b) =（PointB.x-PointA.x，PointB.y-PointA.y） (c，d) =（PointC.x-PointA.x，PointC.y-PointA.y）因此，行列式就像帖子中所述的那样。 - AndyG

这个问题是否为叉积或点积的混淆，可能是因为它涉及到二维空间。事实上，这是二维空间中的叉积：http://mathworld.wolfram.com/CrossProduct.html。请注意，不要改变原意并尽量让翻译通俗易懂。 - brianmearns

就其价值而言，这可以稍微简化为return (b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x);，但编译器可能会自动优化它。 - Nicu Stiurca

这个解决方案取决于点A、B的顺序。在此答案中提供的解决方案math.stackexchange.com/questions/757591/…（暗示计算线AB的方程）与点A、B的顺序无关。 - rkachach

那么对于 a = (1; 0)，b = (-1; 0)，c = (0; 2) 呢？尽管点 c 在直线左侧（应该将其视为直线左侧，因为形成了左转），它会返回 false。证明：((b.X - a.X)(c.Y - a.Y) - (b.Y - a.Y)(c.X - a.X)) = ((-1 - 1) * (2 - 0) - (0 - 0) * (0 - 1)) = -2 * 2 = -4 < 0。 - metamaker

Answer 2

使用向量 (AB,AM) 的行列式符号，其中查询点为 M(X,Y)：

position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))

这一行上是0，一侧是+1，另一侧是-1。

- Eric Bainville

---

+1 很不错，但需要注意的是：当点非常接近于线时，四舍五入误差可能会成为一个问题。对于大多数情况来说不是问题，但有时会让人感到困扰。 - Stephen Canon

如果你发现在这个测试中舍入误差导致问题，你需要查阅Jon Shewchuk的“计算几何中的快速稳健谓词”。请注意保持原文意思，使翻译通俗易懂。 - Stephen Canon

为了澄清，这与线段（b-a）和从a点到给定点m的向量的叉积的Z分量相同。在你喜欢的向量类中：位置 = sign((b-a).cross(m-a)[2]) - larsmoa

交换 A 和 B 不会改变该行，但会改变“positions”的符号。 - Jayen

是的。A、B定义了方向，就像“站在A点，面向B点时，左侧的方向”。 - Eric Bainville

Answer 3

你需要查看行列式的符号：

| x2-x1  x3-x1 |
| y2-y1  y3-y1 |

对于位于一侧的点，它将是正数；对于另一侧的点则是负数（对于落在该直线上的点，则为零）。

- AVB

---

扩展这个答案，以防有人不知道叉积看起来是什么样子。 下一个视觉步骤是 ((x2-x1) * (y3-y1)) - ((y2-y1) * (x3-x1)) - Franky Rivera

Answer 4

向量(y1-y2, x2-x1)垂直于直线，且始终指向右边（如果您的平面方向与我的方向不同，则始终指向左边）。

然后，您可以计算该向量和(x3-x1, y3-y1)的点积，以确定该点是否与垂直向量在同一侧直线上（点积 > 0）。

- Victor Nicollet

---

谢谢您的回答。不清楚(3)、(2)和(1)是什么意思。您能否澄清一下？ - BenKoshy

Answer 5

使用 直线方程 ab，获取与待排序点在相同y坐标处的直线上的x坐标。

• 如果点的x > 直线的x，则该点在直线右侧。
• 如果点的x < 直线的x，则该点在直线左侧。
• 如果点的x == 直线的x，则该点在直线上。

- mbeckish

---

这是错误的，因为正如Aaginor在第一个答案中评论的那样，我们不想弄清楚点是否在有向线段AB的左侧或右侧，即如果你站在A点并朝B看，它在你的左边还是右边？ - dionyziz

@dionyziz - 嗯？我的答案没有为通过AB的线条指定“方向”。我的答案假设“左”是坐标系的-x方向。被接受的答案选择定义一个向量AB，并使用叉积定义左边。原始问题并未说明“左边”的含义。 - mbeckish

注意：如果你使用这种方法（而不是已被批准为答案的叉积法），请注意当线条接近水平时会出现一个陷阱。数学误差会增加，并且如果正好水平，就会达到无限大。解决方法是使用两点之间差异较大的轴。 （或者可能是较小的差异..这是我的初步想法。） - ToolmakerSteve

这正是我一直在寻找的。我不想知道A是否在B上方或下方。我只想知道它是否在线的左侧（负x方向）！ - Jayen

也正是我想找的。非常简单明了。谢谢！ - Jonah Kunz

Answer 6

我用Java实现了这个功能，并运行了一个单元测试（代码在下面）。以上提供的解决方案都不起作用。这段代码通过了单元测试。如果有人发现某个单元测试未通过，请告诉我。

代码：注意：nearlyEqual(double,double)会在两个数字非常接近时返回true。

/*
 * @return integer code for which side of the line ab c is on.  1 means
 * left turn, -1 means right turn.  Returns
 * 0 if all three are on a line
 */
public static int findSide(
        double ax, double ay, 
        double bx, double by,
        double cx, double cy) {
    if (nearlyEqual(bx-ax,0)) { // vertical line
        if (cx < bx) {
            return by > ay ? 1 : -1;
        }
        if (cx > bx) {
            return by > ay ? -1 : 1;
        } 
        return 0;
    }
    if (nearlyEqual(by-ay,0)) { // horizontal line
        if (cy < by) {
            return bx > ax ? -1 : 1;
        }
        if (cy > by) {
            return bx > ax ? 1 : -1;
        } 
        return 0;
    }
    double slope = (by - ay) / (bx - ax);
    double yIntercept = ay - ax * slope;
    double cSolution = (slope*cx) + yIntercept;
    if (slope != 0) {
        if (cy > cSolution) {
            return bx > ax ? 1 : -1;
        }
        if (cy < cSolution) {
            return bx > ax ? -1 : 1;
        }
        return 0;
    }
    return 0;
}

这是单元测试：

@Test public void testFindSide() {
    assertTrue("1", 1 == Utility.findSide(1, 0, 0, 0, -1, -1));
    assertTrue("1.1", 1 == Utility.findSide(25, 0, 0, 0, -1, -14));
    assertTrue("1.2", 1 == Utility.findSide(25, 20, 0, 20, -1, 6));
    assertTrue("1.3", 1 == Utility.findSide(24, 20, -1, 20, -2, 6));

    assertTrue("-1", -1 == Utility.findSide(1, 0, 0, 0, 1, 1));
    assertTrue("-1.1", -1 == Utility.findSide(12, 0, 0, 0, 2, 1));
    assertTrue("-1.2", -1 == Utility.findSide(-25, 0, 0, 0, -1, -14));
    assertTrue("-1.3", -1 == Utility.findSide(1, 0.5, 0, 0, 1, 1));

    assertTrue("2.1", -1 == Utility.findSide(0,5, 1,10, 10,20));
    assertTrue("2.2", 1 == Utility.findSide(0,9.1, 1,10, 10,20));
    assertTrue("2.3", -1 == Utility.findSide(0,5, 1,10, 20,10));
    assertTrue("2.4", -1 == Utility.findSide(0,9.1, 1,10, 20,10));

    assertTrue("vertical 1", 1 == Utility.findSide(1,1, 1,10, 0,0));
    assertTrue("vertical 2", -1 == Utility.findSide(1,10, 1,1, 0,0));
    assertTrue("vertical 3", -1 == Utility.findSide(1,1, 1,10, 5,0));
    assertTrue("vertical 3", 1 == Utility.findSide(1,10, 1,1, 5,0));

    assertTrue("horizontal 1", 1 == Utility.findSide(1,-1, 10,-1, 0,0));
    assertTrue("horizontal 2", -1 == Utility.findSide(10,-1, 1,-1, 0,0));
    assertTrue("horizontal 3", -1 == Utility.findSide(1,-1, 10,-1, 0,-9));
    assertTrue("horizontal 4", 1 == Utility.findSide(10,-1, 1,-1, 0,-9));

    assertTrue("positive slope 1", 1 == Utility.findSide(0,0, 10,10, 1,2));
    assertTrue("positive slope 2", -1 == Utility.findSide(10,10, 0,0, 1,2));
    assertTrue("positive slope 3", -1 == Utility.findSide(0,0, 10,10, 1,0));
    assertTrue("positive slope 4", 1 == Utility.findSide(10,10, 0,0, 1,0));

    assertTrue("negative slope 1", -1 == Utility.findSide(0,0, -10,10, 1,2));
    assertTrue("negative slope 2", -1 == Utility.findSide(0,0, -10,10, 1,2));
    assertTrue("negative slope 3", 1 == Utility.findSide(0,0, -10,10, -1,-2));
    assertTrue("negative slope 4", -1 == Utility.findSide(-10,10, 0,0, -1,-2));

    assertTrue("0", 0 == Utility.findSide(1, 0, 0, 0, -1, 0));
    assertTrue("1", 0 == Utility.findSide(0,0, 0, 0, 0, 0));
    assertTrue("2", 0 == Utility.findSide(0,0, 0,1, 0,2));
    assertTrue("3", 0 == Utility.findSide(0,0, 2,0, 1,0));
    assertTrue("4", 0 == Utility.findSide(1, -2, 0, 0, -1, 2));
}

- Al Globus

Answer 7

我希望能提供一种受物理启发的解决方案。

想象一条沿着直线施加的力，并测量力对点的扭矩。如果扭矩是正的（逆时针），则该点在直线的“左侧”，但如果扭矩为负，则该点在直线的“右侧”。

因此，如果力向量等于定义直线的两个点之间的跨度。

fx = x_2 - x_1
fy = y_2 - y_1

根据以下测试的符号，您可以测试基于点(px,py)的一侧。

var torque = fx*(py-y_1)-fy*(px-x_1)
if  torque>0  then
     "point on left side"
else if torque <0 then
     "point on right side"  
else
     "point on line"
end if

- John Alexiou

Answer 8

首先检查您是否有一个垂直线：

if (x2-x1) == 0
  if x3 < x2
     it's on the left
  if x3 > x2
     it's on the right
  else
     it's on the line

然后，计算斜率：m = (y2-y1)/(x2-x1)。

然后，使用点斜式创建一条直线的方程：y - y1 = m*(x-x1) + y1。为了解释方便，可以将其简化为斜截式（在算法中不是必需的）：y = mx+b。

现在将(x3, y3)代入x和y。以下是一些伪代码详细说明应该发生的事情：

if m > 0
  if y3 > m*x3 + b
    it's on the left
  else if y3 < m*x3 + b
    it's on the right
  else
    it's on the line
else if m < 0
  if y3 < m*x3 + b
    it's on the left
  if y3 > m*x3+b
    it's on the right
  else
    it's on the line
else
  horizontal line; up to you what you do

- maksim

---

失败：对于竖直线无效的斜率计算。无尽的if/else语句。不确定OP所说的左/右是否是这个意思 - 如果是的话，将其旋转90度后查看将使代码减半，因为“上方”将变成右侧或左侧。 - phkahler

这个答案有几个问题。竖线会导致除以零。更糟糕的是，它失败了，因为它没有考虑线的斜率是正还是负。 - user85109

@phkahler，修复了垂直线问题。虽然忘记一个测试用例不是失败，但感谢您的好话。“无尽的if/else”是为了解释数学理论；OP的问题中没有提到编程。@woodchips，修复了垂直线问题。斜率是变量m；当它为正或负时，我会进行检查。 - maksim

Answer 9

假设点为(Ax,Ay)、(Bx,By)和(Cx,Cy)，你需要计算： (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax) 如果点C在由点A和B形成的直线上，结果将为零，否则将根据侧面有不同的符号。这取决于(x,y)坐标系的方向，但你可以将A,B和C的测试值输入到该公式中，以确定负值是在左边还是右边。

- user2154342

Answer 10

这是一个使用叉积逻辑编写的Clojure版本。

(defn is-left? [line point]
  (let [[[x1 y1] [x2 y2]] (sort line)
        [x-pt y-pt] point]
    (> (* (- x2 x1) (- y-pt y1)) (* (- y2 y1) (- x-pt x1)))))

使用示例：

(is-left? [[-3 -1] [3 1]] [0 10])
true

这就是说，点 (0, 10) 在由 (-3, -1) 和 (3, 1) 确定的直线左侧。

注意：此实现解决了其他实现（到目前为止）未能解决的问题！在确定构成直线的点时，顺序很重要。也就是说，它是一个“有向直线”，在某种意义上是有方向的。因此，使用上述代码，此调用还会产生true的结果：

(is-left? [[3 1] [-3 -1]] [0 10])
true

这是由于以下代码片段：

(sort line)

最后，与其他基于叉积的解决方案一样，该解决方案返回一个布尔值，并且不会给出用于共线性的第三个结果。但它将给出一个有意义的结果，例如：

(is-left? [[1 1] [3 1]] [10 1])
false

- Purplejacket