computational-geometry - セグメント/セグメント交差点のセットの高速化

Question

R^2 に一連のセグメントがあるとします (これを S と呼びます)。すべてのセグメントは、次元 WxH のボックスに含まれています (つまり、セット S には、ボックスの各辺に 1 つずつ、合計 4 つの追加セグメントがあります) と、S に追加されるセグメント s があります。セグメント s は、点 A から始まります (計算したいのは、B'がSのセグメントの1つに属し、AB'がSの他のセグメントと交差しないような点B'です。ブルートフォースアルゴリズムを使用せずにB'を計算するワット（つまり、ABをSの他のすべてのセグメントと交差させる）？

Answer 1

Ericson による「Real-time Collision Detection」 (目次) は、このような問題を解決するための優れたリソースです。第 7 章の空間パーティショニングでは、このような問題を解決するのに適した方法をいくつか挙げています。

オクトリー、KD ツリー、または空間ハッシュから始めることを検討してください。それらはすべてかなり簡単に実装でき、問題を O(n^2) から (メモリから) O(n log n) にします。