153

I have a set of points. I want to separate them into 2 distinct sets. To do this, I choose two points (a and b) and draw an imaginary line between them. Now I want to have all points that are left from this line in one set and those that are right from this line in the other set.

How can I tell for any given point z whether it is in the left or in the right set? I tried to calculate the angle between a-z-b – angles smaller than 180 are on the right hand side, greater than 180 on the left hand side – but because of the definition of ArcCos, the calculated angles are always smaller than 180°. Is there a formula to calculate angles greater than 180° (or any other formula to chose right or left side)?

4

15 に答える 15

264

外積を利用するこのコードを試してください:

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 を返します。

于 2010-08-11T18:19:46.063 に答える
231

ベクトル の行列式の符号を使用します(AB,AM)。ここM(X,Y)で、 はクエリ ポイントです。

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

それは0線上にあり、+1片側-1にあり、反対側にあります。

于 2009-10-13T14:12:42.813 に答える
46

あなたはの行列式のサインを見ます

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

一方のポイントでは正になり、もう一方のポイントでは負になります（ライン自体のポイントではゼロになります）。

于 2010-08-11T18:14:35.913 に答える
10

ベクトル(y1 - y2, x2 - x1)は線に垂直であり、常に右を指します（または、平面の方向が私のものと異なる場合は、常に左を指します）。

次に、そのベクトルの内積を計算し、点(x3 - x1, y3 - y1)が垂直ベクトルと同じ側にあるかどうかを判断できます（内積> 0）。

于 2010-08-11T18:14:59.500 に答える
6

線abの方程式を 使用して、並べ替える点と同じ y 座標にある線の x 座標を取得します。

  • ポイントの x > ラインの x の場合、ポイントはラインの右側にあります。
  • ポイントの x < ラインの x の場合、ポイントはラインの左側にあります。
  • ポイントの x == ラインの x の場合、ポイントはライン上にあります。
于 2009-10-13T14:22:29.930 に答える
5

まず、縦線があるかどうかを確認します。

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)ます。何が起こるべきかを詳述した疑似コードを次に示します。xy

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
于 2010-08-11T18:20:41.717 に答える
5

これを Java で実装し、単体テストを実行しました (以下のソース)。上記の解決策はどれも機能しません。このコードは単体テストに合格します。合格しない単体テストを誰かが見つけたら、私に知らせてください。

コード: 注: nearlyEqual(double,double)2 つの数値が非常に近い場合は 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));
}
于 2011-12-15T18:34:10.870 に答える
4

物理学に着想を得たソリューションを提供したかったのです。

線に沿って加えられた力を想像してください。その点についての力のトルクを測定しています。トルクが正 (反時計回り) の場合、点は線の「左」にありますが、トルクが負の場合、点は線の「右」にあります。

したがって、力ベクトルが直線を定義する 2 点のスパンに等しい場合、

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
于 2018-12-18T15:00:30.007 に答える
3

Assuming the points are (Ax,Ay) (Bx,By) and (Cx,Cy), you need to compute:

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

This will equal zero if the point C is on the line formed by points A and B, and will have a different sign depending on the side. Which side this is depends on the orientation of your (x,y) coordinates, but you can plug test values for A,B and C into this formula to determine whether negative values are to the left or to the right.

于 2013-03-19T12:35:33.447 に答える
2

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)

最後に、他のクロス積ベースのソリューションと同様に、このソリューションはブール値を返し、共線性の 3 番目の結果は得られません。ただし、意味のある結果が得られます。たとえば、次のようになります。

(is-left? [[1 1] [3 1]] [10 1])
false
于 2015-02-21T00:42:20.570 に答える
1

基本的に、特定のポリゴンに対して、4つの頂点（p1、p2、p3、p4）で構成されているとしましょう。ポリゴン内の2つの極端に反対の頂点を見つけます。たとえば、最も左上の頂点 (p1 とします) と、最も右下にある反対側の頂点 ( とします) を見つけます。したがって、テスト ポイント C(x,y) が与えられた場合、C と p1 および C と p4 の間でダブル チェックを行う必要があります。

if cx > p1x AND cy > p1y ==> は、C が p1 の右下にあることを意味します。 next if cx < p2x AND cy < p2y ==> は、C が p4 の左上にあることを意味します。

結論、Cは長方形の中にあります。

ありがとう ：）

于 2011-05-17T17:31:09.617 に答える