如何判斷一個點是否在一條線的右側或左側

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