最初に Hoey-Shamos アルゴリズムを実装しましたが、将来の保守性には複雑すぎて (これについては何も言えません)、正しく報告されていなかったので、最適化されたブルート フォース アルゴリズムを使用します。
私の質問は、このコードを使用できるように最適化するにはどうすればよいですか?
現状では、私のコードにはネストされた for ループが含まれており、同じリストを 2 回繰り返しています。
編集: 行を HashSet に変換し、2 つの foreach ループを使用しました... 10,000 のスキャンを約 45 秒短縮しました。まだ十分ではありません。
foreach (Line2D g in lines)
{
foreach (Line2D h in lines)
{
if (g.intersectsLine(h))
{
return false;
}
}
} // end 'lines' for each loop
「intersectsLine()」メソッドが強制的に false を返すようにしても (テスト目的で)、10,000 レコードをスキャンするのに 8 秒かかります (700,000 レコードあります)。これは長すぎるため、このコードを最適化する必要があります。
他のすべての行と比較した後、リストから行を削除しようとしましたが、精度の問題があり (理由はわかりません)、速度の増加はほとんど目立ちません。
これが私の intersectsLine メソッドです。ここで別のアプローチを見つけましたが、すべてのメソッド呼び出しなどで遅くなるようです。勾配を計算するのは、計算に時間がかかりすぎるようには思えません (間違っていたら訂正してください)。
public bool intersectsLine(Line2D comparedLine)
{
//tweakLine(comparedLine);
if (this.Equals(comparedLine) ||
P2.Equals(comparedLine.P1) ||
P1.Equals(comparedLine.P2))
{
return false;
}
double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;
firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;
secondLineSlopeX = comparedLine.X2 - comparedLine.X1;
secondLineSlopeY = comparedLine.Y2 - comparedLine.Y1;
double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.X1) + firstLineSlopeX * (Y1 - comparedLine.Y1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (Y1 - comparedLine.Y1) - secondLineSlopeY * (X1 - comparedLine.X1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
//console.WriteLine("s = {0}, t = {1}", s, t);
//console.WriteLine("this: " + this);
//console.WriteLine("other: " + comparedLine);
return true;
}
return false; // No collision */
}
編集:大きなボトルネックは大きなポリゴンです! 100 を超えるラインを含む実行中のポリゴンを除外したところ、700,000 以上のポリゴンすべてが 5:10 で実行されました。許容範囲内です！このコードを実行する前に、ポリゴンを計算する価値があるかどうかを確認する方法はありますか? XMin、Xmax、YMin、および YMax プロパティにアクセスできますか?
ポリゴンをそれぞれ 1000 ライン未満に制限して、別のテストを実行しました。1時間強かかりました。
ポリゴンのすべての制限を削除しましたが、現在 36 時間実行されています...まだ結果はありません。
私が持っているいくつかのアイデア：
-行のハッシュセットを生成するときに、交差の候補を持つ別のハッシュセット/リストを用意します。交差する可能性がある場合にのみ、このリストに行を追加します。しかし、どうすれば可能性を排除/追加できますか? 他のラインと交差する可能性のあるラインが 3 つしかない場合、4000 ラインではなく 3 ラインに対して 4000 ラインを比較します。これだけでも大きな違いが生じる可能性があります。
- 最初と最後のポイントを除いて、同じポイントが 2 回発生する場合は、ネストされた for ループの実行を省略します。
編集：
ポリゴンに関する情報: 合計 700,000
1,000 以上のポイントを持つ 4,000 以上のポリゴンがあります
70,000 ポイント以上のポリゴンが 2 つある
少し工夫すれば、これを 15 分程度に短縮することは可能だと思います。