평면 직선 그래프

계산 기하학에서 평면 직선 그래프, 짧은 PSLG, (또는 직선 평면 그래프 또는 평면 직선 그래프)는 평면 그래프의 가장자리가 직선 세그먼트로 매핑되도록 평면에 평면 그래프를 내장하는 데 사용되는 용어다.^[1]파리의 정리(1948)는 모든 평면 그래프는 이런 종류의 임베딩을 가지고 있다고 말한다.

계산 기하학에서 PSLG는 종종 평면 세분화라고 불렸으며, 세분화는 곡선을 이루는 경계보다는 다각형이라는 가정이나 주장이 있다.

PSLG는 지리 정보 시스템의 지리 지도와 같은 다양한 지도를 나타내는 역할을 할 수 있다.^[2]

PSLG의 특별한 경우는 삼각측량(폴리곤 삼각측량, 점 집합 삼각측량)이다.포인트 세트 삼각형은 그래프 평면도를 유지하면서 직선 가장자리를 추가할 수 없다는 점에서 최대 PSLG이다.삼각형은 다양한 영역에서 수많은 응용을 한다.

PSLG는 특별한 종류의 유클리드 그래프로 보일 수 있다.그러나 유클리드 그래프와 관련된 논의에서 주요 관심사는 그들의 메트릭 속성, 즉 꼭지점 사이의 거리, PSLG의 경우 주요 관심사는 위상학적 특성이다.Delaunay 삼각형과 같은 일부 그래프의 경우 메트릭 및 위상학적 속성이 모두 중요하다.

표현

PSLG를 나타내기 위해 잘 알려진 세 가지 데이터 구조가 있는데, 이 구조는 Winged-edge 데이터 구조, Halfedge 및 Quadedge이다.날개 가장자리 데이터 구조는 세 가지 중 가장 오래된 것이지만 이를 조작하려면 복잡한 사례 구분이 필요한 경우가 많다.이는 가장자리 참조가 가장자리 방향을 저장하지 않으며, 얼굴 주위의 가장자리 방향이 일관될 필요가 없기 때문이다.하프엣지 데이터 구조는 에지의 방향을 모두 저장하고 에지의 방향을 적절하게 연결하여 운영과 스토리지 계획을 단순화한다.Quadedge 데이터 구조는 평면 구획과 그것의 이중 구획을 동시에 저장한다.그것의 기록은 명시적으로 각 에지마다 4개의 에지 레코드로 구성되어 있으며, 간결한 형태로 PSLG를 저장하기에 적합하다.^[3]

PSLG의 문제점

• 점 위치.쿼리 지점의 경우 PSLG의 어느 면에 속해 있는지 찾으십시오.
• 지도 오버레이.동시에 내장된 두 PSLG에 의해 평면이 분할된 두 개의 PSLG(맵)의 오버레이를 찾는다.GIS에서 이 문제는 "테마틱 맵 오버레이"로 알려져 있다.

참고 항목

• PSLG를 나타내는 데이터 구조인 이중으로 연결된 에지 목록
• 로컬 피쳐 크기

참조