問題描述
下面是 2 個矩形.給定矩形頂點的坐標-(x1, y1)...(x8, y8)，如何計算重疊區域(下圖中的白色)的面積?
注意:
Below are 2 rectangles. Given the coordinates of the rectangle vertices - (x1, y1)...(x8, y8), how can the area of the overlapping region (white in the figure below) be caclulated?
Note that:
- 點的坐標可以是任意的
- 矩形可以重疊也可以不重疊
- 當矩形不重疊，或者它們在點或線處重疊時，假設面積為 0.
- 如果一個矩形在另一個矩形內，則計算較小矩形的面積.
推薦答案
既然你說矩形可能沒有對齊，那么可能的答案可能是空無、一個點、一條線段或一個有 3-8 條邊的多邊形.
Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides.
執行此2d boolean 操作的通常方法是選擇邊緣的逆時針順序，然后評估臨界點(交點或角)之間的邊緣段.在每個交點處，您可以在第一個矩形的邊緣段和第二個矩形的邊緣之間切換，反之亦然.您總是選擇上一個片段左側的片段.
The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). At each intersection you switch between an edge segment of the first rectangle to an edge of the second, or visa-versa. You always pick the segment to the left of the previous segment.
有很多細節，但基本算法是找到所有交叉點并使用適當的數據結構在它們的邊緣上對它們進行排序.選擇一個交點(如果有)并選擇一條遠離該交點的線段.找到所選起始線段左側的另一個矩形的線段.在圖中，我們選擇交叉點a(箭頭所示方向)上的綠色線段作為參考線段.另一個矩形右側的線段是從a 到b 的線段.將其用作下一個參考線段，并在其左側選擇一個綠色線段.這是從 b 到 c 的片段.以相同的方式查找段 cd.下一段是從 d 到角點，所以角點也在交點的頂點列表中.從玉米我們回到a.
There are LOTS of details, but the basic algorithm is to find all intersections and order them on their edges with an appropriate data structure. Choose an intersection (if there is one) and choose a line segment leading away from that intersection. Find the segment of the other rectangle to the left of the chosen starting segment. In the picture, we choose the green segment on intersection a (in the direction indicated by the arrow) as the reference segment. The segment of the other rectangle that is to the right, is the segment from a to b. Use that as the next reference segment, and choose a green segment to the left of it. That's the segment from b to c. Find segment cd the same way. The next segment is from d to the corner, so the corner is in the vertex list for the intersection as well. From the corn we get back to a.
要每次選擇左側，請使用相交邊的方向向量坐標的確定.如果有序的有向邊對的行列式是正的，那么你就走對了.
To choose the left side each time, you use the determinate of the coordinates of the direction vectors for the edges that meet. If the determinant for the ordered pair of directed edges is positive, you're going the right way.
既然您有了相交多邊形的頂點，您就可以使用調查者的公式得到面積.
Now that you have the vertices of the intersection polygon, you can use the surveyor's formula to get the area.
我要留給你的一些細節是:
Some of the details that I'm leaving to you are:
如果一個角與另一個三角形的邊或頂點重合怎么辦?
What if a corner is coincident to to an edge or vertex of the other triangle?
如果沒有交叉點怎么辦?(一個矩形在另一個里面，或者它們是不相交的——你可以使用多邊形點檢查來解決這個問題.參見 關于多邊形的維基百科文章.
What if there are no intersections? (one rectangle is inside the other, or they are disjoint--you can use point-in-polygon checks to figure this out. See the Wikipedia article on polygons.
如果交點是單點或線段怎么辦?
What if the intersection is a single point or a segment?
這篇關于矩形與矩形相交的面積的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！