포인트가 N 시간보다 빠르게 2D convex 폴리곤 안에 있는지 확인하는 방법

Question

포인트가 모든 다각형 안에 있는지 알아보기위한 표준 광선 캐스팅 알고리즘을 알고 있습니다. 그러나 볼록 다각형으로 제한하면 더 빠른 방법이 있습니까?

Answer 1

예, 이진 검색을 사용할 수 있습니다. 이 작업은 재귀 적으로 크기의 일부 (예 : 반)로 다각형을 자르고 현재 어느면에 있는지 확인하여 수행 할 수 있습니다. 예를 들어, 정점 0과 정점 n/2를 지나는 선에서 양수인지 음수인지 확인하여 시작할 수 있습니다. 3 개의 꼭지점을 가지면 나머지 두면을 테스트하고 해당 삼각형에 대한 테스트를 마칩니다.

function TestConvexPolygon(point, polygon) 
    if polygon.size == 3 then 
    return TestTriangle(point, polygon) // constant time 

    if (TestLine(point, polygon[0], polygon[polygon.size/2]) > 0) 
    return TestConvexPolygon(point, new polygon from polygon.size/2 to polygon.size-1 and 0) 
    else 
    return TestConvexPolygon(point, new polygon from 0 to polygon.size/2) 

또 다른 방법을 생각하면 삼각형 팬으로 다각형을 볼 수 있다는 것입니다 시각화 :

여기 잘하면 쉽게이 이해할 수 있도록 몇 가지 의사 코드입니다. 그런 다음 포인트를 중앙 대 내부 중앙을 테스트하여 시작합니다. 그것은 팬으로부터 가능한 삼각형의 절반을 제거합니다. 삼각형 팬의 절반은 여전히 ​​삼각형 팬이므로 삼각형이 팬에 남아있을 때까지이 작업을 반복적으로 수행 할 수 있습니다. 그러면 삼각형이 명시 적으로 테스트됩니다.

실제 구현에는 인덱스 저글링이 필요하지만 그렇지 않으면 쉽고 강력합니다.

Answer 2

답으로, 알고리즘은 재귀 적입니다. 각 단계에서 포인트가 될 수없는 다각형 부분을 잘라냅니다. 다음은 C++ 코드입니다.

#include "stdafx.h" 
#include <vector> 
#include <iostream> 

struct vec2d { 
    double x, y; 
    vec2d(double _x, double _y) : x(_x), y(_y) {} 
}; 

// Finds the cross product of the vectors: AB x BC 
double crossProduct(vec2d pointA, vec2d pointB, vec2d pointC) { 
    vec2d vectorAB = vec2d(pointB.x - pointA.x, pointB.y - pointA.y); 
    vec2d vectorBC = vec2d(pointC.x - pointB.x, pointC.y - pointB.y); 

    return vectorAB.x * vectorBC.y - vectorBC.x * vectorAB.y; 
} 

// Finds area for the triangle ABC 
double S(vec2d A, vec2d B, vec2d C) { 
    return crossProduct(A, B, C)/2; 
} 

bool isPointInsideTriangle(vec2d A, vec2d B, vec2d C, vec2d point) 
{ 
    return S(A, B, point) >= 0 && S(B, C, point) >= 0 && S(C, A, point) >= 0; 
} 

bool isPointAboveLine(vec2d A, vec2d B, vec2d point) 
{ 
    return S(A, B, point) >= 0; 
} 

// O(logN), works only for convex polygons 
bool isPointInsidePolygon(std::vector<vec2d> polygon, vec2d point) { 
    if (polygon.size() == 3) { 
     return isPointInsideTriangle(polygon[0], polygon[1], polygon[2], point); 
    } 

    if (isPointAboveLine(polygon[0], polygon[polygon.size()/2], point)) { 
     std::vector<vec2d> polygonAbove(polygon.begin() + polygon.size()/2, polygon.end()); 
     polygonAbove.emplace(polygonAbove.begin(), polygon[0]); 
     return isPointInsidePolygon(polygonAbove, point); 
    } 
    else { 
     std::vector<vec2d> polygonBelow(polygon.begin(), polygon.begin() + polygon.size()/2 + 1); 
     return isPointInsidePolygon(polygonBelow, point); 
    } 
} 

int main() 
{ 
    std::vector<vec2d> convexPolygon; 
    convexPolygon.push_back(vec2d(0, 2)); 
    convexPolygon.push_back(vec2d(2, 0)); 
    convexPolygon.push_back(vec2d(4, 1)); 
    convexPolygon.push_back(vec2d(6, 3)); 
    convexPolygon.push_back(vec2d(6, 4)); 
    convexPolygon.push_back(vec2d(5, 6)); 
    convexPolygon.push_back(vec2d(2, 6)); 
    convexPolygon.push_back(vec2d(1, 4)); 
    std::cout << isPointInsidePolygon(convexPolygon, vec2d(2, 5)); 

    return 0; 
}