점이 선의 오른쪽인지 왼쪽인지 확인하는 방법

점이 선의 오른쪽인지 왼쪽인지 확인하는 방법

---

나는 일련의 포인트가 있습니다. 나는 그것들을 2 개의 별개의 세트로 나누고 싶습니다. 이를 위해 두 점 ( a 및 b )을 선택하고 그 사이에 가상의 선을 그립니다. 이제이 선에서 남은 모든 점을 한 세트에,이 선에서 오른쪽에있는 점을 다른 세트에 갖기를 원합니다.

주어진 지점 z 에 대해 왼쪽 또는 오른쪽 집합에 있는지 어떻게 알 수 있습니까? azb 사이의 각도를 계산하려고 했습니다. 180 도보 다 작은 각도는 오른쪽에 있고 180 도는 왼쪽에 있습니다.하지만 ArcCos의 정의 때문에 계산 된 각도는 항상 180 °보다 작습니다. 180 °보다 큰 각도를 계산하는 공식이 있습니까 (또는 오른쪽 또는 왼쪽을 선택하는 다른 공식)?

---

벡터 행렬식의 부호를 사용합니다 (AB,AM). 여기서는 M(X,Y)쿼리 지점입니다.

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

그것은 0줄에 있고 +1한쪽 -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를 반환합니다.

---

당신은 결정자의 부호를 본다

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

한쪽에있는 점은 양수이고 다른 쪽은 음수입니다 (선 자체의 점에 대해서는 0).

---

벡터 (y1 - y2, x2 - x1)는 선에 수직이며 항상 오른쪽을 가리 킵니다 (또는 평면 방향이 내 것과 다른 경우 항상 왼쪽을 가리킴).

그런 다음 해당 벡터의 내적을 계산하고 점이 (x3 - x1, y3 - y1)수직 벡터 (내적> 0) 와 같은 선에 있는지 여부를 확인할 수 있습니다 .

---

나는 이것을 자바로 구현하고 단위 테스트를 실행했습니다 (아래 소스). 위의 솔루션 중 어느 것도 작동하지 않습니다. 이 코드는 단위 테스트를 통과합니다. 통과하지 못한 단위 테스트를 발견하면 알려주세요.

코드 : 참고 : 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));
}

---

선 ab 의 방정식을 사용하여 정렬 할 점과 동일한 y 좌표에있는 선의 x 좌표를 얻습니다.

• 점의 x> 선의 x이면 점은 선의 오른쪽에 있습니다.
• 포인트의 x <라인의 x이면 포인트는 라인의 왼쪽에 있습니다.
• 포인트의 x == 라인의 x이면 포인트는 라인에 있습니다.

---

먼저 수직선이 있는지 확인하십시오.

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

---

기본적으로 주어진 다각형에 대해 훨씬 쉽고 간단한 솔루션이 있다고 생각합니다. 네 개의 정점 (p1, p2, p3, p4)으로 구성되어 있고, 다각형에서 두 개의 극히 반대되는 정점을 다른 곳에서 찾습니다. 예를 들어 가장 왼쪽 상단 꼭지점 (p1이라고 함)과 가장 오른쪽 하단에 위치한 반대 꼭지점 (이라고 함)을 찾습니다. 따라서 테스트 포인트 C (x, y)가 주어지면 이제 C와 p1, C와 p4 사이를 다시 확인해야합니다.

if cx > p1x AND cy > p1y ==> means that C is lower and to right of p1 next if cx < p2x AND cy < p2y ==> means that C is upper and to left of p4

conclusion, C is inside the rectangle.

Thanks :)

---

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.

---

@AVB's answer in ruby

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

If det is positive its above, if negative its below. If 0, its on the line.

---

Here's a version, again using the cross product logic, written in 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)))))

Example usage:

(is-left? [[-3 -1] [3 1]] [0 10])
true

Which is to say that the point (0, 10) is to the left of the line determined by (-3, -1) and (3, 1).

NOTE: This implementation solves a problem that none of the others (so far) does! Order matters when giving the points that determine the line. I.e., it's a "directed line", in a certain sense. So with the above code, this invocation also produces the result of true:

(is-left? [[3 1] [-3 -1]] [0 10])
true

That's because of this snippet of code:

(sort line)

Finally, as with the other cross product based solutions, this solution returns a boolean, and does not give a third result for collinearity. But it will give a result that makes sense, e.g.:

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

---

I wanted to provide with a solution inspired by physics.

Imagine a force applied along the line and you are measuring the torque of the force about the point. If the torque is positive (counterclockwise) then the point is to the "left" of the line, but if the torque is negative the point is the "right" of the line.

So if the force vector equals the span of the two points defining the line

fx = x_2 - x_1
fy = y_2 - y_1

you test for the side of a point (px,py) based on the sign of the following test

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

---

An alternative way of getting a feel of solutions provided by netters is to understand a little geometry implications.

Let pqr=[P,Q,R] are points that forms a plane that is divided into 2 sides by line [P,R]. We are to find out if two points on pqr plane, A,B, are on the same side.

Any point T on pqr plane can be represented with 2 vectors: v = P-Q and u = R-Q, as:

T' = T-Q = i * v + j * u

Now the geometry implications:

1. i+j =1: T on pr line
2. i+j <1: T on Sq
3. i+j >1: T on Snq
4. i+j =0: T = Q
5. i+j <0: T on Sq and beyond Q.

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

In general,

• i+j is a measure of how far T is away from Q or line [P,R], and
• the sign of i+j-1 implicates T's sideness.

The other geometry significances of i and j (not related to this solution) are:

• i,j are the scalars for T in a new coordinate system where v,u are the new axes and Q is the new origin;
• i, j can be seen as pulling force for P,R, respectively. The larger i, the farther T is away from R (larger pull from P).

The value of i,j can be obtained by solving the equations:

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

So we are given 2 points, A,B on the plane:

A = a1 * v + a2 * u B = b1 * v + b2 * u

If A,B are on the same side, this will be true:

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

Note that this applies also to the question: Are A,B in the same side of plane [P,Q,R], in which:

T = i * P + j * Q + k * R

and i+j+k=1 implies that T is on the plane [P,Q,R] and the sign of i+j+k-1 implies its sideness. From this we have:

A = a1 * P + a2 * Q + a3 * R B = b1 * P + b2 * Q + b3 * R

and A,B are on the same side of plane [P,Q,R] if

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

ReferenceURL : https://stackoverflow.com/questions/3461453/determine-which-side-of-a-line-a-point-lies