[performance] 2D 포인트가 다각형 내에 있는지 어떻게 알 수 있습니까?

그래픽의 경우 정수를 선호하지 않습니다. 많은 시스템이 UI 페인팅을 위해 정수를 사용하지만 (픽셀은 정수), 예를 들어 macOS는 모든 것을 위해 float를 사용합니다. macOS는 포인트 만 알고 있으며 포인트는 한 픽셀로 변환 될 수 있지만 모니터 해상도에 따라 다른 것으로 변환 될 수 있습니다. 망막 화면에서 반점 (0.5 / 0.5)은 픽셀입니다. 여전히 macOS UI가 다른 UI보다 훨씬 느리다는 것을 알지 못했습니다. 모든 3D API (OpenGL 또는 Direct3D)도 플로트와 함께 작동하며 최신 그래픽 라이브러리는 종종 GPU 가속을 활용합니다.

이제 당신은 속도가 주된 관심사라고 말했습니다. 알았어요. 정교한 알고리즘을 실행하기 전에 먼저 간단한 테스트를 수행하십시오. 다각형 주위에 축 정렬 경계 상자를 만듭니다 . 이것은 매우 쉽고 빠르며 이미 많은 계산을 안전하게 할 수 있습니다. 어떻게 작동합니까? 다각형의 모든 점을 반복하고 X 및 Y의 최소 / 최대 값을 찾습니다.

예를 들어 포인트가 (9/1), (4/3), (2/7), (8/2), (3/6)있습니다. 즉, Xmin은 2, Xmax는 9, Ymin은 1, Ymax는 7입니다. 두 모서리 (2/1)와 (9/7)이있는 사각형 외부의 점은 다각형 내에있을 수 없습니다.

// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
    // Definitely not within the polygon!
}

이것은 어느 시점에서나 실행되는 첫 번째 테스트입니다. 보시다시피이 테스트는 매우 빠르지 만 매우 거칠습니다. 경계 사각형 내에있는 점을 처리하려면보다 정교한 알고리즘이 필요합니다. 이를 계산하는 방법에는 몇 가지가 있습니다. 어떤 방법이 작동하는지는 다각형에 구멍이 있거나 항상 단색인지에 따라 다릅니다. 다음은 단단한 것들 (하나의 볼록, 하나의 오목)의 예입니다.

그리고 여기에 구멍이 하나 있습니다 :

녹색은 중간에 구멍이 있습니다!

위의 세 가지 경우를 모두 처리 할 수 ​​있고 여전히 매우 빠른 가장 쉬운 알고리즘은 레이 캐스팅 입니다. 알고리즘의 아이디어는 매우 간단합니다. 다각형 외부에서 점까지 가상 광선을 그리고 다각형 측면에 얼마나 자주 충돌하는지 계산합니다. 적중 수가 짝수이면 다각형 외부에 있고 홀수이면 내부에 있습니다.

권수 알고리즘은 매우 가까운 다각형 라인에있는 점에 대한 더 정확하지만 훨씬 낮은 속도도의 대안이 될 것입니다. 부동 소수점 정밀도 및 반올림 문제로 인해 다각형쪽에 너무 가까운 점에 대해서는 광선 주조가 실패 할 수 있지만 실제로는 점이 측면에 가까운 것처럼 보이는 것처럼 거의 문제가되지 않습니다. 뷰어가 이미 내부 또는 외부에 있는지 인식합니다.

여전히 위의 경계 상자가 있습니다. 기억하십니까? 경계 상자 외부의 점을 선택하여 광선의 시작점으로 사용하십시오. 예를 들어 점 (Xmin - e/p.y)은 다각형 외부에 있어야합니다.

그러나 무엇 e입니까? 글쎄, e(실제로 엡실론) 경계 상자에 패딩을 제공합니다 . 내가 말했듯이, 다각형 선에 너무 가까이 시작하면 광선 추적이 실패합니다. 경계 상자가 다각형과 같을 수 있으므로 (다각형이 축 정렬 된 사각형 인 경우 경계 상자가 다각형 자체와 동일합니다!)이를 안전하게하려면 패딩이 필요합니다. 얼마나 크게 선택해야 e합니까? 너무 크지 않습니다. 그리기에 사용하는 좌표계 배율에 따라 다릅니다. 픽셀 단계 너비가 1.0 인 경우 1.0을 선택하십시오 (아직 0.1도 작동 했음).

이제 시작과 끝 좌표가있는 광선이 생겼으니, 문제는 ” 다각형 내의 점 “에서 ” 선이 다각형면과 얼마나 자주 교차하는지 “로 이동합니다. 따라서 이전과 같이 다각형 점으로 작업 할 수 없으므로 실제 측면이 필요합니다. 한 변은 항상 두 점으로 정의됩니다.

side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:

모든면에서 광선을 테스트해야합니다. 광선을 벡터로, 모든면을 벡터로 간주하십시오. 광선은 각면을 정확히 한 번만 또는 전혀 치지 않아야합니다. 같은 쪽을 두 번 칠 수 없습니다. 2D 공간의 두 선은 평행하지 않으면 항상 정확히 한 번 교차합니다.이 경우 절대 교차하지 않습니다. 그러나 벡터의 길이는 제한되어 있기 때문에 두 벡터는 평행하지 않으며 서로 만나기에는 너무 짧기 때문에 여전히 교차하지 않을 수 있습니다.

// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
    // Test if current side intersects with ray.
    // If yes, intersections++;
}
if ((intersections & 1) == 1) {
    // Inside of polygon
} else {
    // Outside of polygon
}

지금까지는 잘되었지만 두 벡터가 교차하는지 어떻게 테스트합니까? 다음은 트릭을 수행 해야하는 C 코드 (테스트되지 않음)입니다.

#define NO 0
#define YES 1
#define COLLINEAR 2

int areIntersecting(
    float v1x1, float v1y1, float v1x2, float v1y2,
    float v2x1, float v2y1, float v2x2, float v2y2
) {
    float d1, d2;
    float a1, a2, b1, b2, c1, c2;

    // Convert vector 1 to a line (line 1) of infinite length.
    // We want the line in linear equation standard form: A*x + B*y + C = 0
    // See: http://en.wikipedia.org/wiki/Linear_equation
    a1 = v1y2 - v1y1;
    b1 = v1x1 - v1x2;
    c1 = (v1x2 * v1y1) - (v1x1 * v1y2);

    // Every point (x,y), that solves the equation above, is on the line,
    // every point that does not solve it, is not. The equation will have a
    // positive result if it is on one side of the line and a negative one 
    // if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
    // 2 into the equation above.
    d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
    d2 = (a1 * v2x2) + (b1 * v2y2) + c1;

    // If d1 and d2 both have the same sign, they are both on the same side
    // of our line 1 and in that case no intersection is possible. Careful, 
    // 0 is a special case, that's why we don't test ">=" and "<=", 
    // but "<" and ">".
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    // The fact that vector 2 intersected the infinite line 1 above doesn't 
    // mean it also intersects the vector 1. Vector 1 is only a subset of that
    // infinite line 1, so it may have intersected that line before the vector
    // started or after it ended. To know for sure, we have to repeat the
    // the same test the other way round. We start by calculating the 
    // infinite line 2 in linear equation standard form.
    a2 = v2y2 - v2y1;
    b2 = v2x1 - v2x2;
    c2 = (v2x2 * v2y1) - (v2x1 * v2y2);

    // Calculate d1 and d2 again, this time using points of vector 1.
    d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
    d2 = (a2 * v1x2) + (b2 * v1y2) + c2;

    // Again, if both have the same sign (and neither one is 0),
    // no intersection is possible.
    if (d1 > 0 && d2 > 0) return NO;
    if (d1 < 0 && d2 < 0) return NO;

    // If we get here, only two possibilities are left. Either the two
    // vectors intersect in exactly one point or they are collinear, which
    // means they intersect in any number of points from zero to infinite.
    if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;

    // If they are not collinear, they must intersect in exactly one point.
    return YES;
}

입력 값은 벡터 1 ( 및 )과 벡터 2 ( 및 ) 의 두 끝점 입니다 . 따라서 2 개의 벡터, 4 개의 점, 8 개의 좌표가 있습니다. 그리고 분명하다. 교차로를 늘리고 아무것도하지 않습니다.v1x1/v1y1v1x2/v1y2v2x1/v2y1v2x2/v2y2YESNOYESNO

COLLINEAR는 어떻습니까? 즉, 두 벡터 모두 위치와 길이에 따라 동일한 무한 선에 놓이거나 전혀 교차하지 않거나 끝없는 포인트 수로 교차합니다. 나는이 사건을 어떻게 처리 해야할지 잘 모르겠습니다. 어쨌든 교차로 계산하지 않을 것입니다. 부동 소수점 반올림 오류로 인해 실제로이 경우는 드물다. 더 나은 코드는 아마도 테스트하지 않을 == 0.0f것이지만 < epsilonepsilon이 다소 작은 곳 과 같은 것을 대신합니다 .

더 많은 수의 포인트를 테스트 해야하는 경우 다각형 측의 선형 방정식 표준 형태를 메모리에 유지하여 모든 것을 약간 가속화 할 수 있으므로 매번 다시 계산할 필요는 없습니다. 이렇게하면 다각형 면당 3 개의 부동 소수점 값을 메모리에 저장하는 대신 모든 테스트에서 2 개의 부동 소수점 곱셈과 3 개의 부동 소수점 빼기를 저장할 수 있습니다. 일반적인 메모리와 계산 시간의 균형을 유지합니다.

마지막으로, 3D 하드웨어를 사용하여 문제를 해결할 수 있다면 흥미로운 대안이 있습니다. GPU가 모든 작업을 수행하도록하십시오. 화면이 아닌 그림 표면을 만듭니다. 검은 색으로 완전히 채우십시오. 이제 OpenGL 또는 Direct3D를 사용하여 다각형 (또는 점이 다각형 내에 있는지 여부 만 테스트하려는 경우 모든 다각형)을 페인트하고 다각형을 다른 색으로 채 웁니다 색상 (예 : 흰색) 점이 다각형 내에 있는지 확인하려면 그리기 표면에서이 점의 색을 가져옵니다. 이것은 단지 O (1) 메모리 반입입니다.

물론이 방법은 도면 표면이 크지 않아도 사용할 수 있습니다. GPU 메모리에 맞지 않으면이 방법은 CPU에서 수행하는 것보다 느립니다. 거대해야하고 GPU가 최신 셰이더를 지원하는 경우 위에 표시된 레이 캐스팅을 GPU 셰이더로 구현하여 GPU를 계속 사용할 수 있습니다. 더 많은 수의 폴리곤 또는 많은 수의 테스트 포인트가 있다면, 이것은 일부 GPU가 64-256 포인트를 병렬로 테스트 할 수 있다는 점을 고려할 것입니다. 그러나 CPU에서 GPU로 데이터를 다시 전송하는 것은 항상 비용이 많이 들기 때문에 점 또는 다각형이 동적이며 자주 변경되는 몇 가지 간단한 다각형에 대해 몇 개의 점을 테스트하기 만하면 GPU 접근 방식이 거의 지불하지 않습니다. 떨어져서.

답변

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

public bool IsPointInPolygon( Point p, Point[] polygon )
{
    double minX = polygon[ 0 ].X;
    double maxX = polygon[ 0 ].X;
    double minY = polygon[ 0 ].Y;
    double maxY = polygon[ 0 ].Y;
    for ( int i = 1 ; i < polygon.Length ; i++ )
    {
        Point q = polygon[ i ];
        minX = Math.Min( q.X, minX );
        maxX = Math.Max( q.X, maxX );
        minY = Math.Min( q.Y, minY );
        maxY = Math.Max( q.Y, maxY );
    }

    if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
    {
        return false;
    }

    // https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    bool inside = false;
    for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
    {
        if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
             p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
        {
            inside = !inside;
        }
    }

    return inside;
}

function pointIsInPoly(p, polygon) {
    var isInside = false;
    var minX = polygon[0].x, maxX = polygon[0].x;
    var minY = polygon[0].y, maxY = polygon[0].y;
    for (var n = 1; n < polygon.length; n++) {
        var q = polygon[n];
        minX = Math.min(q.x, minX);
        maxX = Math.max(q.x, maxX);
        minY = Math.min(q.y, minY);
        maxY = Math.max(q.y, maxY);
    }

    if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
        return false;
    }

    var i = 0, j = polygon.length - 1;
    for (i, j; i < polygon.length; j = i++) {
        if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) &&
                p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) {
            isInside = !isInside;
        }
    }

    return isInside;
}

[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]

def isInside(self, border, target):
degree = 0
for i in range(len(border) - 1):
    a = border[i]
    b = border[i + 1]

    # calculate distance of vector
    A = getDistance(a[0], a[1], b[0], b[1]);
    B = getDistance(target[0], target[1], a[0], a[1])
    C = getDistance(target[0], target[1], b[0], b[1])

    # calculate direction of vector
    ta_x = a[0] - target[0]
    ta_y = a[1] - target[1]
    tb_x = b[0] - target[0]
    tb_y = b[1] - target[1]

    cross = tb_y * ta_x - tb_x * ta_y
    clockwise = cross < 0

    # calculate sum of angles
    if(clockwise):
        degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))
    else:
        degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C)))

if(abs(round(degree) - 360) <= 3):
    return True
return False

                       number of edges per polygon
                         3       4      10      100    1000
MacMartin               2.9     3.2     5.9     50.6    485
Crossings               3.1     3.4     6.8     60.0    624
Triangle Fan+edge sort  1.1     1.8     6.5     77.6    787
Triangle Fan            1.2     2.1     7.3     85.4    865
Barycentric             2.1     3.8    13.8    160.7   1665
Angle Summation        56.2    70.4   153.6   1403.8  14693

Grid (100x100)          1.5     1.5     1.6      2.1      9.8
Grid (20x20)            1.7     1.7     1.9      5.7     42.2
Bins (100)              1.8     1.9     2.7     15.1    117
Bins (20)               2.1     2.2     3.7     26.3    278