高速線交差のための線分セグメントコンテナ？ （2D）

Question

私は線を持っています、私はそれが命中する最も近い線分を見つける必要があります。私は線分を最初にソートするとO（log n）の時間にこれを行うことは可能だと思いますが、ソート方法を覚えていません...何らかの木がうまくいくと思いますが、彼らは開始点と終了点の両方で？可能であれば、このデータ構造にすばやく挿入したいと思います。

1つの線と1つの線分のコードがたくさんありますが、1つの線分と多くの線分に何かが必要です...私はどのような用語をGoogleに知らないのですか？

適切な記事へのリンクが良好で、C++コードがさらに優れています。ありがとう！ :)

PS：線分は実際にはCCW順序でソートされた非自己交差ポリゴンの辺ですが、別の方法でそれらをソートするといくつかの利点があると思いますか？

これはすべて2Dです。二思想に

---

、私はこのが可能で完全にはよく分かりません。いくつかの種類の空間パーティショニングが役立つかもしれませんが、そうでなければ、私は線を並べ替える方法を考えていないので、任意の線と比較することができます。

Answer 1

ポリゴンの境界ボックス（最小 - 最大x、y座標）をとり、ボックス内にグリッドを作成できます。次に、各セルについて、セルを横切るすべての線を覚えておいてください。

• グリッドを線 "を描く" ために使用Grid traversal algorithm線が最初にヒットしたセル（O（1））
• をご覧ください：

  は、このようなintesectionを検索します。空でないセルにヒットしたら、すべてのラインをチェックし、セル内に交点があるかどうかをチェックし、最も近い交点を選んでください。すべての交点がセルの外側にある場合は、続行します（これはO（グリッド長）です）。

また、グリッドを階層的にすることもできます（つまり、あなたが求めていたツリーです）。同じアルゴリズムを使用して歩くこともできます。 This is done in raytracing in 3Dであり、時間複雑度はO（sqrt（N））である。

---

それとも、私は私のレイトレーサでやったアプローチを使用：行を含むquadtreeを構築

• を（建物四分木は、記事にdesribedされる） - それらに含まれる場合は、ノード（=領域）に分割

  コンプ：4サブノード（サブエリア）にあまりにも多くのオブジェクトが

• は全てリーフノード光線によってヒットされる四分木のを収集しますルートのute ray-rectangle intersection（ハードではない）。ルートがレイによってヒットした場合、その子を再帰的に処理します。

これについてのクールなことは、ツリーノードがないヒットしたとき、あなたはサブツリー全体（潜在的に大きな矩形領域）を処理をスキップしたことです。

最後に、これはグリッドをトラバースすることに相当します。レイのパス上で最小のセルを収集し、それらの中のすべてのオブジェクトを交差点でテストします。あなたはそれらのすべてをテストし、最も近い交差点を選んで（光線の経路上のすべての線を探索する）必要があります。

これはO（sqrt（N））です。

グリッドトラバーサルでは、交差点を見つけたら検索を停止できます。これを行うには、4つの矩形の交点を距離でソートするか、4セルのグリッドを巧みに横切るかのどちらかを選択します（これは、トラバーサルに戻ります）。

これは、私が思うに実装するのが比較的難しく、うまく機能する別のアプローチです（実データ-O（sqrt（N））でテストしました）。繰り返しますが、もしあなたが少なくとも二つの線を持っていれば、このアプローチの恩恵を受けるでしょう。ポリゴンが10のエッジを持つときには、それらの全てがテストされているのと比べて利益はほとんどありません。

Answer 2

どのようにそれらのいずれかを打つだろうか？彼らがラインであれば、それはありそうもありません。

実際にテストしようとしているポリゴン（平面）の場合、このようなことを行う通常の方法は最初に平面と交差してから、内側/外側の点（2d座標）外側ポリゴン。

多分私はあなたが実際にやっていることを誤解していました。

一般に、複雑な図形で加速する交差点は、空間分割（そして、検査が高価な場合はメールボックスのような技術）によって行われます。

[更新：元の意図を誤って読んでいます]（2d）空間パー​​ティショニングを使用することはできますが、オーバーヘッドはそれに値するものではありません。個々のテストは安価です。ポリゴンが複雑でなければ、歩くほうが安いかもしれません。説明から言うのは難しい。

Answer 3

スキャンライン/アクティブエッジテーブルベースの方法をお探しですか？ Scanline RenderingのWikipediaエントリーを見たり、アルゴリズムのためにGraphics Gemsディレクトリを探したりすることができます（主にCですが、いくつかのC++コードも同様です）。

Answer 4

並べ替えは最高でもO（n log n）操作です。それぞれを個別にチェックする方が良いかもしれません。

Answer 5

説明が間違っていますか？これは正しいですか？

• ダイナミックな線分のセットLがあります。
• 問合せ：与えられた任意の点（x、y）とし、この点から線のどの方向が、あなたはL（もしあれば）に最も近いラインを決定したいですか？

したがって、ポイント（x、y）は修正されていませんか？ （任意の点、任意の方向にすることができます）