加速分段/分段交集

Question

假設您在R^2中有一組分段（稱之爲S）。每個分段都包含在一個WxH維中（因此，集S有四個附加分段，每個分段一邊）和一個要添加到S的分段s。分段s從A點開始（它將屬於到S中的一個段）並結束於B點。我想要計算的是B'點，這樣B'屬於S和AB中的一個段並不與S中的任何其他段相交。是一個wat計算B'而不使用蠻力算法（即S與S中的每個其他分段相交）？

Answer 1

"Real-time Collision Detection"由Ericson（table of contents）是一個很好的資源來解決這樣的問題。第7章空間分區列出了許多適用於解決這些問題的方法。

考慮從八叉樹，KD樹或空間散列開始。他們都相當容易實現，並將使問題從O（N^2）到（從內存）O（N日誌）