如何判断一个点是否在一条线的右侧或左侧

Question

我有一套积分.我想把它们分成两组.为此,我选择两个点(a和b)并在它们之间绘制一条虚线.现在我想让一行中从这一行留下的所有点和另一组中从该行开始的那些点.

如何判断任何给定点z是左侧还是右侧？我试图计算azb之间的角度- 小于180的角度在右侧,大于180在左侧 - 但由于ArcCos的定义,计算的角度总是小于180°.是否有公式计算大于180°的角度(或选择右侧或左侧的任何其他公式)？

Answer 1

试试这个使用交叉产品的代码:

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

其中a =线点1; b =线点2; c =指向检查.

如果公式等于0,则点为共线.

如果该行是水平的,那么如果该点位于该行之上,则返回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

我想提供一个受物理学启发的解决方案。

想象一下沿线施加的力，并且您正在测量该点周围的力的扭矩。如果扭矩为正（逆时针），则该点位于线的“左侧”，但如果扭矩为负，则该点位于线的“右侧”。

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

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 6

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

• 如果点的 x > 线的 x，则该点位于线的右侧。
• 如果点的 x < 线的 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

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