3

単一の長方形と小さな一連の長方形の和集合との交点の面積を計算する方法を探しています。

私が欲しいものの数学表現

私は Java を使用しており、すべての長方形は整数 (x、y、w、h) で表されます。すべての長方形は、x/y 軸に合わせて軸が配置されています。助言がありますか？

4

4 に答える 4

1

長方形を調べて、（x、y、w、h）としてではなく、（x1、y1、x2、y2）として表現します。これは、単純に（x、y、x + w、y + h）です。

次に、すべてのRjをループし、長方形をRect1の座標に「クリップ」します。

Rj.x1 = max(Rj.x1, Rect1.x1)
Rj.y1 = max(Rj.y1, Rect1.y1)
Rj.x2 = min(Rj.x2, Rect1.x2)
Rj.y2 = min(Rj.y2, Rect1.y2)

ここで、長方形が交差しなかった場所Rj.x1>=Rj.x2またはその場合のように、Rjをすべて削除します。Rj.y1>=Rj.y2

その後、残りの長方形のすべての領域を合計します（単に(Rj.x2-Rj.x1) * (Rj.y2-Rj.y1)）。

この時点で、クリップされたRjのいずれかが重なっている領域を二重にカウントします。

したがって、j> iであるすべてのRiとすべてのRjを通過してループし、2つを互いにクリップする必要がありますが、今回は交差点がある場合（上記と同じテスト）、ダブルカウントを削除するためにこれまでに持っている値からの交点の面積。

残念ながら、これによりトリプルオーバーラップのすべての領域が二重に削除されます。したがって、これらの領域を見つけて追加し直す必要があります。4重重ね、5重重なりなどについては、以下同様です。

かなり乱雑になるようですね...

おそらく最も簡単なのは、Rjを赤でキャンバスに描画し、最後にRect1内の赤いピクセルを数えることです。（もちろん、実際のCanvasを使用する必要はありません。ビット配列を使用して独自のCanvasを作成できます。）シナリオ（小さな長方形がたくさんある小さな座標空間など）もありますが、これはより高速です。分析ソリューション。ただし、もちろん、これは整数座標がある場合にのみ機能します。

于 2013-02-11T06:25:35.293 に答える
1

Rect1 と RectSet ユニオン内のすべての四角形の間に一意の交差が生じる可能性があります。したがって、Rect1 とユニオン内の各長方形の間の交差を個別に行う必要があります。交差領域は、Rect1 と結合内の四角形との間のすべての交差セクションの結合です。

最適化は、長方形の和集合に対して多数の長方形を作成することです (できれば、和集合が作成されるときに行われます)。Rect1 がこの境界四角形と交差しない場合は、それ以上の交差をスキップして領域を null にすることができます。

于 2013-02-11T04:31:40.813 に答える
1

2 つの長方形の交点は、長方形そのものです (縮退している可能性がありますが、それらは面積がゼロであり、無視できます)。また、和集合の交点は交点の和集合と同じです（分配法則）。したがって、R1 と Rj のそれぞれを交差させて、結果の長方形の結合を見つけることができます。

結合を見つけるための最も簡単な方法は、各頂点を通る垂直線を引いて、シーンを縦縞に分割することです。次に、各ストライプ内で、これはよく知られた 1 次元の問題であり、ポイントの内外をカウントし、カウントが 1 より大きいものを削除することによって解決されます。

于 2013-02-11T05:48:12.457 に答える
0

nm の答えとPQuinn の答えはどちらも、交差点をユニオン全体に分散させてから、ユニオンの面積を見つけることを提案しています。良い考えです。

Java では、R1 と Rj の間に非縮退交差の新しいセットを作成することをお勧めします。これは、ほとんどの交差が縮退するという仮定に基づいています。次に、 http://codercareer.blogspot.com/2011/12/no-27-area-of-rectangles.htmlのアルゴリズムを使用して、一連の交点の面積を見つけます。

于 2014-05-22T16:50:20.630 に答える