다각형 알고리즘의 포인트

다각형 알고리즘의 포인트

---

아래 알고리즘이이 링크 에서 주어진 다각형에 점이 있는지 확인하는 것을 보았습니다 .

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;
}

나는이 알고리즘을 시도했고 실제로 완벽하게 작동합니다. 하지만 안타깝게도 아이디어를 얻기 위해 시간을 보낸 후에는 잘 이해할 수 없습니다.

그러니 누군가이 알고리즘을 이해할 수 있다면 저에게 조금 설명해주세요.

감사합니다.

---

알고리즘은 오른쪽에 레이 캐스팅입니다. 루프가 반복 될 때마다 테스트 포인트가 다각형의 가장자리 중 하나에 대해 확인됩니다. 포인트의 y 좌표가 에지의 범위 내에 있으면 if-test의 첫 번째 줄이 성공합니다. 두 번째 줄은 테스트 지점이 줄의 왼쪽에 있는지 확인합니다 (제 생각에는 확인할 수있는 스크랩 종이가 없습니다). 이것이 사실이면 테스트 포인트에서 오른쪽으로 그려진 선이 해당 가장자리를 교차합니다.

의 값을 반복적으로 반전함으로써 c알고리즘은 오른쪽 선이 다각형을 교차하는 횟수를 계산합니다. 홀수 번 교차하면 점이 안쪽에있는 것입니다. 짝수이면 포인트는 밖에 있습니다.

나는 a) 부동 소수점 산술의 정확성, b) 수평 가장자리 또는 꼭지점과 동일한 y 좌표를 갖는 테스트 포인트의 효과에 대해 우려 할 것입니다.

---

Chowlett은 모든면에서 정확합니다. 알고리즘은 포인트가 다각형의 선에 있으면 외부에 있다고 가정합니다. 경우에 따라 이것은 거짓입니다. 두 개의 '>'연산자를 '> ='로 변경하고 '<'를 '<='로 변경하면 문제가 해결됩니다.

bool PointInPolygon(Point point, Polygon polygon) {
  vector<Point> points = polygon.getPoints();
  int i, j, nvert = points.size();
  bool c = false;

  for(i = 0, j = nvert - 1; i < nvert; j = i++) {
    if( ( (points[i].y >= point.y ) != (points[j].y >= point.y) ) &&
        (point.x <= (points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) + points[i].x)
      )
      c = !c;
  }

  return c;
}

---

이것은 실제 코드에서 레이트 레이싱 알고리즘을 설명하기 위해 얻을 수있는 것만 큼 상세 할 수 있습니다. 최적화되지 않을 수도 있지만 항상 시스템을 완전히 파악한 후에 이루어져야합니다.

    //method to check if a Coordinate is located in a polygon
public boolean checkIsInPolygon(ArrayList<Coordinate> poly){
    //this method uses the ray tracing algorithm to determine if the point is in the polygon
    int nPoints=poly.size();
    int j=-999;
    int i=-999;
    boolean locatedInPolygon=false;
    for(i=0;i<(nPoints);i++){
        //repeat loop for all sets of points
        if(i==(nPoints-1)){
            //if i is the last vertex, let j be the first vertex
            j= 0;
        }else{
            //for all-else, let j=(i+1)th vertex
            j=i+1;
        }

        float vertY_i= (float)poly.get(i).getY();
        float vertX_i= (float)poly.get(i).getX();
        float vertY_j= (float)poly.get(j).getY();
        float vertX_j= (float)poly.get(j).getX();
        float testX  = (float)this.getX();
        float testY  = (float)this.getY();

        // following statement checks if testPoint.Y is below Y-coord of i-th vertex
        boolean belowLowY=vertY_i>testY;
        // following statement checks if testPoint.Y is below Y-coord of i+1-th vertex
        boolean belowHighY=vertY_j>testY;

        /* following statement is true if testPoint.Y satisfies either (only one is possible) 
        -->(i).Y < testPoint.Y < (i+1).Y        OR  
        -->(i).Y > testPoint.Y > (i+1).Y

        (Note)
        Both of the conditions indicate that a point is located within the edges of the Y-th coordinate
        of the (i)-th and the (i+1)- th vertices of the polygon. If neither of the above
        conditions is satisfied, then it is assured that a semi-infinite horizontal line draw 
        to the right from the testpoint will NOT cross the line that connects vertices i and i+1 
        of the polygon
        */
        boolean withinYsEdges= belowLowY != belowHighY;

        if( withinYsEdges){
            // this is the slope of the line that connects vertices i and i+1 of the polygon
            float slopeOfLine   = ( vertX_j-vertX_i )/ (vertY_j-vertY_i) ;

            // this looks up the x-coord of a point lying on the above line, given its y-coord
            float pointOnLine   = ( slopeOfLine* (testY - vertY_i) )+vertX_i;

            //checks to see if x-coord of testPoint is smaller than the point on the line with the same y-coord
            boolean isLeftToLine= testX < pointOnLine;

            if(isLeftToLine){
                //this statement changes true to false (and vice-versa)
                locatedInPolygon= !locatedInPolygon;
            }//end if (isLeftToLine)
        }//end if (withinYsEdges
    }

    return locatedInPolygon;
}

최적화에 대한 한마디 : 가장 짧은 (및 / 또는 가장 간결한) 코드가 가장 빠르게 구현된다는 것은 사실이 아닙니다. 배열에서 요소를 읽고 저장하고 필요할 때마다 배열에 액세스하는 것보다 코드 블록 실행 내에서 여러 번 사용하는 것이 훨씬 빠른 프로세스입니다. 이는 어레이가 매우 큰 경우 특히 중요합니다. 제 생각에는 배열의 각 용어를 잘 명명 된 변수에 저장하면 그 목적을 평가하는 것이 더 쉬워지고 따라서 훨씬 더 읽기 쉬운 코드를 형성 할 수 있습니다. 내 2 센트 만 ...

---

알고리즘은 가장 필요한 요소로 제거됩니다. 개발 및 테스트 후 불필요한 모든 항목이 제거되었습니다. 결과적으로 쉽게 이해할 수는 없지만 작업을 수행하고 성능도 매우 우수합니다.

---

나는 그것을 ActionScript-3으로 자유롭게 번역 할 수 있었다 .

// not optimized yet (nvert could be left out)
public static function pnpoly(nvert: int, vertx: Array, verty: Array, x: Number, y: Number): Boolean
{
    var i: int, j: int;
    var c: Boolean = false;
    for (i = 0, j = nvert - 1; i < nvert; j = i++)
    {
        if (((verty[i] > y) != (verty[j] > y)) && (x < (vertx[j] - vertx[i]) * (y - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
            c = !c;
    }
    return c;
}

---

이 알고리즘은 다각형의 측면이 교차하지 않는 한 모든 닫힌 다각형에서 작동합니다. 삼각형, 오각형, 정사각형, 심지어는 교차하지 않는 매우 매력적인 조각 선형 고무 밴드.

1) 다각형을 방향 벡터 그룹으로 정의하십시오. 이것은 다각형의 모든면이 정점 an에서 정점 an + 1로 이동하는 벡터로 설명된다는 것을 의미합니다. 벡터는 마지막 벡터가 첫 번째 벡터의 꼬리에 닿을 때까지 하나의 머리가 다음 벡터의 꼬리에 닿도록 지정됩니다.

2) 다각형 내부 또는 외부에서 테스트 할 점을 선택합니다.

3) 다각형의 둘레를 따라 각 벡터 Vn에 대해 테스트 포인트에서 시작하여 Vn의 꼬리에서 끝나는 벡터 Dn을 찾습니다. DnXVn / DN * VN으로 정의 된 벡터 Cn을 계산합니다 (X는 외적을 나타내고 *는 내적을 나타냄). Mn이라는 이름으로 Cn의 크기를 부릅니다.

4) 모든 Mn을 더하고이 수량을 K라고 부릅니다.

5) K가 0이면 점은 다각형 외부에 있습니다.

6) K가 0이 아니면 점은 다각형 내부에 있습니다.

이론적으로 다각형의 가장자리에있는 점은 정의되지 않은 결과를 생성합니다.

K의 기하학적 의미는 테스트 지점에 앉아있는 벼룩이 다각형 가장자리에서 걷고있는 개미가 왼쪽으로 걷는 전체 각도에서 오른쪽으로 걷는 각도를 뺀 각도입니다. 폐쇄 회로에서 개미는 시작된 지점에서 끝납니다. 위치에 관계없이 다각형 외부에서 답은 0입니다.
다각형 내부에서는 위치에 관계없이 "점 주위에 한 번"입니다.

---

---

좀 더 읽기 쉽게 원본 코드 를 변경했습니다 (또한 Eigen 사용). 알고리즘은 동일합니다.

// This uses the ray-casting algorithm to decide whether the point is inside
// the given polygon. See https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
bool pnpoly(const Eigen::MatrixX2d &poly, float x, float y)
{
    // If we never cross any lines we're inside.
    bool inside = false;

    // Loop through all the edges.
    for (int i = 0; i < poly.rows(); ++i)
    {
        // i is the index of the first vertex, j is the next one.
        // The original code uses a too-clever trick for this.
        int j = (i + 1) % poly.rows();

        // The vertices of the edge we are checking.
        double xp0 = poly(i, 0);
        double yp0 = poly(i, 1);
        double xp1 = poly(j, 0);
        double yp1 = poly(j, 1);

        // Check whether the edge intersects a line from (-inf,y) to (x,y).

        // First check if the line crosses the horizontal line at y in either direction.
        if ((yp0 <= y) && (yp1 > y) || (yp1 <= y) && (yp0 > y))
        {
            // If so, get the point where it crosses that line. This is a simple solution
            // to a linear equation. Note that we can't get a division by zero here -
            // if yp1 == yp0 then the above if be false.
            double cross = (xp1 - xp0) * (y - yp0) / (yp1 - yp0) + xp0;

            // Finally check if it crosses to the left of our test point. You could equally
            // do right and it should give the same result.
            if (cross < x)
                inside = !inside;
        }
    }
    return inside;
}

---

이 방법은 점 (testx, testy)에서 O (0,0)까지의 광선이 다각형의 측면을 자르는 지 여부를 확인합니다.

여기에 잘 알려진 결론이 있습니다 . 한 지점에서 광선이 비추고 다각형의 측면을 이상한 시간 동안 자르면 해당 지점이 다각형에 속하고 그렇지 않으면 해당 지점이 다각형 외부에 있습니다.

---

기본 아이디어는 다각형의 모서리 당 하나씩 점에서 벡터를 계산하는 것입니다. 벡터가 한 모서리를 가로 지르면 점은 다각형 내에 있습니다. 오목한 다각형을 사용하면 홀수 가장자리를 가로 지르면 내부에 있습니다 (면책 조항 : 모든 오목 다각형에 대해 작동하는지 확실하지 않음).

---

두 번째 줄이 지점이 줄의 왼쪽에 있는지 확인하는 @chowlette의 대답 을 확장하려면 파생이 제공되지 않지만 이것이 제가 해결 한 것입니다. 먼저 두 가지 기본 사례를 상상하는 데 도움이됩니다.

• 점이 선의 왼쪽에 . /있거나
• 포인트는 선의 오른쪽입니다 / .

우리의 요점이 수평으로 광선을 쏘는 것이라면 선분에 닿을 곳입니다. 우리의 포인트는 그것의 왼쪽 또는 오른쪽입니까? 안팎? 정의상 점과 동일하기 때문에 y 좌표를 알고 있습니다. x 좌표는 무엇입니까?

기존의 라인 공식을 사용하십시오 y = mx + b. m은 실행에 대한 상승입니다. 여기에서 대신에 우리는 점과 높이 (y)가 같은 선분에있는 점 의 x 좌표 를 찾으려고합니다 .

그래서 우리는 x : x = (y - b)/m. m실행 이상 상승이 상승을 통해 실행하거나가되도록한다 (yj - yi)/(xj - xi)됩니다 (xj - xi)/(yj - yi). b는 원점으로부터의 오프셋입니다. yi좌표계의 기준으로 가정하면 b는 yi가됩니다. 우리의 요점 testy은 입력이며, 빼면 yi전체 공식이 yi.

이제 (xj - xi)/(yj - yi)또는 1/m시간 y 또는 (testy - yi):가 (xj - xi)(testy - yi)/(yj - yi)있지만 testx는 기반이 yi아니므로 두 값을 비교하기 위해 다시 추가합니다 (또는 testx 0).

---

이것의 PHP 구현은 다음과 같습니다.

<?php
class Point2D {

    public $x;
    public $y;

    function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
    }

    function x() {
        return $this->x;
    }

    function y() {
        return $this->y;
    }

}

class Point {

    protected $vertices;

    function __construct($vertices) {

        $this->vertices = $vertices;
    }

    //Determines if the specified point is within the polygon. 
    function pointInPolygon($point) {
        /* @var $point Point2D */
    $poly_vertices = $this->vertices;
    $num_of_vertices = count($poly_vertices);

    $edge_error = 1.192092896e-07;
    $r = false;

    for ($i = 0, $j = $num_of_vertices - 1; $i < $num_of_vertices; $j = $i++) {
        /* @var $current_vertex_i Point2D */
        /* @var $current_vertex_j Point2D */
        $current_vertex_i = $poly_vertices[$i];
        $current_vertex_j = $poly_vertices[$j];

        if (abs($current_vertex_i->y - $current_vertex_j->y) <= $edge_error && abs($current_vertex_j->y - $point->y) <= $edge_error && ($current_vertex_i->x >= $point->x) != ($current_vertex_j->x >= $point->x)) {
            return true;
        }

        if ($current_vertex_i->y > $point->y != $current_vertex_j->y > $point->y) {
            $c = ($current_vertex_j->x - $current_vertex_i->x) * ($point->y - $current_vertex_i->y) / ($current_vertex_j->y - $current_vertex_i->y) + $current_vertex_i->x;

            if (abs($point->x - $c) <= $edge_error) {
                return true;
            }

            if ($point->x < $c) {
                $r = !$r;
            }
        }
    }

    return $r;
}

테스트 실행 :

        <?php
        $vertices = array();

        array_push($vertices, new Point2D(120, 40));
        array_push($vertices, new Point2D(260, 40));
        array_push($vertices, new Point2D(45, 170));
        array_push($vertices, new Point2D(335, 170));
        array_push($vertices, new Point2D(120, 300));
        array_push($vertices, new Point2D(260, 300));


        $Point = new Point($vertices);
        $point_to_find = new Point2D(190, 170);
        $isPointInPolygon = $Point->pointInPolygon($point_to_find);
        echo $isPointInPolygon;
        var_dump($isPointInPolygon);

---

이것은 내가 사용하는 알고리즘이지만 속도를 높이기 위해 약간의 전처리 속임수를 추가했습니다. 내 다각형에는 ~ 1000 개의 모서리가 있고 변경되지 않지만 마우스를 움직일 때마다 커서가 하나 안에 있는지 확인해야합니다.

기본적으로 경계 사각형의 높이를 동일한 길이 간격으로 분할하고 각 간격에 대해 그 안에 / 교차하는 가장자리 목록을 컴파일합니다.

점을 찾아야 할 때 O (1) 시간에 어떤 간격에 있는지 계산할 수 있으며 간격 목록에있는 가장자리 만 테스트하면됩니다.

I used 256 intervals and this reduced the number of edges I need to test to 2-10 instead of ~1000.

---

I modified the code to check whether the point is in a polygon, including the point is on an edge.

bool point_in_polygon_check_edge(const vec<double, 2>& v, vec<double, 2> polygon[], int point_count, double edge_error = 1.192092896e-07f)
{
    const static int x = 0;
    const static int y = 1;
    int i, j;
    bool r = false;
    for (i = 0, j = point_count - 1; i < point_count; j = i++)
    {
        const vec<double, 2>& pi = polygon[i);
        const vec<double, 2>& pj = polygon[j];
        if (fabs(pi[y] - pj[y]) <= edge_error && fabs(pj[y] - v[y]) <= edge_error && (pi[x] >= v[x]) != (pj[x] >= v[x]))
        {
            return true;
        }

        if ((pi[y] > v[y]) != (pj[y] > v[y]))
        {
            double c = (pj[x] - pi[x]) * (v[y] - pi[y]) / (pj[y] - pi[y]) + pi[x];
            if (fabs(v[x] - c) <= edge_error)
            {
                return true;
            }
            if (v[x] < c)
            {
                r = !r;
            }
        }
    }
    return r;
}

참고URL : https://stackoverflow.com/questions/11716268/point-in-polygon-algorithm