이중으로 연결된 에지 목록
Doubly connected edge list반 에지 데이터 구조라고도 알려진 이중 연결 에지 목록(DCEL)은 평면 그래프와 3D의 폴리토페스를 포함하는 데이터 구조다. 이 데이터 구조는 문제의 물체(수직, 가장자리, 면)와 관련된 위상학적 정보를 효율적으로[quantify] 조작할 수 있도록 한다. 흔히 평면 직선 그래프(PSLG)라고 불리는 평면의 다각형 소분법을 처리하기 위해 계산 기하학의 많은 알고리즘에 사용된다. 예를 들어, 보로노이 도표는 일반적으로 경계 상자 안의 DCEL로 표현된다.
이 데이터 구조는 원래 뮬러와 프리파타가[1] 3D 볼록 다면체의 표현을 위해 제안했다.
이후 다소 다른 데이터 구조가[citation needed] 제시되었으나, 'DCEL'이라는 명칭은 그대로 유지되었다.
단순성을 위해 연결된 그래프만 고려되지만[by whom?], 분리된 구성요소 사이에 더미 에지를 도입하여 분리된 그래프를 처리하도록 DCEL 구조를 확장할 수 있다.[2]
데이터 구조
DCEL은 단순히 이중으로 연결된 가장자리 목록 그 이상이다. 일반적인 경우 DCEL은 각 가장자리, 정점 및 소분면의 기록을 포함한다. 각 기록에는 추가 정보가 포함될 수 있다. 예를 들어 얼굴에는 해당 영역의 이름이 포함될 수 있다. 각 가장자리는 보통 두 개의 면을 경계하며, 따라서 각 가장자리는 두 개의 "반쪽 끝"(오른쪽 그림에서 두 꼭지점 사이에 반대 방향을 가진 두 가장자리로 표시됨)으로 간주하는 것이 편리하다. 각각의 반쪽 끝은 하나의 얼굴로 "연관"되어 있고 따라서 그 얼굴에 포인터를 가지고 있다. 얼굴과 관련된 모든 반쪽 에지는 시계 방향 또는 반시계 방향이다. 예를 들어, 오른쪽 그림에서 가운데 얼굴과 관련된 모든 반쪽 눈금(즉, "내부" 반쪽 눈금)은 시계 반대 방향이다. 반쪽 가장자리에는 같은 얼굴의 다음 반쪽 가장자리와 이전 반쪽 가장자리로 가는 포인터가 있다. 다른 얼굴에 닿으려면 반쪽 끝의 쌍둥이로 가서 다른 얼굴을 가로지르면 된다. 각 반쪽 가장자리에는 원점 꼭지점에 대한 포인터가 있다(대상 꼭지점은 쌍둥이의 원점 또는 다음 반쪽 가장자리의 원점을 쿼리하여 얻을 수 있다).
각 꼭지점에는 정점의 좌표가 포함되며, 정점을 원점으로 하는 임의의 가장자리에 포인터를 저장하기도 한다. 각 면은 외부 경계의 일부 반쪽 가장자리에 포인터를 저장한다(얼굴이 언바운드되지 않은 경우 포인터는 null임). 그것은 또한 얼굴 안에서 일어날 수 있는 각 구멍마다 하나씩 반쪽짜리 리스트를 가지고 있다. 정점이나 면에 재미있는 정보가 없다면 정점을 저장할 필요가 없으므로 공간을 절약하고 데이터 구조의 복잡성을 줄인다.
참고 항목
참조
- ^ Muller, D. E.; F. P. "두 볼록 폴리아드라의 교차점 찾기", 기술 보고서 UIUC, 1977, 38pp, 또한 이론 컴퓨터 과학, Vol. 7, 1978, 217–236
- ^ de Berg, Mark (1997). Computational Geometry, Algorithms and Applications, Third Edition. Springer-Verlag Berlin Heidelberg. p. 33. ISBN 978-3-540-77973-5.
