MFC를 써서 폴리곤의 내부를 칠하기 위해서는 윈도 GDI region을 다루는 CRgn 클래스의 CRgn::CreatePolygonRgn() 메쏘드를 써서 해당 폴리곤으로 bound 된 영역을 만든 이후에 CDC::FillRgn() 함수를 이용하여서 원하는 색으로 칠할 수 있다. 직접 raster에 칠하려고 할 때는 이러한 방법이 너무 불편하다 (물론 라스터(DIB)를 윈도 비트맵으로 변환한 후에 위의 방법대로 칠하고, 다시 윈도 비트맵을 라스터로 바꾸는 작업을 하면 되는데 번거롭다).
쉽게 생각할 수 있는 방법은 point_in_polygon() 방법을 써서 각각의 픽셀이 주어진 폴리곤 내부점인지를 확인하면서 작업을 할 수 있다. 그러나 이 방법은 한 픽셀을 검사하기 위해서 주어진 폴리곤의 모든 에지를 다 건들어야 하는 낭비를 하게 된다. 보다 효율적인 방법은 point_in_polygon 알고리즘을 구현할 때 사용하는 원리를 이용하면 적어도 한 스캔라인의 모든 픽셀에 대해서는 딱 한 번만 전체 폴리곤의 에지를 검사하게 만들 수 있다. inclusion 테스트는 해당점에서 출발하는 수평 반직선이 폴리곤과 몇 번 교차하는지를 세서 내부점인지 외부점인지를 판별한다. 이것을 생각하면 수평선이 폴리곤과 교차하는 점들을 모두 구하여서(한번 폴리곤의 전체 에지 검사가 필요) 크기의 순서대로 정렬할 때, 짝수번째 구간(0->1, 2->3,.....)에 들어가는 스캔라인의 픽셀들은 모두 폴리곤의 내부점이 된다는 것을 알 수 있다.
알고리즘 순서:
각각의 스캔라인에 대해서 교차점들을 구한다: 꼭짓점 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-좌표는 윗식의 좌변 값이 된다.
주어진 영상에서 선분을 찾고자 하면 어떻게 해야 할까. 우선 에지 영상을 만들어 선분을 강조하고, 선분이 하나만 있는 경우에는 에지 데이터를 가지고 line-fitting 알고리즘을 적용해서 해당 선분을 기술하는 파라미터를 추출할 수 있다. 그러나 영상이 선분을 여러 개 포함하는 경우에는 이 방법을 이용하기 어렵다(불가능한 것은 아니지만 노이즈 등에 의한 영향을 고려해야 하므로 복잡한 과정을 거쳐야 한다). 평면에서 선분은 원점까지 거리와 그것의 수직(수평)인 방향만 주어지면 결정이 된다. 직선에서 원점까지 거리를 $r$, 법선이 $x$-축과 이루는 각도가 $θ$면
$$r = \cos(θ) x + \sin(θ) y;$$
의 형태로 주어진다. 즉, $(r,θ)$ 한쌍이 주어지면 직선 한 개가 정의된다 (주어진 $(r,θ)$ 값이 만드는 직선을 $a x + b y = c$ 꼴로 쓰면 계수는 $a = \cos θ$, $b = \sin θ$, $c = r$로 표현된다).
이 직선 방정식은 $rθ$-평면의 stripe=$[0,∞) \times [0,2π]$을 $xy$-평면으로 보내는 변환으로도 생각할 수 있다. 이 변환은 $rθ$-평면의 한 점을 $xy$-평면의 한 직선으로 보낸다. 역으로는 $xy$-평면의 한 점은 $rθ$-평면의 한 곡선으로 변환이 된다. 직선 상의 점들은 같은 원점 거리=$r$, 같은 기울기=$\theta$를 가지므로, 직선 위의 각 점들이 $rθ$-평면에 만드는 곡선들은 공통의 교점을 가지게 된다. 이 교점의 위치가 $xy$-평면에서 직선을 기술하는 파라미터를 준다.
Hough Transform은 이 변환의 특성을 이용한 것이다. 이미지에서 에지에 해당하는 점들을 위의 변환에 의해서 $rθ$-평면의 곡선으로 보내는 것이다 (프로그램적으로는, 에지점 좌표 $(x, y)$가 주어지면 $θ=0 \rightarrow π$까지 일정 간격으로 증가시키면서 곡선 $r=x \cos(θ) + y\sin(θ)$의 값을 구해서 메모리 상의 $[r,θ]$ 지점의 도수를 1씩 증가시킨다). 만약 에지에 해당되는 점들이 직선의 관계를 가지게 되면, 각 점들에 해당하는 $rθ$-평면에서 곡선들은 한 교점을 형성하게 될 것이다. 긴 선분은 $rθ$-평면의 한 점에서 더 많은 곡선들의 교점을 형성하게 된다. 따라서, $rθ$-평면에서 이러한 교점의 히스토그램을 구하여, 교점 수가 일정 이상 누적이 된 경우를 취하면, $xy$-이미지 평면에서 일정한 길이 이상을 갖는 선분을 골라낼 수 있다.
그러면 왜 $rθ$-평면으로 변환을 생각하는 것일까? 직선이 $y= a x+b$의 형태로 표시되므로 기울기와 $y$축과의 교점을 기술하는 $ab$-공간을 이용할 수도 있지만, 이 경우에 $y$-축에 평행인 직선의 경우에 기울기 $a$ 값이 무한히 커지는 경우가 발생하여 저장공간 할당에 문제가 생긴다. 실제적인 문제에서 되도록이면 compact 한 공간으로 변환을 고려해야 하는 것이다. $rθ$-공간으로의 변환은 유한한 이미지의 경우 항상 유한한 $rθ$-공간의 영역으로 변환된다.
아래의 그림은 $x-y=-5$인 직선상의 세 점 $(5,10)$, $(10,15)$, $(15,20)$에 해당하는 $rθ$-평면상의 세 곡선을 보인 것이다: $r = 5 \cos(θ) + 10\sin(θ)$, $r = 10 \cos(θ) + 15 \sin(θ)$, $r = 15 \cos(θ) + 20 \sin(θ)$. 이 세 곡선은 $(r,θ) = (5/\sqrt{2}, 3 \pi /4)$ 지점에서 만남을 알 수 있다. 이 만나는 지점을 구하면, 거꾸로 세 점이 $x-y=-5$ 인 직선 위의 점들이었다는 것을 추정할 수 있다.
BOOL HoughTransformLine(BYTE* image, int width, int height, /*background=0*/
double rho/*=2*/,
double theta/*=Pi/180.*/,
int threshold/*=20*/,
std::vector<Line>& vecLine) {
/* use cosine and sine look-up tables*/
double irho = 1 / rho;
int numangle = (int) (Pi / theta);
int numrho = (int) (((width + height) * 2 + 1) / rho);
int *accum = (int*)malloc( sizeof(accum[0]) * (numangle + 2) * (numrho + 2) );
memset( accum, 0, sizeof(accum[0]) * (numangle + 2) * (numrho + 2) );
double ang;
int n, rwidth = (numrho + 2);
for (int y = 0; y < height; y++ ){
for (int x = 0; x < width; x++ ){
if ( image[y * width + x] != 0 ){ // only for foreground pixels;
for (ang = 0, n = 0; n < numangle; ang += theta, n++ ) {
double rho = (x * cos(ang) + y * sin(ang)) * irho ;
int r = rho >= 0 ? int(rho + .5) : (-int(-rho + .5));//round to nearest int;
// accum을 이차원배열로 생각하고, 1 픽셀의 border를 두는 형태로 한다.
// 이는 아래의 local-maxima를 찾을때 경계를 고려할 필요가 없어서 유리하다.
r += (numrho - 1) / 2;
accum[(n + 1) * rwidth + r + 1]++;
}
}
}
}
//find local maxima;
for (int r = 0; r < numrho; r++ ) {
for (int n = 0; n < numangle; n++ ) {
int base = (n + 1) * rwidth + r + 1;
//test whether it is local-maximum(4-way);
if ( accum[base] > threshold &&
accum[base] > accum[base - 1] && accum[base] > accum[base + 1] &&
accum[base] > accum[base - rwidth] && accum[base] > accum[base + rwidth] )
{
Line line;
line.rho = (r - (numrho - 1) * .5) * rho;
line.angle = n * theta;
vecLine.push_back( line );
}
}
}
free(accum);
return TRUE;
}
아래 그림에서 첫 번째는 소스 이미지이고, 이 이미지에서 $rθ$-평면으로 Hough Transform 한 것이 두 번째 것이다(rho=2, theta=Pi/360). 원본 이미지에는 8개의 선분이 있고, 4 개씩 같은 방향을 갖고 있다. Hough Transform 된 이미지에서 이러한 특징을 볼 수 있다(가로축이 $θ$이고 세로축이 $r$이다. $r$ 축은 가운데가 $r=0$이다). 누적이 많이 된 부분이 두 군데의 동일한 θ에서 나타나고 있다. 그러나 결과에서 8개의 피크를 분리하기는 쉽지 않다. 위의 코드는 각각의 점에서 4방향으로 체크하여 극대 값을 찾고 있으나, 항상 잘 동작하는 것은 아니다.
local-maxima를 좀 더 잘 잡고 싶으면, 위처럼 주변의 4점만 체크할 것이 아니라, 윈도를 좀 더 크게 잡고, 그 윈도 내에서 최댓값을 찾아보는 것도 한 방법이 된다.
평면에서 보로노이 다이어그램을 계산하는 알고리즘 중에 1980년대에 Fortune에 의해서 발견이 된 Sweep line 알고리즘에 대해서 살펴보겠다. 이 알고리즘은 보로노이 다이어그램 계산문제의 optimal 한 답 중에 하나이다(~O(n * log(n)). Fortune이 자신의 알고리즘을 직접 C로 구현한 것이 있는데 이것은 웹상에서 쉽게 구할 수 있다. 그러나 알고리즘의 얼개는 간단하나 구현에 들어간 자료구조 등을 간단히 않아서 코드를 이해하는 것이 쉽지 않았다(이에 비하면 incremental delaunay triangulation은 매우 단순하다). 몇 번을 간단한 자료구조를 이용해서 재 작성을 해보려고 했는데 잘 되지 않았다. 인터넷에서 구할 수 있는 다양한 구현 소스를 분석해 보았으나 쉬운 것을 찾기가 힘들었다(triangle.c에서도 구현되어 있고, 자바로도 구현이 된 것을 찾을 수 있다.) 원래의 목적은 Fortune의 코드가 메모리 처리를 잘못하여 메모리 leak이 발생하여서 이 문제를 해결하려고 시도한 것인데, 메모리 문제는 자바의 경우에 처럼 가비지 콜렉터를 만들어서 처리할 수는 있다. 이 알고리즘의 구현에 들어가는 기본적인 자료구조는 priority queue와 balanced binary tree이다. 이들의 기본적인 구현은 이미 잘 알려져 있으므로 이것들을 직접적으로 알고리즘에 적용하는 문제만 남는다. balanced binary tree로 만들어진 자료구조를 쓰면 자료를 찾는 시간이 O(log(n))의 시간 복잡도를 주지만, 이것이 알고리즘을 직관적으로 보는 것을 방해하므로 여기서는 이중 연결 리스트를 이용하도록 한다. 전체적으로 알고리즘은 O(n^2)의 복잡도를 가진다.
1. priority queue 구성: 주어진 입력점들을 가지고 구성한다. 알고리즘 중간에 세 점으로 원이 구성이 되는 circle event가 생성이 되는데 이것은 따로 event 큐를 구성한다. event의 우선순위는 x 좌표의 순서에 의해서 구성하고 동일한 x 좌표값에 대해서는 y값이 작은 순서대로 구성한다(compare 구조체에서 point와 event에 대한 비교 연산자를 정의한다).
2. site event 처리: sweep line(x=const)은 전체 평면을 반으로 나누는 역할을 한다. 알고리즘은 sweep 라인이 쓸고 지나간 영역에서만 관심 영역이다. sweep라인과 주어진 점은 하나의 포물선을 정의할 수 있다(주어짐 점이 포물선의 초점을 구성함). 따라서 sweep 라인이 진행하면 sweep line의 왼편의 입력점들은 각각 하나의 포물선을 형성하고, 이 포물선들의 구간 중에서 sweep라인에 가장 가까운 부분은 포물선 arc로 연결인 되는 하나의 beach line을 형성한다. sweep라인이 새로운 입력점을 지나면 여기서 새로운 포물선 arc가 생기는데, 이것은 이미 만들어진 beach라인을 구성하는 포물선 arc 중 하나를 둘로 가르고, 그 자신이 새로운 beach 라인의 일부를 구성하게 된다; sweep라인이 전진하면서 비치라인을 구성하는 arc가 다른 arc에 파 묻혀서 없어지는 경우가 생긴다. 이 경우가 circle event가 만들어지는 시점이다.
.......................
* BEFORE AFTER * * new point new arc * | | * __ | _____ __ | _____ * \ \|/ | \ \|/ arc a * \ ` | \ ` __|__ * \ X | p------X __|__<-- arc c * a | arc a a | | * / | / arc a * / | / | * /__ __|__ /__ __|__ * __/ \ | __/ \ | * \ | \ | * \ | \ | * b | arc b b | arc b * / | / | * / | / | * __/ __|__ __/ __|__
3. circle event 처리; sweep라인이 각각의 site에 도달하면 새로운 포물선의 arc가 비치라인에 추가가 되는데 sweep 라인으로부터 멀어진 arc들은 어느 시점에서 없어져야 한다. 이것은 인접하는 세 개의 arc들의 교점이 현재의 sweepline 위치에서 하나로 만들어져서 중앙의 arc가 없어지는 경우로 이것을 circle event라고 한다. 이때 만들어지는 교점은 보로노이 에지의 꼭짓점을 구성하게 된다. circle event에서는 나머지 두 개의 남은 arc의 교점이 trace 하는 새로운 에지가 생기게 된다.
* __ * \ * a \ * \ * __ | * ` / * \ / * b X <-- Arc b is overtaken at point X (this is a circle center) * / \ * __, \ * \ * \ * c | * / * / * /
* * BEFORE AFTER * * \ arc a \ * \ \ a.s0 * \ <-- a.s0 \ | * \ \ \|/ * \ \ ` * \ \ * arc b X <-- termination point .--------------------<-- new segment * / / * / / . * / <-- c.s1 / /|\ * / / | * / arc c / c.s1 * /
//포물선 arc를 정의하기 위한 클래스;
struct arc {
point p; //focus of parabola;
arc *prev, *next; //double linked-list;
event *e;
////////////////////////////////////////////////////
seg *s0 ; //edge of voronoi starting from break point;
seg *s1; //edge of voronoi starting from break point;
arc(point _p, arc *_a=0, arc *_b=0)
: p(_p), prev(_a), next(_b), e(0), s0(0), s1(0) {}
};
// voronoi edge를 정의하는 segment class;
struct seg {
point start, end; //defines segment;
bool done;
int ref ; //referece count in order to distingush the double edges;
seg(point _p, int _ref=0)
: start(_p), end(0,0), done(false), ref(_ref)
{ output.push_back(this); } //garbage collector;
void finish(point p) { if (done) return; end = p; done = true; }
};
//메인 wrapper;
int fortune_main(std::vector<POINT>& pts, //voronoi points;
std::vector<EDGE>& edges) //voronoi edges;
{
//point priority_queue구성;
std::vector<POINT>::iterator iter=pts.begin();
for(; iter !=pts.end(); iter++) {
point P(iter->x, iter->y) ;
points.push_back(P);
}
//body of algorithm ;
while(!points.empty()) {
if(!events.empty() && events.top()->x <= points.top().x)
process_event() ; //circle event ;
else
process_site() ; //site event;
}
//for remaining circle events if any;
while(!events.empty())
process_event() ;
//2. prepare output edges and clean memory;
}
arc * root=NULL; //global variable;
void process_site() {
point P= points.top(); points.pop(); //because popping return void in STL;
if(!root) { // root of double linked list for arcs(global);
root = new arc(P) ; return ;
}
//
for(arc* a = root; a; a=a->next) {
point Q;
if(intersect(P, a, &Q)) { //arc a와 점P에서의 포물선(degenerate 된)이 만나는 점 Q;
duplicate_arc(P, a) ; //교차하는 arc를 둘로 만든다
//(다음 arc가 있고, 만약에 이것과도 교차하면 circle event 임으로 제외)
insert_new_arc(P, a, a->next) ;//새 arc를 중간에 삽입한다;
//새 arc의 에지 세팅 ::교차점을 출발점으로 하는 두개의 반직선을 만든다:
//도착점은 circle event에 대부분 결정되고, 나머지는 후처리 과정에서 결정됨)
a = a->next ;
a->prev->s1 =a->s0 = new seg(Q, ref_count) ;
a->next->s0 =a->s1 = new seg(Q, ref_count++) ; //쌍으로 생성되는 반직선을 identify하기
//위해서 동일번호를 부여함.
//새 site 추가로 비치라인을 구성하는 arc의 초점들과 circle event를 만들 수 있는가 체크함;
check_circle_event(a, P.x) ;
check_circle_event(a->prev, P.x) ;
check_circle_event(a->next, P.x) ;
}
}//for-;
};
//
void process_event(){
event *e = events.top(); events.pop();
if (e->valid) {
// start a new edge.(single edges)
seg *s = new seg(e->p, ref_count++);
// remove the associated arc from the front. and attach a new segment;
arc *a = e->a;
remove_arc(a, s);
// finish the edges before and after a==>new voronoi vertex;
if (a->s0) a->s0->finish(e->p);
if (a->s1) a->s1->finish(e->p);
// recheck circle events on either side of p:
if (a->prev) check_circle_event(a->prev, e->x);
if (a->next) check_circle_event(a->next, e->x);
delete a;
}
delete e;
};
// Look for a new circle event for arc a.
void check_circle_event(arc *a, double x0/*=current sweep-line*/) {
// Invalidate any old event.
if (a->e && a->e->x != x0) a->e->valid = false;
a->e = NULL;
if (!a->prev || !a->next) return;
double maxx;
point O;
point& A = a->prev->p ;
point& B = a->p ;
point& C = a->next->p ;
//collinear가 아니고, 최대값이 현재의 site event위치보다도 큰 경우에;
if (circle(A, B, C, &maxx, &O) && maxx > x0) { //점 A,B,C에 의해서 형성이 되는
//원 중심(O)과 최우측x(maxx) 좌표를 얻음;
// create new event.
a->e = new event(maxx, O, a);
events.push(a->e);
}
};
나머지 함수들은 모두 단순한 구현이므로 생략한다;
보로노이 에지는 seg collector에서 각각의 segment를 끄집어내어서 그리면 된다. 그러나 각각의 segment는 보로노이 에지를 전체를 커버하는 것이 아니다. site event인 경우에는 항상 듀얼로 반직선을 생성하는데. 이 두 개의 반직선이 하나의 보로노이 에지를 정의한다(따라서 ref를 참조하면 온전한 하나의 에지를 찾을 수 있다). circle event의 경우에는 에지가 듀얼로 생성하지 않았으므로 이 경우에는 하나의 segment가 그 에지를 표현한다. 에지 액세스를 쉽게 하기 위해서는 모든 에지를 듀얼 구조로 만들어서 사용할 수 있다.
n 개의 점들의 보로노이 다이어그램은 얼마나 많은 꼭짓점과 에지를 가질까?
이것은 오일러 공식 V-E+F=2를 사용하면 된다. 보로노이 다이어그램은 경우 바깥쪽의 에지들은 무한대로 연결이 되어 있다. 이것을 무한대에서 가상의 꼭짓점을 가정하고 그것에 연결이 되어 있다고 생각하면 된다. 따라서 V --> V+1로 계산을 해야 한다. 오일러 공식 : V+1-E + F= 2; 여기서 F=n임을 알 수 있다. (n개의 점들이 하나의 face상에 놓여 있음)그리고 하나의 에지가 두 개의 꼭짓점을 연결하므로 각각의 꼭짓점에서 나간 에지의 합(=deg(v))을 계산하면 2*E 개 임을 알 수 있다. sum deg(v) = 2 * E;그런데 각각의 꼭짓점에서는 적어도 3개 이상의 에지와 연결이 되어 있으므로 위식의 좌변은 (V+1) * 3 <= 2 * E;를 준다. 따라서 오일러 공식과 이 부등식을 연관시키면 V <= 2*n - 5; E <= 3*n - 6;임을 알 수 있다. 즉 필요한 메모리의 양은 입력점의 수의 선형적으로 비례한다.
따라서 전체 이벤트의 개수는 site 이벤트와 꼭짓점에 해당하는 circle event 만큼이 있으므로 O(3*n) 정도이다. 각각의 event에 대해서 arc노드를 검색해야 하므로 O(n) 번 탐색을 해야 한다(balanced binary tree의 경우에는 log(n)). 따라서 알고리즘의 복잡도는 O(n^2 ( n*log(n))이다./**** http://blog.naver.com/helloktk/80041603288*/
** 첨부된 실행파일로 알고리즘을 테스트해 볼 수 있다(중복된 입력점은 제거하였고, 세 점이 일직선상에 놓인 것을 방지하기 위해서 작은 랜덤 값을 첨가하였다)
monotone 폴리곤은 한 축 방향으로 꼭짓점의 좌표값이 단조 증가하는 형태를 갖는 단순 폴리곤이다. 단순 폴리곤을 monotone 폴리곤으로 분할하는 방법은 잘 알려져 있고 O(n log n)의 복잡도를 갖는다. monotone 폴리곤은 한 방향에 대해서 이미 정렬이 되어 있기 때문이 그 방향으로 sweep-line 기법을 쓰면 선형 시간 내에 triangulation이 가능하다. 이러한 알고리즘은 이미지 처리에 적용하면 매우 효율적으로 이용이 가능하다. raster 상의 데이터는 scanline 방향으로 항상 정렬이 되어 있기 때문이다.
Algorithm Monotone_Triangulation
Input: Monotone polygon P (ccw-ness needed!)
Output: Set of triangles
(1) 주어진 폴리곤의 꼭지점을 x-좌표를 기준으로 정렬하여 V에 저장 (O(n) due to monotonicity).
(2) sweep-line 리스트(L)을 초기화 :: V의 처음 두 포인트(이벤트)를 넣음.
(3) while(V is not empty) do
get next vertex (p) from V ;
if (p is opposite to points in L) then
while(size(L)>1) do
out triangle { first(L), second(L), p }
remove(first(L))
end while
add p to L;
else
while ( size(L)>1 && ccw(last(L), previous(last(L)), p)) do
out triangle { last(L), previous(last(L)), p }
remove(last(L))
end while
add p to L
end if
end while/*입력이 ccw이면 ccw-test도 ccw로, cw면 test도 cw로 해야한다.*/
/* 구현 코드(C++)의 일부이다.*/
struct endpoint {
int vid; /* polygon vertex id */
double* x; /* X coordinate of the endpoint */
double* y; /* Y coordinate of the endpoint */
} ;
//x-크기순서대로--> y-크기순 서대로; (ascending-order);
static
int point_compare(double* x1, double* y1, double* x2, double* y2) {
if (*x1 > *x2) return 1;
if (*x1 < *x2) return -1;
if (*y1 > *y2) return 1;
if (*y1 < *y2) return -1;
return 0;
}
//qsort에서 사용;
static
int endpoint_compare(const void* p1, const void* p2) {
endpoint* e1 = *(endpoint**) p1;
endpoint* e2 = *(endpoint**) p2;
return point_compare(e1->x, e1->y, e2->x, e2->y);
}
//
class endpointqueue {
int n; /* total number of endpoints */
int next; /* index of next endpoint on queue */
endpoint* data; /* array of all endpoints */
endpoint** sorted; /* sorted list of endpoint pointers */
bool create(int npoly, double polyx[], double polyy[]);
public:
~endpointqueue() {
if(data) delete[] data ;
if(sorted) delete[] sorted;
}
endpointqueue() : data(NULL), sorted(NULL), n(0), next(0) {}
endpointqueue(int npoly, double polyx[], double polyy[]) {
create(npoly, polyx, polyy);
} ;
endpoint * getnext() { return (next >= n) ? NULL : sorted[next++];}
} ;
bool endpointqueue::create(int n, double polyx[], double polyy[]) {
data = new endpoint [n] ;
this->n = n ;
this->next = 0;
for (int i = 0; i < n; i++) {
data[i].x = &polyx[i] ;
data[i].y = &polyy[i] ;
data[i].vid = i;
};
sorted = new endpoint* [n] ;
for (i = 0; i < n; i++) {
sorted[i] = &data[i];
};
//non-optimal sorting; use monotonicity of input;
qsort(sorted, n, sizeof(endpoint*), endpoint_compare);
return true ;
}
//deque의 행동을 재정의할 필요가 있음.
struct sweepline {
int n; /* number of vertices in polygon */
endpoint* deque;
int bot, top;
sweepline() : n(0), deque(NULL) {}
sweepline(int n_) {
n = n_; bot = -1; top = -1;
deque = new endpoint [n] ;
}
~sweepline(){ if(deque) delete [] deque;}
endpoint* add(endpoint* e) ;
void removefirst() { if (bot < top) bot++;} //safe::size()>1
void removelast() { if (top > bot) top--;} //safe::size()>1;
int size() { if (top >= 0 && bot >= 0 && top >= bot) return top - bot + 1; else return 0;}
endpoint* getlast() { ASSERT(size() > 0); return &deque[top];}
endpoint* getprelast() { ASSERT(size() > 1); return &deque[top - 1];}
endpoint* getfirst() { ASSERT(size() > 0); return &deque[bot ];}
endpoint* getsecond() { ASSERT(size() > 1); return &deque[bot + 1];}
bool opposite(endpoint* e) ;
void draw(CDC *pDC, DWORD color = RGB(0xFF, 0, 0)) ;
};
endpoint* sweepline::add(endpoint* e) {
if (bot == -1 && top == -1) //first adding;
bot = 0;
top++;
deque[top].x = e->x ;
deque[top].y = e->y ;
deque[top].vid = e->vid ;
return &deque[top];
}
bool sweepline::opposite(endpoint* e) {
if (e->vid == ((deque[top].vid + 1) % this->n))
return false;
else
return true ;
}
void monotone_triangulate(CPoint P[], int n,
void (*print_triangle)(int a, int b, int c)) {
double *polyx = new double [n] ;
double *polyy = new double [n] ;
for (int i = 0; i < n; i++) {
polyx[i] = P[i].x;
polyy[i] = P[i].y;
};
//
endpointqueue eq(n, polyx, polyy);
sweepline sl(n);
endpoint *e ;
sl.add(eq.getnext());
sl.add(eq.getnext());
while ((e = eq.getnext())) {
TRACE("event=%d(x=%5.0f, y=%5.0f)\n", e->vid, *e->x, *e->y);
if (sl.opposite(e)) {
while (sl.size() > 1) {
//(first, second, p);
print_triangle(sl.getfirst()->vid, sl.getsecond()->vid, e->vid);
sl.removefirst();
}
sl.add(e);
} else {
while (sl.size() > 1 && isccw(sl.getlast(), sl.getprelast(), e)) {
//triangle(last, previous(last), p);
print_triangle(sl.getlast()->vid, sl.getprelast()->vid, e->vid);
sl.removelast();
}
sl.add(e);
}
}
//
delete [] polyx;
delete [] polyy;
};
단순 폴리곤을 사다리꼴로 분해하는 알고리즘이다(삼각형은 평행한 변 중에 하나의 길이가 0인 것으로 취급한다). 이 알고리즘은 복잡한 폴리곤을 한 방향으로 정렬된 보다 단순한 형태로 바꾸어, 효율적인 알고리즘의 디자인과 적용이 가능하게 한다. 이 역시 sweep-line 알고리즘을 이용한다.
(1) 폴리곤의 꼭짓점들을 y-값(or x) 값으로 크기순 서로 정렬한다.
(2) sweep-line L이 정렬된 각각의 꼭짓점을 스캔한다.
(3) 각각의 꼭짓점에서 폴리곤 내부에 들어가는 최대의 평행 세그먼트를 계산한다. (녹색과 붉은색(붉은 색은 꼭짓점이 세그먼트 중간에 있는 것을 표시함))
