Advanced
Detecting Uncertain Boundary Algorithm using Constrained Delaunay Triangulation
Detecting Uncertain Boundary Algorithm using Constrained Delaunay Triangulation
Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography. 2014. Mar, 32(2): 87-93
Copyright © 2014, Korean Society of Surveying, Geodesy, Photogrammetry and Cartography
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : December 12, 2013
  • Accepted : March 03, 2014
  • Published : March 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
성환 조
Member, Seoul National University Engineering Research Institute (E-mail:hallem@snu.ac.kr)
Abstract
지적 필지를 구성하고 있는 폴리곤 집합은 현실세계의 국토를 반영하는 가장 기반이 되는 데이터 집합이다. 따라서 지적 필지는 서로 간에 겹쳐있거나 공백을 가지지 않는 위상적 무결성이 보장되어야하는 데이터이다. 하지만, 여러 가지 이유로 필지들 간의 겹침과 공백의 문제가 발생하고 있고, 이러한 경우 폴리곤의 경계들은 주변의 폴리곤과 정확하게 인접하고 있지 못하기 때문에 의도하지 않은 겹침 영역과 공백 영역이 생산되고 있다. 이와 같이 정확하게 인접되어 있지 않은 경계가 불확실한 모서리를 하나 이상 포함하고 있는 경우, 이 폴리곤을 불확실한 영역이라고 부른다. 본 논문에서는 이러한 영역을 탐색하기 위한 TTA 기법을 제안하고자 한다. TTA 처리 순서는 우선 폴리곤 데이터 집합으로부터 포인트와 폴리라인을 추출하여 제한된 델로네 삼각분할을 수행한다. 다음으로 각 삼각형마다 데이터 집합과 중첩되는 면의 수를 세어 삼각형에 태깅을 수행한다. 태깅 값이 0 또는 1 이상인 삼각형을 추출한 후 연결성을 가지고 있는 삼각형끼리 병합을 수행하여 위상적 모순이 있는 영역들을 발견한다. 본 실험에서는 제안하는 알고리즘을 자동화하여 실세계에서 경계가 교차하는 지적 데이터에 적용하여 실험을 하였다.
Keywords
1. 서 론
지적은 현실세계의 땅을 소유 관계로 구분한 경계이다. 개별 필지는 이들 경계를 폐합한 폴리곤 형태로 결정된다. 지적은 토지의 인허가는 물론 재산권과 밀접하기 때문에 인접한 필지 경계의 위상관계의 일관성을 유지하는 것이 필요하다. 즉 인접 필지 폴리곤들은 반드시 그 모서리나 경계가 정확하게 일치해야 한다( Laurini and Milleret-Raffort, 1994 ). 그러나 지적을 구성하는 필지들은 여러 가지 이유의 오류로 인해 위상관계의 일관성을 유지할 수 없게 되었고, 결과적으로 현재의 지적 공간정보는 위상관계에 있어 다양한 형태의 오류를 가지게 되었다. 이러한 오류는 오랜 기간 지적 서고에 보관되어 있던 지적 원도의 이완, 수축이 가장 큰 원인이고, 다음으로 지적 원도를 디지타이징하는 과정에서 작업자의 판단과 숙련도에 따라 필지 경계에 위치 오차에 의하여 발생하였다. 또한, 서로 다른 기준점 사용한 측량 성과를 통합하는 과정에서 발생하는 오차의 전이가 원인이기도 한다( Chrisman, 1987 ; Ubeda and Egenhofer, 1997 ). 이러한 오류들은 중앙집중적 지적 데이터베이스가 아닌 각자의 관할 지역을 담당하고 있는 측량 주체가 지적 데이터베이스를 관리할 경우 경계 지역에서 더욱더 심각한 오류가 발생할 수밖에 없다. 이렇게 발생한 오류를 해결하기 위하여 GAP-Tree를 이용한 방법( Ai and Van Oosterom, 2002 ) 등이 제안되기도 하였다. 이러한 방법들이 제안되었지만, 특정 유형의 오류에만 적용가능하기 때문에 광범위한 지역에 적용할 경우 국지적으로 심각한 오류를 발생시킬 수밖에 없었다. 특히, 동일한 측량 주체의 관할지역 내에서는 사전에 정의된 모형과 임계값을 적용하여 위상관계의 일관성을 유지하는 것이 가능하지만, 서로 다른 측량 주체에 의하여 구축된 인접 지역의 경우 각자의 고유한 측량 성과 및 오류 유형이 존재하기 때문에 측량 기준점에서 멀어질수록 다양한 형태의 큰 오차를 가지게 된다. 결국, 경계 지역의 필지는 크고 작은 면적의 겹침 영역(Overlaps)과 공백 영역(Gaps)을 가지게 된다.
지적 데이터의 가장 이상적인 목표는 위와 같은 겹침과 공백 영역을 제거하고 인접한 필지들의 위상관계 일관성을 확보하는 것이다. 이를 위해서는 하나의 기관에서 오류가 발생한 지역에서 불확실한 경계를 재측량하여 위상적 무결성을 확보해야하며, 하나의 통합 데이터베이스에 전국토의 지적데이터를 관리하고 모든 측량 성과의 입출력 과정에서 위상적 무결성을 검사 및 탐색할 수 있는 기능을 구축하는 것이 필요하다. 그러나 이는 단기간에 이루어질 수 없을 뿐만 아니라, 상당한 수준의 재정적 투자가 뒷받침되어야 한다. 따라서 현실적인 해결 방안은 자동화된 알고리즘을 이용한 접근이다. 지금까지의 방법은 일반적으로 임계 거리 이내에서 인접한 꼭지점이나 경계를 정합하는 방법이다( Beard and Chrisman, 1988 ).
불확실한 영역을 탐색하기 위하여 많은 연구들이 임계 거리를 정의하고 임계 거리 내에 존재하는 꼭지점이나 경계를 탐색하는 방법을 제안하였다( Perkal, 1966 ). 대표적으로 스위프 라인(sweep line) 알고리즘은 n개의 필지 경계선이 주어졌을 때 O(nlog n)의 연산 속도로 서로 교차하는 경계선 쌍을 탐색할 수 있다. 이 알고리즘은 전산 기하학과 관련된 많은 문제를 해결하는데 효과적으로 활용되었으며, 특히 중첩하고 있는 폴리곤을 탐색하는데 활용되었다. Klajnsek and Zalik (2005) 는 위상관계의 일관성이 없는 영역을 탐색하기 위하여 임계값에 의한 SBS(Sweep Band Status) 방법을 제안하였다. 이 방법은 임의의 꼭지점에서부터 나머지 꼭지점까지의 거리를 측정한다. 측정된 거리가 사전에 정의된 임계 거리보다 짧을 경우 불확실한 영역으로 분류된다. Siejka et al.(2013) 는 공간 데이터의 기하학적 정확성과 관련된 문제가 모든 국가에서 여전히 나타나고 있음을 지적하고, virtual objects 기반의 지도 객체의 위상적 오류를 탐색하고 바로잡기 위한 시스템을 개발하였다.
선행 연구들은 겹침 및 공백 영역을 탐색하기 위하여 필지객체의 개별 선분 사이의 교차 여부를 탐색하고 그 결과를 이용하였다. 하지만 이 방법은 오류가 발생한 영역을 구성하는 개별 경계선들만을 탐색할 뿐, 오류 영역을 직접 탐색하지는 않는다. 따라서 교차하는 경계선을 대상으로 추가적인 알고리즘을 적용하여 겹침 및 공백 영역을 구성해야 한다. 본 연구에서는 이 문제를 해결하기 위하여 제한된 델로네 삼각분할 (Constrained Delaunay Triangulation, 이하 CDT)을 적용하여 인접 지적 데이터에서 겹침 및 공백 영역을 직접 탐색하는 방안을 제안하고자 한다.
2. CDT를 적용한 오류 영역 탐색 기법
본 연구에서는 불확실한 영역을 탐색하는 방법으로 다음과 같이 5단계로 구성되는 TTA(Triangles-Tag Algorithm) 기법을 제안하였다.
  • Step 1. 입력된 인접 지적 데이터의 폴리곤으로부터 꼭지점 과 경계선 추출
  • Step 2. CDT를 적용하여 삼각형 생성의 기준이 되는 꼭 지점과 제약 조건인 경계선으로부터 삼각형 분할
  • Step 3. 분할된 삼각형의 영역과 두 인접 지적 데이터와의 중첩관계 발생 회수를 삼각형의 속성으로 태깅
  • Step 4. 태깅된 값이 0이거나 1보다 큰 삼각형을 검색하고 주변 삼각형들과의 인접관계 분석
  • Step 5. 선분을 공유하는 삼각형들을 병합하여 오류 영역 생성
TTA 기법의 처리 과정은 Fig. 1 와 같다.
PPT Slide
Lager Image
Work flow process chart of TTA
- 2.1 꼭지점과 경계선 추출
제안하는 기법을 수행하기 위해서는 삼각형을 생성하는 기준인 시드 점 집합과 제약 조건인 경계선 집합이 정의되어야 한다. 본 연구에서는 인접 지적 데이터의 필지 폴리곤을 구성하는 꼭지점들과 필지 폴리곤들의 경계선을 CDT에 적용하기 위하여 시드 점 집합과 제약 조건으로 이용하였다.
- 2.2 CDT 적용
꼭지점 집합을 이용한 영역 분할에는 보로노이 다이어그램 (Voronoi diagram), DT 그리고 CDT 기법 등이 있다. 보로노이 다이어그램은 어떤 시드 점들과의 거리에 따라서 평면을 분할한 기법으로서, 평면위에 주어진 시드 점 p 1 , p 2 , ..., pn 에 대한 보로노이 다이어그램은 평면위의 점들이 어떤 pi와 가장 가까운지에 따라서 영역을 분할한다( Aurenhammer, 1991 ). 예를 들어, Fig. 2(a) 와 같이 공간에 9개의 시드 점이 주어지면 Fig. 2(b) 와 같은 보로노이 다이어그램이 나온다. 쉽게 생각하면 어떤 주어진 영역이 있고 그 영역 내에 있는 9개의 점을 기준으로 나눈다고 했을 때, 각 지역이 어떤 점과 가장 가까운지를 기준으로 나누는 방법이다. 또 다른 방법인 DT는 평면위의 점들을 삼각형으로 연결하여 공간을 분할할 때, 이 삼각형들의 내각의 최소값이 최대가 되도록 하는 분할하는 방법이다 ( Lee and Lin, 1986 ). 예를 들어, Fig. 2(c) 와 같이 점들이 있을 때 이 점들을 연결하여 삼각형을 만드는 방법은 Fig. 2(d), (e) 와 같이 다양하게 나올 수 있다. DT는 이러한 여러 삼각분할 중에서 Fig. 2(d) 와 같이 각각의 삼각형들이 최대한 정삼각형에 가까운 즉, Fig. 2(e) 와 같이 길쭉하고 홀쭉한 삼각형이 나오지 않도록 하는 기법이다. DT의 가장 중요한 특징 중 하나는 "어떤 삼각형의 외접원도 그 삼각형의 세 꼭지점을 제외한 다른 어떤 점도 포함하지 않는다" 이다. DT는 보로노이 다이어그램과 밀접한 관계를 가지고 있다. 다시 말해서 보로노이 영역들 간의 시드 점들을 연결하면 이 시드 점들에 대한 델로네 삼각분할을 얻을 수 있는 이중성을 가지고 있다. CDT는 기본적으로 DT와 동일하지만 제약조건으로 주어진 선분이 들로니 삼각 분할 결과에 포함되도록 제약 조건이 부여된다. 제한 조건이란 미리 삼각형이 생길수 있는 영역을 선으로 구분해 놓은 방법이다. 이 제한 조건에 의해 생성되는 삼각형은 주어진 선을 넘지 않는 삼각형을 생성한다( Chew, 1989 ). Fig. 2(f) 와 같이 검은 선의 제약 조건이 주어진 상태에서 DT를 생성하면 Fig. 2(g) 와 같이 제한 선을 넘어가지 않는 삼각형을 얻는다. 본 연구에서는 지적 필지의 경계 내외에서 삼각형을 얻기 위하여 CDT를 사용하였다.
PPT Slide
Lager Image
Representative spatial decomposition methods
CDT는 폴리곤을 중복되지 않는 삼각형으로 분할할 수 있도록 해준다. 또한, 이 삼각형들의 내각의 최소값이 최대가 되도록 하고 주어진 제약 조건을 만족하도록 되어 있다. 즉, 어떠한 삼각형의 경계들도 제약 조건의 경계를 지나지 않고, 모든 폴리곤은 포인트의 추가 없이도 삼각 분할될 수 있다는 것을 의미한다 ( De Berg et al., 1997 ). 본 연구에서 Fig. 3(a) 와 같이 각각의 폴리곤 경계의 안쪽과 바깥쪽에 대해 삼각형을 생성하였다. 폴리곤의 안쪽만 삼각형을 생성할 경우 공백 영역을 탐색할 수 있는 기반을 생성하지 못한다. CDT를 통해 데이터 집합의 모든 공간을 삼각형으로 채우는 과정은 서로 다른 관할 지역에 의해 생성된 데이터 집합 간의 겹침 영역과 공백 영역을 인식할 수 있는 기반을 마련해 준다. Fig. 4(b) 는 입력된 Fig. 4(a) 에 대해 CDT를 생성한 결과를 보여준다.
PPT Slide
Lager Image
Detecting uncertain areas based on CDT
- 2.3 중첩관계를 이용한 태깅
CDT에 의하여 Fig. 3 과 같이 얻어진 삼각형의 일부는 인접한 두 지적 데이터 중 한 데이터의 필지와만 중첩관계를 가지거나 모든 데이터와 중첩관계를 가질 수도 있다. 또한 어떤 지적 데이터와도 중첩관계를 가지지 않는 삼각형도 발생한다. 따라서 각 삼각형이 몇 개의 지적 폴리곤과 중첩관계를 갖는지를 연산하여 겹침 영역과 공백 영역 탐색할 수 있다. Fig. 3(b) 는 CDT를 적용한 Fig. 3(a) 의 삼각형 중 태깅값이 1인 중복과 겹침이 없는 삼각형을 채색한 결과이다. Fig. 4(c) 는 각 삼각형에 태깅값이 부여된 결과를 보여준다.
- 2.4 불확실 영역 추출 및 연결성 확인
Fig. 4(d) 에서 태깅값이 0이거나 2보다 큰 삼각형을 볼 수 있다. 태깅값이 0인 삼각형은 공백 영역을 나타내고, 태깅값이 1인 삼각형은 겹침 영역들을 보여준다. 만약 입력된 데이터 집합의 모든 폴리곤들이 균일한 평면 분할을 구성하고 있다면, 모든 삼각형들의 태깅값은 1이 될 것이다. 이런 면에서 겹침 영역과 공백 영역은 쉽게 불확실한 영역으로 인식 된다. 모든 삼각형들이 인접해 있고 하나보다 많거나 적은 중첩 수를 가지고 있는 경우는 불확실한 영역이다. Fig. 4(d) 는 CDT에 의한 겹침 영역과 공백 영역의 탐색 결과를 보여준다.
- 2.5 병합
탐색된 겹침 영역과 공백 영역은 개별 삼각형의 집합으로 얻어진다. 따라서 삼각형들 사이의 인접성을 확인하여 하나의 영역으로 병합하는 과정이 필요하다. 본 연구에서는 하나의 선분을 공유하는 삼각형들을 탐색하여 폴리곤으로 병합하였다. 이 과정을 통하여 Fig. 4(e) 와 같이 검정색 굵은선으로 표시된 영역과 같은 두 개의 겹침 영역과 한 개의 공백 영역을 탐색할 수 있다.
PPT Slide
Lager Image
Five steps of “Triangles-Tag” algorithm
3. 실험 및 결과
제안하는 TTA 기법을 평가하기 위하여 TTA에 의한 탐색 결과와 서로 숙련도가 다른 8명의 작업자에 의하여 탐색된 오류 영역을 비교하였다. 제안 알고리즘은 윈도우즈 7 플랫폼에서 Visual C++를 사용하여 구현하였다. 실험 대상 지역은 경기도의 시군구 중에서 수원시와 용인시의 경계 지역(510개 필지, 둘레 20.7km, 면적 6.94km 2 )으로 설정하였다. 해당 지역 및 결과는 Fig. 5 와 같다.
PPT Slide
Lager Image
Dataset used in this study and detected results by TTA
실험 대상 지역에 대해 TTA 기법을 수행한 결과, 다양한 모양의 겹침 영역과 공백 영역이 발견되었다. 탐색된 결과를 크게 두 가지의 모양으로 분류하면, 한 쪽 방향으로 얇고 긴모양과 넓은 면을 가진 결과로 나눌 수 있었다. 넓은 면을 가진 결과는 쉽게 육안 판별이 가능하지만, 얇고 긴 모양의 결과는 1m 2 이내의 면적을 가지기 때문에 직선으로 오인할 수 있을 것으로 판단된다. Table 1 에서 보는 바와 같이, 1번부터 5번까지의 겹침 영역과 1번부터 4번까지의 공백 영역은 면적이 매우 작기 때문에 관심을 가지고 확대를 수행해야 그 오류를 알 수 있다. 이러한 미세한 면적의 겹침 영역과 공백 영역이 나타나는 이유는 지적 측량에서 측량 성과 등록할 때, 좌표의 소수점 자리수를 2째 자리 혹은 3째 자리에서 오사오입 과정을 거쳐 잘라내기 때문이다. 이는 서로 인접한 필지가 서로 동일한 필계점을 공유하고 있는 경우에는 문제가 되지 않지만, 필계선 상에 새로 생성되는 필계점의 경우 소수점 자리수가 가지는 오차로 인해 발생되는 것으로 나타났다. Table 1 은 TTA에 의한 결과를 보여준다.
Overlaps and Gaps detected by TTA
PPT Slide
Lager Image
Overlaps and Gaps detected by TTA
Table 1 의 가장 작은 면적의 겹침 영역과 공백 영역 각각 10개에 대하여 숙련도가 서로 다른 작업자에 의해 탐색한 결과는 작업자에 따라 서로 다르기는 하지만 Table 2 에서 보는 바와 같이 면적이 작은 영역에 대해서는 탐색율이 매우 저조하게 나타났다. 면적이 1m 2 미만의 영역에 대해서는 약 8%의 탐색율을 보인 반면, 겹침 영역 8번과 공백 영역 6번은 1m 2 이상의 면적임에도 불구하고 상대적으로 탐색율이 낮게 나타났다. 이는 수작업에 의한 탐색은 대체적으로 한 쪽 방향으로 얇고 긴 모양의 오류면적에 대해서 탐색율이 낮다는 것을 보여준다. 이것은 시각적인 판단에 의존할 수밖에 없기 때문에 발생한 문제이다. 수작업에 의한 탐색 정확도가 서로 다르게 나타나는 이유는 식별 가능한 면을 가지는 오류면적의 여부에 따른 것이다. 식별 가능한 면의 오류에 대해서 많은 작업자가 정확하게 탐색한 반면, 얇고 긴 모양의 오류는 작업자의 숙련도에 따라 탐색율이 다르게 나타났다.
Results by workers with different skills
PPT Slide
Lager Image
Results by workers with different skills
4. 결 론
본 논문은 지적 필지에서 문제가 되는 겹침 영역과 공백 영역을 탐색하기 위한 방법으로 TTA 기법을 제안하였다. TTA 기법은 인접한 지적 데이터에 CDT를 적용하여 삼각 분할을 수행한 뒤, 두 지적 데이터와의 중첩회수를 속성값으로 각각의 삼각형에 태깅한다. 만약 태깅값이 0이라면 공백영역, 2라면 겹침 영역을 구성하는 삼각형이 된다. 이렇게 탐색된 삼각형들의 인접관계를 고려하여 병합함으로써 겹침 및 공백 영역을 탐색할 수 있었다. 제안된 방법의 결과를 서로 다른 숙련도를 가진 작업자의 수작업에 의한 탐색 결과와 비교해 보았을 때 작업자가 탐색하지 못하는 오류도 정확하게 탐색할 수 있음을 확인할 수 있었다.
제안 방법의 장점은 불확실한 영역을 찾기 위해 선행 연구에서 필요했던 허용 오차 임계값이 필요하지 않다는 점이다. 따라서 사용자는 임계값을 조정하면서 반복적으로 결과를 확인해야 하는 반복 작업을 하지 않아도 된다. 또한 임계값에 의해 불확실한 영역이 누락되는 문제 역시 발생하지 않는다. 따라서 제안된 TTA 기법은 그동안 수작업에 의한 방법이나 임계치에 의한 방법이 가지고 있던 한계를 해결할 수 있었다. 하지만 제안된 방법은 기하학적 형상만을 이용한 방법이므로 실제 지적 데이터가 가지고 있는 불부합지 탐색에 있어서는 더 많은 연구가 필요하다. 예를 들어, 가장 우선시되는 지적 필지의 불부합 여부 판단 기준은 필지 면적의 오차가 공차범위 내에 포함되는가이다. 공차 계산에 사용되는 면적은 필지의 대장 면적과 축척인데, 이 면적은 100년 전 일제 강점기때에 시작된 측량 오차가 누적된 면적이다. 이는 현재 지적 필지의 불부합 여부 판단에도 영향을 미치기 때문에 이 문제를 해결하기 위한 추가 연구가 필요하다.
Acknowledgements
본 연구는 국토교통부 첨단도시개발사업 - Realtime Digital Map 생성 및 활용기술 개발과제의 연구비지원 (11첨단도시G10)에 의해 수행되었습니다.
References
Ai T. , Van Oosterom P. 2002 Gap-tree extensions based on skeletons Springer Berlin 10th International Symposium on Spatial Data Handling, Advances in Spatial Data Handling 501 - 513
Aurenhammer F. 1991 Voronoi diagrams–a survey of a fundamental geometric data structure ACM Computing Surveys (CSUR) 23 (3) 345 - 405
Beard M.K. , Chrisman N.R. 1988 Zipper: a localized approach to edgematching The American Cartographer 15 (2) 163 - 172
Chew L. P. 1989 Constrained delaunay triangulations Algorithmica 4 (1-4) 97 - 108
Chrisman R. 1987 Efficient digitizing through the combination of appropriate hardware and software for error detection and editing Journal of Geographical Information Systems 1 (3) 265 - 277
De Berg M. , van Kreveld M. , Overmars M. , Schwarzkopf O. 1997 Computational Geometry Algorithms and Applications Springer Berlin 365 -
Klajnsek G. , Zalik B. 2005 Merging polygons with uncertain boundaries Computers & Geosciences 31 (3) 353 - 359
Laurini R. , Milleret-Raffort F. 1994 Topological reorganization of inconsistent geographical databases: a step towards their certification Computers & Graphics 18 (6) 803 - 813
Lee D. T. , Lin A. K. 1986 Generalized Delaunay triangulation for planar graphs Discrete & Computational Geometry 1 (1) 201 - 217
Perkal J. 1966 On the length of empirical curves, Discussion Paper No. 10 Michigan Inter-University Community of Mathematical Geographers Ann Arbor 132 - 142
Siejka M. , Slusarski M. , Zygmunt M 2013 Correction of topological errors in geospatial databases International Journal of Physical Sciences 8 (12) 498 - 507
Ubeda T. , Egenhofer M. 1997 Advances in Spatial Databases Springer Berlin Fifth International Symposium on Large Spatial Databases, SSD'97 283 - 287