세그먼트 교차점의 속도 증가/

Question

R^2에 세그먼트 집합이 있다고 가정합니다 (S라고 함). 모든 세그먼트는 WxH 차원의 상자에 포함되어 있습니다 (따라서 집합 S에는 상자의 각면에 하나씩 4 개의 추가 세그먼트가 있음). 세그먼트 s는 S에 추가됩니다. 세그먼트 s는 S의 세그먼트 중 하나에) 끝나고 B 점에서 끝납니다. S와 AB '의 세그먼트 중 하나에 대한 B'belong이 S의 다른 세그먼트와 교차하지 않도록 B'점을 계산하고 싶습니다. 거기에 있습니까? brute-force 알고리즘을 사용하지 않고 B '를 계산하는 와트 (즉, AB에서 S의 다른 모든 세그먼트와 교차)?

Answer 1

"Real-time Collision Detection" by Ericson (table of contents)은 이와 같은 문제를 해결하는 훌륭한 리소스입니다. 7 장 공간 분할은 이러한 문제를 해결하는 데 적합한 여러 가지 방법을 나열합니다.

Octrees, KD-Trees 또는 공간 해싱으로 시작하는 것이 좋습니다. 그것들은 모두 구현하기가 비교적 쉽고 문제는 O (n^2)에서 (메모리로) O (n log n)이됩니다.