는, 4.44 [분리 자기 교차 폴리 라인은, 프로그램
정점
[1.11의 정렬 된 어레이 2.22] 주어 ...은 다음 3.33 고려 [5.55, 6.66] ...]
여기서 각 정점은 평면 및 어레이 전체에서 (x = 11.11, y = 2.22)와 같이 표현되는 x, y 좌표 폴리선을 나타냅니다. Python에서 자기 교차를 감지하고 "매듭"된 줄에서 "매듭"을 제거하는 가장 빠른 방법은 다음과 같습니다.
문제의 정의는 모호하다. 당신이 "매듭"이라고 정의하는 것을 이해하는 것이 도움이 될 것입니다. 내가 이해할 수있는 것은 당신이하고자하는 것입니다 : 1. 겹침 선의 첫 번째 교차점과 마지막 교차점을 찾습니다. 2. [Vn, 첫 번째 교차점] 및 [마지막 교차점, V + 5] 부분을 가져 와서 폴리 라인을 만듭니다.
Bentley-Ottmann 알고리즘 (https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm)을 사용하여 모든 교차점을 감지하고 정렬 한 다음 나머지 작업을 수행 할 수 있습니다.
감사합니다.