본문 바로가기

Function

폴리곤을 삼각형 격자로 분할하기

 

 

위와 같은 연두색 폴리곤 하나를 아래와 같은 폴리곤들로 분할해 주는 방법에 대해 개략적으로 설명해보겠다.

 

폴리곤의 분할 기준은 크기가 입력된 정사각형 격자를 대각선으로 가르는 직각삼각형들이다. 직각삼각형 하나가 폴리곤 안에 온전히 포함된다면 그대로 온전히 포함되고, 직각삼각형 하나가 폴리곤의 경계와 만난다면 만나는 부분들의 계산해서 부정형의 도형을 만들어준다.

 

구멍(hole)이 있는 폴리곤도 문제없이 분할해준다. 단, 여러개의 독립된 도형으로 이루어지는 MultiPolygon 은 Polygon 단위로 나누어 함수에 넣어야 한다.

 

이러한 작업은 Qgis에서 폴리곤과 삼각형 그리드를 미리 만들어놓고, intersect 기능을 이용해서 만들어낼 수 있다. 다만, 그리드 분할에 최적화된 함수가 아니기 때문에 대량의 작업을 할 때 속도가 빠르지 않다.

 

아래 깃허브에 cpp 로 작성된 코드가 있다. test.cpp에 사용 예시를 넣어놓았다.

 

GitHub - vuski/tessPolyGRAT: Tessellating the Polygon into a Grid of Right-Angled Triangles

Tessellating the Polygon into a Grid of Right-Angled Triangles - GitHub - vuski/tessPolyGRAT: Tessellating the Polygon into a Grid of Right-Angled Triangles

github.com

 

쓰임새

 

우선 이 함수는 아래 그림처럼 삼각형 격자로 된 지형과 도로가 입체적으로 불일치하는 문제를 해결하기 위해 만들었다.

도로를 지형 격자에 맞춰 분할한 후 각 정점에 지형과 일치하는 높이 값을 주면, 아래 그림처럼 지형의 경사면에 가지런히 align 시킬 수 있다.

 

그 밖에도 그리드의 크기를 1km, 2km 정도로 키우면 벡터 타일맵을 만드는데 사용할 수 있다. 공간적으로 연속된 도형들을 그리드에 맞춰 잘라주기 때문이다.

 

좀 더 부수적인 작업을 추가한다면, 부정형의 행정구역에 할당된 값을 규칙적인 격자로 면적 비례 배분하는데 사용할 수도 있다. 기존의 부정형 도형을 격자로 분할하므로, 분할된 격자 만큼의 면적 비율을 계산할 수 있기 때문이다. 

 

 

 

함수 내부의 작업 절차

 

 

tessellatePolygon 함수는 아래와 같은 절차로 진행된다.

 

다시 차례차례 설명해보겠다.

 

 

1.

(구멍이 포함된) 폴리곤 하나 입력

현재 함수는 geojson 기준으로 Polygon 형식만 입력되므로 MultiPolygon 형식의 도형은 Polygon 으로 분할한 후 입력해야 한다.

 

 

2.

폴리곤 표준화

작업 도중에 도형이 CCW(Counter ClockWise) 여부를 이용하게 된다. 그러므로 표준 형식에 맞게 바깥 폴리곤은 CCW로, 안쪽 구멍은 CW로 정리한다.

 

 

3.

폴리곤의 선분들을 순회하면서 그리드와 교차점에 점 추가(선분 분절)

폴리곤의 선분들 하나씩 순회하면서 그리드와 교차하는 부분에 정점을 추가하고 선분을 분절해준다. 이 부분의 함수만 떼어내면 LineString 형식의 도형들을 그리드에 맞춰 분절하는 함수를 작성할 수 있다.

 

입력된 회색  도형은 최초에 검은색 정점만 가지고 있다. 여기에 위의 작업을 통해 빨간 점들을 추가하고, 마지막으로 그리드의 정점인 보라색 점도 추가해준다.

 

 

4. 

폴리곤 이중 배열을 vertex 연속과  indirect(first, count)로 변환. 이 때 겉 테두리와 hole의 구분이 무의미해진다.

작업의 효율을 위해 테두리와 구멍의 이중 배열 자료 형식을 연속된 vertex의 vector와 그 vector에서 어디부터 어디까지가 하나의 도형 테두리인지 기록하는 별도의 간접배열로 재구성해준다. 0번 배열은 테두리 도형이 되고, 1번부터는 구멍이 된다.

 

 

 

5.

분절된 선분들을 순회하면서 각각의 그리드에 귀속시킨다. , 그리드별 map에 선분을 배분한다.

도형들은 이제 그리드 단위로 작업할 것이므로 분절된 선분들을 그리드별로 귀속시켜준다. unordered_map 자료구조의 key 값은 그리드 번호를 적당히 인코딩해서 uint32_t 형식으로 만들어주고, value에 선분 배열을 넣어준다. 

작업의 성능을 위해 vertex를 바로 취급하지 않고 index로 관리한다. vertex가 중복되는 경우가 많기 때문이다.

동시에, 각 분할된 선분의 첫점과 끝점(그리드와 교차하는 점), 지금 해당 선분이 CW인지 CCW인지 등 부가적인 정보들을 같이 기록해둔다.

 

 

 

6.

이제 각각의 그리드들에서 도형의 선분과 그리드의 선분들을 바탕으로 폴리곤을 재구성한다.

위와 같이 하나의 그리드 안에 귀속된 도형과 그리드 테두리등의 연속 여부를 탐지해가며 반시계 방향으로 순회하고 인덱스들을 이어서 하나의 도형으로 구성해준다.

 

 

7.

포함 관계에 있는 폴리곤이 2개 이상 있다면, 폴리곤 간의 포함 관계를 판별해가며 구멍을 등록한다.

한 그리드 안의 도형 구성이 끝났으면, 하나의 도형이 다른 도형을 포함하고 있는지 판별한다. 포함하고 있을 경우 구멍으로 등록해준다.

 

8. 

다수의 그리드를 지나가는 폴리곤일 경우, 선분이 지나가지 않는 폴리곤 내부의 그리드들에 삼각형을 발생시켜서 채운다.

이제까지의 알고리즘은 도형의 경계선이 만나는 부분에 대해서만 폴리곤을 만들어주었다. 그러므로 이제 도형 내부에 이미 포함되어 있는 온전한 직각삼각형들을 채워준다. 물론 최초 폴리곤이 작을 경우 해당되는 직각삼각형들이 없을 수도 있다.

 

여기까지의 절차를 거치면 아래와 같은 도형이 만들어진다.

 

 

도형은 vertex와 index 형식으로 만들어진다.

OpenGL이나 Vulkan 등, GPU를 이용한 그래픽에서 흔히 사용하는 방식이다.

 

물론, 지금까지의 단계에서는 삼각형 그리드로 분할해 주기만 했으므로 삼각형 이상의 정점을 가진 폴리곤들도 포함되어 있다. 따라서 mapbox::earcut 등의 라이브러리를 통해 triangulation 해 주어야 GPU 기반 indexed drawing에 이용할 수 있다.

 

 

아래 깃허브에 cpp 로 작성된 코드가 있다. test.cpp에 사용 예시를 넣어놓았다.

 

GitHub - vuski/tessPolyGRAT: Tessellating the Polygon into a Grid of Right-Angled Triangles

Tessellating the Polygon into a Grid of Right-Angled Triangles - GitHub - vuski/tessPolyGRAT: Tessellating the Polygon into a Grid of Right-Angled Triangles

github.com