다중 선 세그먼트 교차점
Multiple line segment intersection계산 기하학에서 다중 선 세그먼트 교차로 문제는 유클리드 평면에 선 세그먼트 목록을 제공하고 두 개 중 어느 하나라도 교차하는지(크로스) 묻는다.
간단한 알고리즘은 각 세그먼트 쌍을 검사한다.단, 다수의 교차 세그먼트를 점검해야 하는 경우, 대부분의 세그먼트 쌍이 일반적인 입력 시퀀스에서 서로 근접하지 않기 때문에 이는 점점 더 비효율적이 된다.많은 수의 세그먼트에 대해 이 문제를 해결하는 가장 보편적이고 더 효율적인 방법은 스위프 라인 알고리즘을 사용하는 것이다. 여기서 우리는 선 세그먼트를 가로질러 미끄러지는 선을 상상하고 이진 검색 트리에 기초한 동적 데이터 구조를 사용하여 각 지점에서 선 세그먼트가 어떤 선 세그먼트를 교차하는지 추적한다.샤모스-Hoey 알고리즘은[1] 선 세그먼트 집합에 교차가 있는지 여부를 결정하는 선 세그먼트 교차로 감지 문제를 해결하기 위해 이 원칙을 적용한다. Bentley-Otmann 알고리즘은 교차로당 로그 시간으로 모든 교차를 나열하는 동일한 원리에 의해 작동한다.
참고 항목
참조
- ^ Shamos, M. I.; Hoey, D. (1976). "17th Annual Symposium on Foundations of Computer Science (sfcs 1976)" (PDF): 208. doi:10.1109/SFCS.1976.16. S2CID 124804.
{{cite journal}}: Cite 저널 요구 (도움말) 장 : "지질교차로 문제"
추가 읽기
- Mark de Berg; Marc van Kreveld; Mark Overmars; and Otfried Schwarzkopf (2000). Computational Geometry (2nd ed.). Springer. ISBN 3-540-65620-0. 제2장: 선 세그먼트 교차점, 페이지 19-44.
- 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 1990년ISBN 0-262-03293-733.2: 어떤 한 쌍의 세그먼트가 교차하는지 여부 결정, 페이지 934–947.
- J. L. 벤틀리와 T.Ottmann, 기하학적 교차로 보고 및 계수를 위한 알고리즘, IEEE Trans.계산하다.C28 (1979), 643–647.
외부 링크
- Dan Sunday에 의한 선과 평면 알고리즘과 샘플 코드의 교차점
- 로버트 플레스강의 노트 4개.워싱턴 대학교 세인트 Louis, CS 506: Computing Geometry (cached copy)
- CGAL의 선 세그먼트 교차점, 계산 지오메트리 알고리즘 라이브러리
- 제프 에릭슨의 "라인 세그먼트 교차점" 강의 노트
- C코드 샘플 Dall Rex Finley를 이용한 선-선 교차로법
