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

Question

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

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

Answer 1

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

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

有0就行，和+1在一侧，-1在另一侧上。

Answer 2

试试这个代码，其利用一个叉积的：

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

其中一 =行点1; B'/ EM> =行点2; C =指向核对。

如果公式是等于0，则点是共线的。

如果该行是水平的，则此如果该点是线之上返回true。

Answer 3

您看的行列式

的符号

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

这将是正面为在一侧上的点，和负的其他（和零就行本身点）。

Answer 4

的载体(y1 - y2, x2 - x1)是垂直于线，始终指向右侧（或总是指向左边，如果平面取向是我的不同）。

可以然后计算该向量和(x3 - x1, y3 - y1)的点积以确定该点位于线为垂直矢量（点积> 0）的相同侧或不

Answer 5

我在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 6

使用 直线方程 ab, ，获取与要排序的点位于同一 y 坐标的线上的 x 坐标。

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

Answer 7

首先检查，如果你有一条垂直线：

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

Answer 8

基本上，我认为有一个解决方案，它是非常容易和简单的，对于任何给定的多边形，可以说包括四个顶点（P1，P2，P3，P4），发现在多边形的两种极端相反的顶点在另一个单词，找出例如最左上顶点（可以说P1）和相对的顶点，其位于至多右下方（可以说）。因此，鉴于您的测试C点（X，Y），现在你必须让C和P1和C与P4之间仔细检查：

如果CX> P1X和cy> P1Y ==>表示C是较低和p1的右 下一个 如果CX 表示C是上和向左P4的

结论，C是在矩形内。

谢谢:)

Answer 9

假设点是（AX，AY）（BX，BY）和（CX，CY），则需要计算：

（Bx的 - 斧）*（CY - AY） - （由 - AY）*（CX - 斧）

此将等于零，如果点C是由点A和B形成的线，并且将具有根据侧不同的符号。哪一侧，这是依赖于取向的（X，Y）坐标，但是可以插为A，B和C试验值代入此公式，以确定负值是否向左或向右移动。

Answer 10

@ AVB在红宝石回答

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

如果det为正其以上，如果为负其下方。如果为0，其就行了。

Answer 11

这里的一个版本，再次使用叉积逻辑，写在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)

最后，与其它叉积基础的解决方案，该解决方案返回一个布尔值，并且不给共线性第三结果。但它会给出一个结果是有道理的，e.g：

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

Answer 12

我想与通过物理激发的溶液提供。

想象沿着线施加的力和要测量绕点的力的扭矩。如果扭矩是正的（逆时针），则点在该行的“左”，但如果扭矩为负的点是该行的“右”。

因此，如果该力矢量等于两个点定义的直线的跨度

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 13

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

让 普格=[P,Q,R] 是形成被线分为 2 条边的平面的点 [P，R]. 。我们要找出是否有两个点 普格 平面 A、B 在同一侧。

任意点 时间 pqr 平面上可以用 2 个向量表示： v = P-Q 和 你 = R-Q，为：

T' = T-Q = 我 * v + j *你

现在几何意义：

1. i+j =1：公关线上的T
2. i+j <1：T 平方
3. i+j >1:T on Snq
4. i+j =0:T = Q
5. i+j <0：T 在 Sq 上且超出 Q。

i+j: <0 0 <1 =1 >1 ---------Q------[PR]--------- <== this is PQR plane ^ pr line

一般来说，

• i+j 是 T 距 Q 或线 [P,R] 多远的度量, ， 和
• 的标志 i+j-1 暗示了T的侧面。

其他几何意义 我 和 j （与此解决方案无关）是：

• 我,j 是新坐标系中 T 的标量，其中 v,u 是新的轴和 问 是新的原点；
• 我, j 可以看作 拉力 为了 磷、磷, ， 分别。较大的 我, ，T 距离越远 右 （较大的拉力来自 磷).

的价值 我,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 在同一边，则如下：

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

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

T= 我 * P + j *问+ 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)