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

Question

我有一组要点。我想将它们分成两个不同的集合。为此，我选择两个点（a 和 b）并在它们之间绘制一条假想线。现在我想将这条线左边的所有点放在一组中，将这条线右边的点放在另一组中。

我如何判断任何给定点z它是在左边还是在右边？我尝试计算 azb 之间的角度 - 小于 180 的角度在右侧，大于 180 的角度在左侧 - 但由于 ArcCos 的定义，计算出的角度总是较小大于180°。是否有计算大于 180° 的角度的公式（或选择右侧或左侧的任何其他公式）？

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。

Answer 2

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

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

它是0在线上，+1 位于一侧，-1 位于另一侧。

Answer 3

您查看 的行列式的符号，

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

对于一侧的点，它为正，而在另一侧，则为负（对于直线本身上的点，它为零）。

Answer 4

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

然后，您可以计算该向量与 (x3 - x1, y3 - y1) 的点积，以确定该点是否与垂直向量位于直线的同一侧（点积 > <代码>0）或不。

Answer 5

使用直线方程 ab，获取 x 坐标与要排序的点具有相同 y 坐标的线。

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

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));
}

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

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。

现在为 x 和 y 插入 (x3, y3)。这是一些伪代码，详细说明了应该发生的情况：

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

Answer 9

假设点是 (Ax,Ay) (Bx,By) 和 (Cx,Cy)，则需要计算：

(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)

这如果 C 点位于 A 点和 B 点形成的直线上，则该值为零，并且根据边的不同，其符号也不同。这是哪一侧取决于 (x,y) 坐标的方向，但您可以将 A、B 和 C 的测试值代入此公式中，以确定负值是在左侧还是在右侧。

Answer 10

基本上，我认为有一个更容易和直接的解决方案，对于任何给定的多边形，假设由四个顶点（p1，p2，p3，p4）组成，找到多边形中两个极端相对的顶点，在另一个换句话说，找到例如最左上角的顶点（比方说 p1）和位于最右下角的相反顶点（比方说 ）。因此，给定您的测试点 C(x,y)，现在您必须在 C 和 p1 以及 C 和 p4 之间进行双重检查

： p1x 和 cy ＞ p1y==>表示 C 低于 p1 且位于 p1 的右侧
下一个
如果 cx < p2x AND cy ＜ p2y==>意味着C在p4结论的左上方

，C在矩形内部。

谢谢 ：）

Answer 11

@AVB 在 ruby​​ 中的答案

det = Matrix[
  [(x2 - x1), (x3 - x1)],
  [(y2 - y1), (y3 - y1)]
].determinant

如果 det 为正则其上方，如果为负则其下方。如果为0，则上线。

Answer 12

这是一个版本，再次使用跨积逻辑，用 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

Answer 13

现有解决方案的问题：

虽然我发现 Eric Bainville 的答案是正确的，但我发现它完全不足以理解：

• 两个向量如何具有行列式？我认为这适用于矩阵？
• 什么是符号？
• 如何将两个向量转换为矩阵？

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

• Bx 是什么？
• Y 是什么？ Y 不是应该是向量，而不是标量吗？
• 为什么解决方案是正确的 - 其背后的推理是什么？

此外，我的用例涉及复杂曲线而不是简单的直线，因此它需要一些重新调整：

重构答案

Point a = new Point3d(ax, ay, az); // point on line
Point b = new Point3d(bx, by, bz); // point on line

如果您想查看您的点是否高于/低于曲线< /em>，那么您需要获得您感兴趣的特定曲线的一阶导数 - 也称为曲线上点的切线。如果你能这样做，那么你就可以突出你的兴趣点。当然，如果你的曲线是一条直线，那么你只需要兴趣点而不需要切线。切线就是直线。

Vector3d lineVector = curve.GetFirstDerivative(a); // where "a" is a point on the curve. You may derive point b with a simple displacement calculation:

Point3d b = new Point3d(a.X, a.Y, a.Z).TransformBy(
                 Matrix3d.Displacement(curve.GetFirstDerivative(a))
                );

Point m = new Point3d(mx, my, mz) // the point you are interested in.

解决方案：

return (b.X - a.X) * (m.Y - a.Y) - (b.Y - a.Y) * (m.X - a.X) < 0; // the answer

适合我！请参阅上面照片中的证明。青砖满足条件，但是外面的砖被过滤掉了！在我的用例中 - 我只想要接触圆圈的砖块。

答案背后的理论

我将返回解释这一点。有一天。不知怎的...

Answer 14

感受 netters 提供的解决方案的另一种方法是了解一些几何含义。

令 pqr=[P,Q,R] 是形成平面的点，该平面被直线 [P,R] 分为 2 个边。我们要找出pqr平面上的两个点A、B是否在同一侧。

pqr 平面上的任何点 T 都可以用 2 个向量表示：v = PQ 和 u = RQ，如下：

T' = TQ = < strong>i * v + j * u

现在几何含义：

1. i+j =1: T on pr line
2. i+j <1: T on Sq
3. i+j > 1: T on Snq
4. i+j =0: T = Q
5. i+j <0: T on Sq 且超出 Q。


i+j: <0 0 <1 =1 >1
---------Q------[PR]--------- <== 这是 PQR 平面
^
公关线


一般来说，

• i+j 是 T 距离 Q 或线 [P,R] 的距离的度量，以及
• i+j-1 的符号strong> 暗示 T 的侧面。

i 和 j 的其他几何意义（与此解无关）是：

• i,j 是新坐标系中 T 的标量，其中 v,u 是新轴，Q 是新原点；
• i、j可以分别视为P、R的拉力。 i越大，T离R越远（来自P的拉力越大）。

i,j 的值可以通过求解方程得到：

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

因此我们在平面上有 2 个点 A,B：


A = a1 * v + a2 * u
B = b1 * v + b2 * u


如果 A、B 在同一侧，则为 true：

sign(a1+a2-1) = sign(b1+b2-1)

请注意，这也适用于问题：A、B 是否在平面 [P,Q,R] 的同一侧，其中：

T = i * P + j > * Q + k * R

和 i+j+k=1 意味着 T 在平面 [P,Q,R] 上并且 的符号i+j+k-1 暗示其侧面。由此我们有：


A = a1 * P + a2 * Q + a3 * R
B = b1 * P + b2 * Q + b3 * R


和 A,B 位于平面 [P,Q,R] 的同一侧，如果

sign(a1+a2+a3-1) = sign(b1+b2+b3-1)

Answer 15

线方程为 y-y1 = m(x-x1)，

此处 m 为 y2-y1 / x2-x1

现在将 m 放入方程中，并将条件置于 y < m(x-x1) + y1 那么它是左侧点，

例如。

for i in rows:

  for j in cols:

    if j>m(i-a)+b:

      image[i][j]=0

Answer 16

A(x1,y1) B(x2,y2) 长度为 L=sqrt( (y2-y1)^2 + (x2-x1)^2 ) 的线段

和点 M(x,y)

进行变换坐标以便将 A 点作为新的起点，将 B 点作为新 X 轴的点，

我们得到 M 点的新坐标

，它们是
newX = ((x-x1)(x2-x1)+(y-y1)(y2-y1)) / L
从 (x-x1)*cos(t)+(y-y1)*sin(t) 其中 cos(t)=(x2-x1)/L, sin(t)=(y2-y1)/L

newY = ((y-y1)(x2-x1)-(x-x1)(y2-y1)) / L
从 (y-y1)*cos(t)-(x-x1)*sin(t) 得出，

因为“左”是 X 轴的 Y 为正的一侧，如果 newY（即 M 到 AB 的距离） )为正，那么它在AB（新的X轴）的左侧
如果您只想要符号，则可以省略除以 L（始终为正）