2
며칠 전이 질문을 게시했습니다 : How to intersect multiple polygons?. 이제는 스윕 라인 알고리즘을 구현했습니다 (구체적으로 Martinez, Rueda 및 Feito의 알고리즘).여러 다각형의 면적을 계산하는 방법은 무엇입니까?
결과는 겹치지 않는 다각형 집합입니다. 그러나이 다각형은 서로 (구멍)를 포함하거나 경계를 만질 수 있습니다 (구멍 또는 섬 다각형).
무슨 뜻인지의 그림 :이 모든 특별한 경우를 포함해야한다고 생각
; 교차점은 스윕 라인 알고리즘에 의해 처리됩니다.
이제 폴리곤 영역 (회색으로 표시)이 필요합니다. 내 첫 번째 아이디어는 다각형을 다각형으로 추가하고 다각형이 서로 포함되어 있는지 확인하고 필요한 다각형 만 선택하는 지능형 선택 메커니즘을 사용하는 것이 었습니다. 그러나 이것은 약간의 O (n^2) 알고리즘을 생성합니다 : 처리 할 각 다각형에 대해, 모든 에지는 이미 처리 된 모든 에지와 비교되어야합니다.
좋지 않습니다. 전체 면적을 계산하는 방법에 대한 힌트를 줄 수 있습니까?
문제는 스윕 라인 알고리즘이 방향에 대해 중요하지 않다는 것입니다. 따라서 구멍은 cw 및 ccw 섬에 저장되지 않습니다. 순서를 고려한 Sweepline 알고리즘을 알고 계십니까? –
원래의 다각형이 모두 반 시계 방향이고 구멍이없는 경우, 스위프 라인 알고리즘은 아일랜드와 구멍에 올바른 방향을 제공해야합니다. 각 세그먼트에 방향을 유지하고 변경하지 마십시오. 세그먼트가 교차로 나누어지면 두 개의 작은 세그먼트가 방향을 상속합니다. 구멍이 자동으로 반 시계 방향이됩니다. –
사실 : 사실이 아닙니다. 특정 스위프 라인 알고리즘에 대해 이야기하고 있습니다. 몇 가지가 있습니다. 발견하고 구현 한 알고리즘은 다각형 모서리의 체인을 찾으려고 시도하면서 끝나지 만 체인의 방향은 체인의 원래 방향에 의존하지 않습니다. 그러나 알고리즘을 수정할 수 있는지 확인합니다. –