Geometry의 공간연산

얼마전에 했던 작업이 공간연산이였는데, 쉽게 알고만 있었고 쉽게 사용해 왔던 공간연산이 직접 하나 하나 정확하게 구분하려고 보니, 상당이 헤깔린다는 것을 알게 되었다. 또한 공간연산하면 단지 교차하는지, 포함하는지와 같은 공간관계 연산만이 아니라 공간분석 연산도 포함되다는 사실을 알게 되어 정리하는 차원에서 글을 남긴다. 또한 작업했던 것에 대한 Test 실행파일을 올리니 여러분도 한번 실행해 시험해 보길 바란다. 참고로 공간분석 연산의 경우 결과가 Multi-Polygon인 경우 자랑스런 Memory 충돌에러가 발생한다는 점에 주의하기 바란다.

Geometry의 Spatial Relations

GIS에서 Geometry는 단순하게 Point, Polyline, Polygon으로 구분되며, 몇가지 제약사항을 갖게 되는데 이러한 Geometry를 Simple Feature라고 한다. 이러한 Simple Feature 둘 이상이 공간상에서 관계를 갖게 되는데, Spatial Relation이라고 한다. Spatial Relation의 종류는 모두 8가지 이다.

  • Equals – 두개의 Geometry가 동일한가?
  • Disjoint – 두개의 Geometry가 서로 격리되었는가?
  • Intersects – 두개의 Geometry가 교차하는가?
  • Touches – 두개의 Geometry가 접촉하는가?
  • Crosses – 두개의 Geometry가 횡단하는가?
  • Within – 하나의 Geometry가 다른 하나에 포함되는가?
  • Contains – 하나의 Geometry가 다른 하나를 포함하는가?
  • Overlaps –  – 두개의 Geometry가 부분적으로 겹치는가?

8가지의 관계들 중에는 서로 비슷한 연산이 있지만, 분명한 차이점을 가지고 있다. 예들 들어 두개의 폴리곤이 touch 관계을 갖는다면, intersect 관계도 항상 갖는다. 하지만 반대로 intersect 관계을 갖는다고 해서 touch 관계을 갖지는 않는다. 다른 예로 overlap과 intersect 연산의 경우, overlap이 참인 경우 항상 intersect도 참이지만, 반대로 intersect이 참이라고 해서 항상 overlap이 참이지는 않다. 하나의 폴리곤이 다른 하나의 폴리곤안에 완전이 포함되는 경우 intersect이 참이지만 overlap은 참이 아니기 때문이며, 이러한 경우는 contain이 참이거나 within이 참이기 때문이다. 여기서 contain과 within은 능동이냐, 수동이냐의 의미를 갖는다.



일단은 폴리곤에 대한 예를 들었지만 서로 다른 형태의 폴리곤과 폴리라인과의 관계를 생각하면 8가지의 관계의 필요성과 이해가 더욱 피부에 와닿을 것이다. 즉, crosses의 경우에는 폴리곤과 폴리라인의 경우에만 연산의 의미가 있다.

Geometry의 Spatial Analysis

GIS에서 Geometry의 Spatial Analysis는 모두 6가지이며 다음과 같다.

  • Buffer – 일정한 값만큼 Geometry를 키우거나 축소시킨 폴리곤을 얻는다.
  • Convex Hull – Geometry를 감싸는 최소넓이의 볼록한 폴리곤을 얻는다.
  • Intersection – 두개의 Geometry가 교차하는 부분에 대한 Geometry를 얻는다.
  • Union – 두개의 Geometry의 합쳐쳐 만들어진 하나의 Geometry를 얻는다.
  • Difference – 하나의 Geometry에서 다른 하나의 Geometry의 부분을 빼고 남은 Geometry를 얻는다.
  • Symmetric Difference – Union으로 구한 Geometry와 Intersection으로 구한 Geometry의 Difference이다.

위의 화면은 Test의 실행 화면인데, Union 연산, 20 Pixel 확장 Buffering 연산, Difference 연산에 대한 결과이다.

폴리곤에 대한 삼각형 Mesh 생성(Triangulation)

2D GIS 데이터인 벡터 데이터(Shape)를 3D API를 이용해서 그리고자 할 경우에, 폴리곤은 볼록해야한다는 3D API의 전제조건으로 2D 도형 데이터를 쉽게 표시하기가 힘들다.

다행이 OpenGL의 경우는 Tessellation 기능을 이용해 폴리곤을 삼각형으로 구성된 Mesh로 재구성 해줄 수 있다. 하지만 Direct3D의 경우는 이러한 지원이 전혀 없으므로, 개발자가 직접 구현해서 적용해줘야 한다. 그러나 OpenGL 역시 매우 복잡한 폴리곤에 대해서는 삼각형 Mesh를 생성하지 못하는 경우가 많다.

이러한 문제로 인해, 회사에서 맡은 프로젝트 중에 폴리곤에 대한 삼각형 Mesh를 생성해주는 기능이 필요하여 작업한 결과물에 대한 화면이다.

[입력 데이터]

[위의 입력데이터에 대한 결과]

[Hole이 있는 폴리곤에 대한 결과]

[삼각형의 최대 넓이 제약 조건을 지정한 경우]

[삼각형의 최소 내각의 제약 조간을 지정한 경우]

폴리곤에 대한 삼각형으로 구성된 Mesh를 얻고자 할때, 구성 삼각형에 대한 제약 조건으로 최대 넓이와 최소 내각을 지정하여 더욱 다양한 Mesh를 구성할 수 있다. 이런 기능을 이용한다면 Surface Analysis도 가능하다고 생각된다.