### 'simple polygon'에 해당되는 글 4건

1. 2010.07.03 Finding the Convex Hull of Simple Polygon (2)
2. 2008.05.26 Polygon Triangulation (II)
3. 2008.05.22 Trapezoidalization
4. 2008.05.22 Sweep Line Algorithm

## Finding the Convex Hull of Simple Polygon

2010. 7. 3. 12:34
It is well known that the convex hull of a set of n points in the (Euclidean) plane can be
found by an algorithm having worst-case complexity O(n log n). In this note we give a short linear algorithm for finding the convex hull in the, case that the (ordered) set of points from the vertices of a simple (i.e., non-self-intersecting) polygon.

ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/81/887/CS-TR-81-887.pdf http://deepblue.lib.umich.edu/bitstream/2027.42/7588/5/bam3301.0001.001.pdf

We present space-efficient algorithms for computing the convex hull of a simple polygonal line in-place, in linear time. It turns out that the problem is as hard as stable partition, i.e., if there were a truly simple solution then stable partition would also have a truly simple solution, and vice versa. Nevertheless, we present a simple self-contained solution that uses O(log n) space, and indicate how to improve it to O(1) space with the same techniques used for stable partition. If the points inside the convex hull can be discarded, then there is a truly simple solution that uses a single call to stable partition, and even that call can be spared if only extreme points are desired (and not their order). If the polygonal line is closed, then the problem admits a very simple solution which does not call for stable partitioning at all.

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

 3개의 숫자 중에서 가장 큰 것은  (0) 2012.01.17 2010.11.06 2010.07.03 2010.01.17 2010.01.16 2009.12.19

### 댓글을 달아 주세요

1. 2010.07.06 09:39

비밀댓글입니다

2. 2010.07.15 10:19

비밀댓글입니다

## Polygon Triangulation (II)

2008. 5. 26. 17:53

단순폴리곤의 삼각화 알고리즘의 다른 구현이다. 이전 구현과 같은 Ear-Clipping  알고리즘을 써서 구현한 것이다. 폴리곤의 각 꼭지점을 돌면서 현재 꼭지점의 직전과 직후의 꼭지점들로 만들어지는 삼각형이 Ear인가를 체크해서 Ear이면 삼각형을 하나를 얻고, 현재의 꼭지점은 주어진 폴리곤에서 제거를 한 후에 테스트를 계속 진행한다. nv 개의 꼭지점을 가지는 단순폴리곤의 경우에 nv-2 개의 삼각형으로 분해가 된다.

알고리즘은 주어진 폴리곤이 시계방향인 경우에는 반시계방향으로 수정하여서 작업을 한다. 구현된 알고리즘의 복잡도는 O(N^2)이다.

last update: 2012.10.03;

static bool leftSide(CPoint *P, CPoint *A, CPoint *B) {
static bool insideTriangle (CPoint *P, CPoint *A, CPoint *B, CPoint *C) {
static bool earTest(int a, int b, int c, int nv, int *V, CPoint *points) {
static double polygonArea2(std::vector<CPoint>& pts) {
/* Polygon should be simple(ccw or cw);*;
int polygonTriangulation(std::vector<CPoint>& points, std::vector<Triangle>& triplets) {
int nv = points.size();
if (nv < 3) return 0;
triplets.clear();
triplets.reserve(nv - 2);
std::vector<int> V(nv) ;
// 주어진 단순폴리곤을 반시계방향으로 정렬한다;
if (polygonArea2(points) > 0)
for (int v = 0; v < nv; ++v) V[v] = v;
else
for (int v = 0; v < nv; ++v) V[v] = nv - 1 - v;
// nv-2개의 꼭지점을 차례로 제거한다. 한개의 꼭지점이 제거될때마다 삼각형이 하나씩
// 생긴다;
int err_detect = 2*nv;   /* error detection */
for (int v = nv - 1; nv > 2;  ) {
// 단순폴리곤이 아닌 경우에 무한루프를 도는 것을 방지;
if (0 >= (err_detect--)) {
TRACE("triangulate::ERROR\n");
triplets.clear();
return 0;
}
// <u,v,w>는 연속하는 세꼭지점의 인덱스임;
int u = v % nv;
v = (u + 1) % nv;
int w = (v + 1) % nv;
if (earTest(u, v, w, nv, &V, &points)) {
triplets.push_back(Triangle(points[V[u]], points[V[v]], points[V[w]]));
// 꼭지점 V[v]를 제거함;
for (int k = v; k < nv - 1; ++k)
V[k] = V[k + 1];
--nv;
/* resest error detection counter */
err_detect = 2*nv;
}
}
return triplets.size();
//number of triangle = (nv-2);
} 최적화 후: #### 'Computational Geometry' 카테고리의 다른 글

 삼각형 외접원의 Inclusion Test  (0) 2008.05.29 2008.05.28 2008.05.26 2008.05.25 2008.05.22 2008.05.22

## Trapezoidalization

2008. 5. 22. 14:19

단순 폴리곤을 사다리꼴로 분해하는 알고리즘이다(삼각형은 평행한 변중에 하나가 0인 것으로 취급한다). 이 알고리즘은 복잡한 폴리곤을 한 방향으로 정렬된 보다 단순한 형태로 바꾸어서, 효율적인 알고리즘의 디자인과 적용이 가능하게 한다. 이 역시  sweep-line 알고리즘을 이용한다.

(1) 폴리곤의 꼭지점들을 y-값(or x)값으로 크기순서로 정렬한다.

(2) sweep-line L이 정렬된 각각의 꼭지점을 스캔한다.

(3) 각각의 꼭지점에서 폴리곤 내부에 들어가는 최대의 평행 세그먼트를 계산한다.
(녹색과 붉은색(붉은 색은 꼭지점이 세그먼트 중간에 있는 것을 표시함))

** 알고리즘 복잡도 : O(n log n) 붉은색 세그먼트에 포함된 꼭지점에서 위/아래의 세그먼트의 꼭지점으로 대각선을 그을 수 가 있는데, 이 대각선을 이용하면 폴리곤을 monotonic(y방향)한 분리가 가능하다.

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

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

 Polygon Fill  (0) 2008.05.22 2008.05.22 2008.05.22 2008.05.22 2008.05.22 2008.05.22

## Sweep Line Algorithm

2008. 5. 22. 09:42

(1) closest pair in the planar point set
* brute force : O(n^2) --> O(n log n), see also divide and conquer algorithm.
* ref : http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html (2) simplicity of polygon : Shamos-Hoey Algorithm (3) voronoi diagram :Fortune algorithm (4) segment intersection : Bentley-Ottmann Algorithm
* 파란색 점 : sweep-line과 교차하는 세그먼트들 간의(붉은색으로 표시)의 교차점으로(before sweep-line)로 point 이벤트큐에 들어간다.
* 청록색 점 : sweep-line이 지나간 후의 교차점. ** Degeneracy is the source of all evil!!!
sweep-line알고리즘을 구현하는데서 스텝별로 쪼개서 구현하려고 하니 조금 귀찮은 작업들이 많아진다 (DC에 그려지는것을 자동으로 저장하는 부분을 만들어서 매 스텝마다 캡쳐하는 작업은 줄였다). 그러나 근본적인 문제는 입력되는 데이터에 degeneracy가 있는 경우다. 이것 때문에 가장 기본적인 세그먼트 intersection 부분 부터 다시 살펴보아야 했다.

/**
** http://blog.naver.com/helloktk/80051980882 에서 옮긴 글.
*/

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

 Polygon Fill  (0) 2008.05.22 2008.05.22 2008.05.22 2008.05.22 2008.05.22 2008.05.22