728x90

기하 관련 프로그래밍을 하다 보면 평면 상의 한 점이 다각형 내의 점인가 아니면 밖의 점인가를 판단해야 할 필요성이 많이 생긴다. 이 문제에 대한 답을 생각해보기로 하자. $N$개의 꼭짓점 $\{ x_i, y_i| i=0,...., N-1\}$으로 구성이 된 다각형을 놓고 생각을 하도록 하자. 평면상의 주어진 점 $(x_p, y_p)$에서 오른쪽으로 출발하는 반직선을 쭉 그으면 다각형과 교차하는 점들이 생기게 된다. 교차하는 상황을 잘 헤아려 보면 해당점이 다각형의 내부에 들어 있는 경우에는 항상 홀수번의 교차점이 생기고, 외부에 있는 경우에는 짝수번(0번 포함)의 교차점이 생김을 알 수 있다. 따라서 주어진 점에서 시작하는 반직선과 다각형의 교차점 개수의 홀짝 여부를 판별하면 내부/외부점인지에 대한 문제를 풀 수 있다. 여기서 한 가지 주의할 사항은, 주어짐 점에서 그은 반직선이 다각형의 변(edge)을 포함하는 경우는 제외해야 하고, 꼭짓점이 반직선에 걸리는 경우는 꼭짓점을 공유하는 두 변과 만나지만 한 번으로 카운트해야 한다.

BOOL is_inside_polygon(POINT p, POINT polygon[], int N){
    int counter = 0;
    POINT* q1 = &polygon[0];
    for (int i = 1; i <= N; i++) {
        POINT *q2 = &polygon[i % N];
        if (p.y > min(q1->y, q2->y)) {                                //y-intersect.;
            if (p.y <= max(q1->y, q2->y)){                            //y-intersect(=single);
                if (p.x <= max(q1->x, q2->x)){                        //x-intersect;
                    if (q1->y != q2->y) {                             //not parallel;
                        double xq = (p.y - q1->y) * (q2->x - q1->x) / (q2->y - q1->y) + q1->x;
                        // x-intersect;
                        if (q1->x == q2->x || p.x <= xq)
                            counter++;
                    }
                }
            }
        }
        q1 = q2; // move to next edge;
    }
    if (counter % 2 == 0) return FALSE;
    else return TRUE;
}

네이버 블로그에서 이전

참고: 

1. www.ics.uci.edu/~eppstein/161/960307.html

2.geomalgorithms.com/a03-_inclusion.html

'Computational Geometry' 카테고리의 다른 글

단순 다각형의 면적(2D)  (0) 2021.01.23
삼각형 외접원의 Inclusion Test  (0) 2020.12.30
Point in Polygon  (2) 2020.12.14
Incremental Delaunay Triangulation  (1) 2020.12.01
Chain Hull  (2) 2012.09.16
Quick Hull  (2) 2012.09.16
Posted by helloktk

댓글을 달아 주세요

  1. hgmhc 2020.12.17 18:15 신고  댓글주소  수정/삭제  댓글쓰기

    꼭짓점과 반직선이 만나는 경우에 예외 처리가 제일 짜증나는 부분인 것 같습니다.
    1번으로 따로 카운트하는 방법도 있지만,
    반직선의 기울기를 아주 살짝 위를 향하게 하는 방법도 있다고 합니다!

  2. hgmhc 2020.12.30 15:07 신고  댓글주소  수정/삭제  댓글쓰기

    혹은 모든 점에 대해 ccw를 이용하는 방법도 있다고는 하는데,
    솔직히 아무도 안 쓸 것 같네요

728x90

MFC를 써서 폴리곤의 내부를 칠하기 위해서는 윈도  GDI region을 다루는  CRgn  클래스의 CRgn::CreatePolygonRgn() 메쏘드를 써서 해당 폴리곤으로 bound 된 영역을 만든 이후에 CDC::FillRgn() 함수를 이용하여서 원하는 색으로 칠할 수 있다. 직접  raster에 칠하려고 할 때는 이러한 방법이 너무 불편하다 (물론 라스터(DIB)를 윈도 비트맵으로 변환한 후에 위의 방법대로 칠하고, 다시 윈도 비트맵을 라스터로 바꾸는 작업을 하면 되는데 번거롭다).

쉽게 생각할 수 있는 방법은  point_in_polygon()  방법을 써서 각각의 픽셀이 주어진 폴리곤 내부점인지를 확인하면서 작업을 할 수 있다. 그러나 이 방법은 한 픽셀을 검사하기 위해서 주어진 폴리곤의 모든 에지를 다 건들어야 하는 낭비를 하게 된다. 보다 효율적인 방법은 point_in_polygon 알고리즘을 구현할 때 사용하는 원리를 이용하면 적어도 한 스캔라인의 모든 픽셀에 대해서는 딱 한 번만 전체 폴리곤의 에지를 검사하게 만들 수 있다. inclusion 테스트는 해당점에서 출발하는 수평 반직선이 폴리곤과 몇 번 교차하는지를 세서 내부점인지 외부점인지를 판별한다. 이것을 생각하면 수평선이 폴리곤과 교차하는 점들을 모두 구하여서(한번 폴리곤의 전체 에지 검사가 필요) 크기의 순서대로 정렬할 때, 짝수번째 구간(0->1, 2->3,.....)에 들어가는 스캔라인의 픽셀들은 모두 폴리곤의 내부점이 된다는 것을 알 수 있다.

사용자 삽입 이미지


알고리즘 순서:
(1) 각각의 스캔라인에 대해서 교차점들을 구한다:
       꼭짓점-i와 꼭짓점-j(=i-1)를 잇는 직선의 방정식: x = x[i] + (x[j] - x[i])*(y - y[i]) / (y[j] - y[i]) 이므로
       현재의 scanline 위치에서 y값이 두 꼭지점의 y값 (y[i], y[j]) 사이에 있으면, 교차점의 x-좌표는 윗식의
       좌변 값이 된다.
(2) 교차점들을 크기의 순서대로 정렬한다.

(3) 짝수번째 구간에 들어가는 스캔라인상의 픽셀들은 해당 색깔로 칠한다.


static int comp(const void *a, const void *b);

더보기
// qsort용 비교함수;
static int comp(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
};
/*코드 샘플
** 폴리곤을 플로팅타입으로 변환이 필요?
*/
void FillPolygon(POINT poly[], int npoly,
                 DWORD color,
                 BYTE *image, int width, int height, int bpp) {
    int *nodeX = new int [npoly] ; //never exceeds npoly;
    for (int y = 0; y < height; y++) {
        // find intersection nodes;
        int nodes = 0;
        for (int i = 0, j = npoly - 1; i < npoly; j = i++) {
            if (poly[i].y < y && poly[j].y >= y || poly[j].y < y && poly[i].y >= y) {
                // 수평인 에지는 그리지 않는다(부등식을 자세히 보라)
                nodeX[nodes++] = (int)(poly[i].x + double(y - poly[i].y) * double(poly[j].x \
                                 - poly[i].x) / double(poly[j].y - poly[i].y) + .5); 
                                 // round to integer!!.
            }
        }
        // sort nodes (ascending order);
        qsort(nodeX, nodes, sizeof(int), comp) ;
        // fill the pixels between node pairs.
        for (INT i = 0; i < nodes; i += 2) {
            if (nodeX[i    ] >= width) break;
            if (nodeX[i + 1] > 0) {
                if (nodeX[i    ] < 0)     nodeX[i  ] = 0 ;
                if (nodeX[i + 1] > width) nodeX[i + 1] = width;
                for (int x = nodeX[i]; x < nodeX[i + 1]; x++) 
                    SetPixel(x, y, color, image, width, height, bpp); 
                    //SetPixel()은 다른 프로토타입을 가질 수 있다.
            }
        }
    } 
    delete[] nodeX;
};

사용자 삽입 이미지

/**
** http://blog.naver.com/helloktk/80050645334 에서 옮김.
*/

'Computational Geometry' 카테고리의 다른 글

Polygon Triangulation (II)  (0) 2008.05.26
Polygon Triangulation  (4) 2008.05.25
Polygon Fill  (0) 2008.05.22
Fortune's Sweep Algorithm  (0) 2008.05.22
Triangulating Monotone Polygon  (0) 2008.05.22
Trapezoidalization  (0) 2008.05.22
Posted by helloktk

댓글을 달아 주세요