[C#] 점이 선의 오른쪽인지 왼쪽인지 알려주는 방법

C# / 글쓴이

포인트가 있습니다. 나는 그것들을 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).

답변

선 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

답변

나는 이것을 자바로 구현하고 단위 테스트 (아래 소스)를 실행했다. 위의 해결책 중 어느 것도 작동하지 않습니다. 이 코드는 단위 테스트를 통과합니다. 누구도 통과하지 못하는 단위 테스트를 찾으면 알려주십시오.

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