다각형이 자체 교차하는지 확인

나는 일련의 점으로 완전히 결정된 레이아웃을 가진 System.Windows.Shapes.Polygon 개체를 가지고 있습니다. 이 다각형이 자체 교차하는지 확인해야합니다. 즉, 다각형의 변 중 임의의 변이 정점이 아닌 지점에서 임의의 다른 변과 교차하는 경우. 이것을 계산하는 쉽고 빠른 방법이 있습니까?다각형이 자체 교차하는지 확인

출처

2011-02-02 GWLlosa

쉽고, 천천히, 낮은 메모리 풋 프린트 : 모든 사람에 대한 각 세그먼트를 비교하고 교차로를 확인하십시오. 복잡성 O (n).
약간 빠른 중간 메모리 공간 (위의 수정 된 버전) 공간 "버킷"에 저장 가장자리 후 당 버킷 알고리즘에 기초하여 상기 수행한다. 복잡도 O (n/m) 버킷 (균등 분포라고 가정)에 대한.
& 높은 고속 메모리 공간 : 버킷으로 에지 분할 공간 해시 함수를 사용한다. 충돌을 확인하십시오. 복잡성 O (n).
고속 & 낮은 메모리 용량 : 하나는 here (또는 here)를 기재 등의 스윕 라인 알고리즘을 사용한다. 메모리 균형, 특히 Bentley-Ottmann algorithm - 그것은 좋은 속도가 같은 복잡성 O (N 로그 n)이

마지막으로 내 마음에 드는 것이다. 구현은 너무 복잡하지 않습니다.

출처

2011-02-02 15:25:22

나는 우리가 말한대로 마지막 알고리즘에 대해 머리를 쓰려고 노력하고있다. 특히, 구조 T의 의미/목적을 추적하는 데 문제가 있습니다. – GWLlosa

* T *는 스윕 라인 * L *을 가로 지르는 선분을 포함하는 구조입니다. 가장 효율적인 구조는 이진 검색 트리입니다 ([Bentley-Ottmann 알고리즘] (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm) 참조). –

그림과 함께 Bentley-Ottmann 알고리즘 (http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm)이 설명 된 또 다른 링크를 추가했습니다. –

인접하지 않은 한 쌍의 선분이 교차하는지 확인하십시오 ().

출처

2011-02-02 15:15:42

꼭지점에서 모두 교차해야합니다. 그런 다음 문제는 임의의 선분 집합 사이의 비 정점 교차를 확인하는 가장 빠른 방법입니다. – GWLlosa

좋은 점은 인접하지 않은 세그먼트가 교차하는지 확인하기 위해 편집했습니다. 내장 메소드가 없다고 생각하면 메소드를 작성해야합니다. Polygon.Points를 가져 오는 것으로 시작하십시오. –

** 열려있는 ** 선 세그먼트를 의미하지 않습니까? 나는 인접하지 않은 선분을 들어 본 적이 없다. –

나는이 토론에 다른 알고리즘을 추가합니다.

독자가 축 정렬 경계 상자 (Google이 아닌 경우)를 알고 있다고 가정하면 "Sweep and Prune Algorithm"을 사용하여 AABB의 충돌이 발생하는 가장자리 쌍을 빠르게 찾을 수 있습니다. (구글). 그런 다음 교차점 루틴이이 쌍에 호출됩니다.

장점은 직선이 아닌 선 (원과 스플라인)을 교차 할 수도 있고 접근 방식이 비슷할지라도보다 일반적입니다.

출처

2013-07-25 19:06:05

다각형이 자체 교차하는지 확인

답변

관련 문제