p1 と p2 の 2 つのポリゴンのオーバーラップをチェックする関数を実装しました。これは、p1 が p2 とオーバーラップしているかどうかを確認するためです。エッジを共有できます)。
関数は問題なく動作します。問題は、1000回呼び出され、各エッジをポイントごとに反復処理する必要があるため、プログラムが非常に遅くなることです。ポリゴンのオーバーラップの 4 つのケースのみをチェックしています。
三角形が三角形に重なる場合。
三角形が長方形に重なっている場合。
三角形が平行四辺形に重なっている場合。
長方形が平行四辺形に重なっている場合。
これらの重複のケースが発生しているかどうかを確認する、より簡単で高速な方法はありますか?
あなたが本当に探しているのは、線分が交差する場所だけだと思います。これは、O((N+k) log N) で実行できます。ここで、N は線分の数 (おおよそ頂点の数) で、k は交点の数です。Bentley-Ottmann アルゴリズムを使用します。これは、単純に一度に 2 つだけを検討するのではなく、すべてのポリゴンを使用して行うのがおそらく最適です。
問題は、どの線分がどのポリゴンに属しているかを追跡することです。また、単純に 2 つのポリゴンのみを考慮するよりも、すべての線分を考慮する方が悪い可能性があるという問題もあります。その場合、有効な交差が 1 つ得られたらすぐに停止します (一部の交差は、オーバーラップとしてカウントされる要件を満たさない場合があります)。この方法はおそらく高速ですが、ポリゴンのさまざまな組み合わせを試す必要がある場合があります。その場合、単純にすべての線分を考慮する方がよいでしょう。
エッジがポリゴンの境界ボックスと交差するかどうかを最初に確認することで、交差テストを高速化できます。Line2D.interSects(Rectangle2D rect) を見てください。
1 万個のポリゴンがある場合は、ポリゴンを空間インデックス (Region Quadtree) に格納することで、さらに高速化できます。これにより、ブルート フォースですべてを検索するのではなく、ビュー ポリゴンに検索が制限されます。しかし、これはおそらく、プログラムの起動時に一度だけではなく、頻繁に検索する必要がある場合にのみ意味があります.