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

Question

我有一组点。我想将它们分成2个不同的集合。为此，我选择两个点（a和b）并在它们之间绘制一条虚线。现在我想把这一行中的所有点都放在一个集合中，并且这些行中的所有点都放在另一个集合中。

我该如何判断任何给定的点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

使用equation of the lineab，获取与要排序的点在同一个y坐标线上的x坐标。

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

Answer 3

你看看

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

行列式这将利好点一侧的（上线本身分零）的标志，而在其他阴性。

Answer 4

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

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

Answer 5

尝试这个代码，其利用一个cross product的：

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 =第2行; c =指向检查。

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

如果该行是水平的，那么如果该点位于该行之上，则返回true。

Answer 6

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

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 7

基本上，我认为有一个解决方案，它是非常容易和简单的，对于任何给定的多边形，可以说包括四个顶点（P1，P2，P3 ，p4），在多边形中找到两个极端相对的顶点，换句话说，找到例如最左上角的顶点（可以说是p1）以及位于最右下角（可以说）的相反顶点。因此，考虑到您的测试点C（x，y），现在您必须在C与p1和C以及p4之间进行双重检查：如果cx> p1x AND cy> p1y ==>意味着C较低并且到的P1 下 右如果CX < P2X和cy < P2Y ==>表示C是上和向左P4

结论的，C是在矩形内。

谢谢:)

Answer 8

我在Java中实现这一点，并（下面源）跑一个单元测试。上述解决方案均不起作用。这段代码通过了单元测试。如果有人发现未通过单元测试，请告诉我。

代码：NOTE：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 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

@ 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) 

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

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