光線があります。光線が当たる最も近い線分を見つける必要があります。最初に線分をソートすると O(log n) 時間でこれを行うことができると思いますが、それらをソートする方法を思い出せません...ある種のツリーが最適に機能すると思いますが、どうすればソートできますか始点と終点の両方でそれらを？可能であれば、このデータ構造への高速挿入も希望します。
1 つの光線と 1 つの線分のコードはたくさんありますが、1 つの線と多数の線分のコードが必要です...どの用語を検索すればよいかわかりません。
適切な記事へのリンクは有効です。C++ コードはさらに優れています。ありがとう！:)
PS: 線分は、実際には自己交差しないポリゴンのエッジであり、反時計回りの順序で並べ替えられています...しかし、別の方法で並べ替えると、いくつかの利点があると思いますか?
これはすべて2Dです。
よく考えてみると、これが可能かどうかは完全にはわかりません。ある種の空間分割が役立つかもしれませんが、そうでなければ、任意の光線と比較できるように線を並べ替える方法が思いつきません。
ポリゴンのバウンディング ボックス (最小-最大 x、y 座標) を取得し、ボックス内にグリッドを構築できます。次に、各セルについて、セルを横切るすべての線を覚えておいてください。
次のような交差点を見つけます。
グリッドを階層化することもできます (つまり、 quadtree - 求めていたツリー)、同じアルゴリズムを使用してそれをたどることができます。これは 3D のレイトレーシングで行われ、時間の複雑さは O(sqrt(N)) です。
または、レイトレーサーで行ったアプローチを使用します。
光線が当たる四分木のすべての葉ノードを収集します。
ルートの光線と長方形の交差を計算します (難しいことではありません)。ルートが光線に当たった場合、その子を再帰的に処理します。
これの優れた点は、ツリー ノードがヒットしない場合、サブツリー全体 (潜在的に大きな長方形領域) の処理をスキップしていることです。
最終的に、これはグリッドをトラバースすることと同じです。レイのパス上で最小のセルを収集し、それらのすべてのオブジェクトの交差をテストします。それらすべてをテストして、最も近い交点を選択するだけです (したがって、レイのパス上のすべての線を探索します)。
これは O(sqrt(N)) です。
グリッドトラバーサルでは、交点を見つけたら検索を停止できます。四分木のトラバーサルでこれを実現するには、子を正しい順序で検索する必要があります。つまり、4 つの四角形の交点を距離で並べ替えるか、4 セル グリッドを巧みにトラバースします (トラバーサルに戻ります)。
これは単なる別のアプローチであり、実装が比較的難しいと思いますが、うまく機能します（実際のデータでテストしました-O（sqrt（N）））。繰り返しますが、このアプローチの恩恵を受けるのは、少なくとも 2 本の線がある場合に限られます。ポリゴンに 10 個のエッジがある場合、それらすべてをテストする場合と比較してメリットはほとんどないと思います。
並べ替えはせいぜい O(n log n) 操作であることに注意してください。個別に確認したほうがいいかもしれません。
それらのいずれかにヒットすることをどのように確信していますか？それらが線である場合、それはありそうにありません。
テストしようとしているのが実際にポリゴン (つまり平面) である場合、この種のことを行う通常の方法は、最初に平面と交差し、次にポリゴンの内側/外側についてそのポイントを (2d 座標で) テストします。
多分私はあなたが実際に何をしているのか誤解しています。
一般に、複雑な図形との交差を加速するには、空間分割を使用します (テストに費用がかかる場合は、メールボックスのような手法も使用します)。
[更新: 元の意図を読み違えていた] (2d) 空間パーティショニングは引き続き使用できますが、オーバーヘッドに見合う価値はないかもしれません。個々のテストは安価です。ポリゴンが複雑でない場合は、それらを歩くだけで安価になる可能性があります。説明から言いにくい。
スキャンライン/アクティブ エッジ テーブル ベースの方法をお探しですか? ウィキペディアのScanline Renderingのエントリを参照するか、 Graphics Gemsディレクトリでアルゴリズム (ほとんどが C ですが、C++ コードもいくつかあります) を検索できます。
説明を求めてください、これは正しいですか？
では、ポイント（x、y）は修正されていませんか？（それは任意の点、および任意の方向である可能性がありますか？）