掃引アルゴリズム

Question

私は良いデータを得る良い掃引アルゴリズムをお勧めしますか？ いくつかの文書、方法、その他。

これは、2次元空間内のグラフの交点を検出するスイープアルゴリズムです。グラフは常に閉じています。

Answer 1

http://www.amazon.com/Computational-Geometry-Algorithms-Applications-Second/dp/3540656200のものはかなり良いです。

交差点をテストするためのスイープラインはかなり簡単です。ここにあなたを始めるための論文があります：http://www.cs.umd.edu/~mount/Papers/crc-intersect.pdf。

Answer 2

私はこれまでプレーンクローズドグラフの交差を検出するスイープアルゴリズムに3つの変種を実装しました。私はグラフを表現する大きなデータを持っています（200辺以上のように、頂点は2次元の点のペアです。辺は2つの頂点のペアです.1つはソースでもう1つはデスティネーションです）。他の目的のためのC++ライブラリ。

問題は、3つの実装が整数ではうまく動作しないか、それほど長くないデータを2倍にすることですが、グラフを表すデータにこれらの3つの実装を試みたとき、毎回異なる結果を得ました。もの。私はすべて私が欲しいの交差点が、私は結果として、グラフから、いくつかのポイントを持っているかどうか（交差点ではありません）グラフ

から他のいくつかのポイントが、私は必要があるいくつかの交差点を持っているかどうか

• 私はちょうど交差点が

このすべてDEPEを必要としているかどうか計算結果から

が欠落しています私が見たソート関数の上のndsと、他の何かの上にあるかもしれませんが、私はそれを理解できません。次のようにソート機能は、グラフの辺を注文：

x.E1.Vstart<x.E2.Vstart or 
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart<y.E2.Vstart or 
x.E1.Vstart==x.E2.Vstart and y.E1.Vstart==y.E2.Vstart and slope(E1)<slope(E2) 

私はこのソート機能がmonoticityやその他の場合に適して思ったが、どうやらそれだけでいくつかのケースのために働いている：E1(Vstart,Vend), E2(Vstart,Vend)などの2つのエッジを考える

通常の交差点のほかに他の交差点も検出します。いくつかのケースでは、すべての交点を計算するのではなく、グラフからある点だけを計算するという点で全く機能しません。