如何識別2D中兩個矩形重疊區域的邊界點？

Question

我正在尋找返回2個任意矩形之間重疊區域邊界的座標。最好的方法來處理這個問題，將照顧所有的特殊情況，例如：

• 只在單個頂點相交的矩形？ （該程序將不得不返回單獨的頂點）
• 共享全部或部分邊的矩形？ （程序將不得不返回公共線段的端點）

要增加複雜性，必須按順時針/逆時針順序對點進行排序。因此，我可以在報告之前使用凸包算法對它們進行排序，但如果有一種算法可以直接計算出邊界點，那將是最好的！

任何想法，我應該看什麼途徑？我不是在尋找代碼項目等，只是泛型算法的一般思路，我不需要保留很多類型的代碼。

編輯：矩形是任意的 - 即它們可以/可以不平行於X/Y軸...

Answer 1

只需使用一般凸多邊形相交法。查找intersect convex polygons rotating calipers。

Answer 2

這可能是真的，但粗糙：

object rectangle { 

    pos { x, y }    // top-left position 
    size { height, width }  // rectangle-size 
} 


collision::check (rectangle rect) { 

    // collision-detection logic 

    collision->order_coords(coords); // order-coords clockwise; 
    return collision_result_object; // return collided vertices, ordered clockwise, or 0 if rect hit nothing 
} 

collision::order_rects (rectangle *rect, opt angle) { 

    return clockwise_rects; // returns rectangles ordered clockwise 
} 

collision::order_coords (coordinate *coord, opt angle) { 

    return ordered_coords; // recieves coordinates and returns ordered clockwise 
} 

rectangle rects; // bunch of rectangles 

ordered_rects = collision->order_rects (rects); // order rects starting at 12PM 

loop {  

     foreach ordered_rects as i { 

      if (collision->check(i)) { 

      array_of_collision_result_objects[i] = collision->check(i);  // start checking rects starting at 12PM, if collision found, return ordered vertexes 
      } 
     } 

} 

Answer 3

查找矩形段的所有路口。結果由其中的一些和一些初始頂點組成。要找到它們，只需檢查它在兩個矩形中的每個點。刪除不必要的點（如果一行有3個或更多）。結果是凸的，並且沒有任何一點是嚴格的，所以（如果至少有3個）從某個內點按角度排序點並享受結果。

Answer 4

好吧，我們將再次嘗試這個......

考慮了兩下，由通過在ABCD從每一個頂點畫一條線（黑色）到EFGH（紅色）定義區域的聯合：

這裏最難的是未來與所有這些線定義的形狀

一旦你（無論是灰色系和原線從ABCD和EFGH矩形來了。）圖出來，創建一個鏈接l並且假設這些形狀中的每一個存在於交叉點內。

第1步。翻譯&旋轉一切，以便ABCD在0,0上有一個頂點，它的線與x和y軸平行/垂直。

步驟1A。在ABCD中查找最低的y值頂點，然後從場景中的所有其他頂點中減去它。我們假設爲了演示目的，該頂點是C.通過從場景中的每個頂點減去C，我們將有效地將原點（0,0）移動到C，使得圍繞C的旋轉變得容易。

for all shapes in linked list { 
    for all vertices in shape { 
     vertex -= C; 
    } 
} 

步驟1B。繞着由等於所述C-> B載體和x軸之間的角度的角度的原點一切，所以在x軸即乙土地：

// see http://en.wikipedia.org/wiki/Atan2 
float rotRadians = atan2(B.x, B.y); // assuming ABCD vertices are labelled clockwise 

for all shapes in linked list { 
    for all vertices in shape { 
     rot(thisVert, rotRadians); 
    } 
} 


// ... 

// function declaration 
void rot(theVertex, theta) { 
    tempX = theVertex.x; 
    tempY = theVertex.y; 

    theVertex.x = cos(theta) * tempX + sin(theta) * tempY; 
    theVertex.y = cos(theta) * tempY - sin(theta) * tempX; 

} 

如果ABCD頂點被標記順時針ABCD的頂點，現在應該是這樣的：

A = ABCDx , ABCDy 
B = ABCDx , 0 
C = 0  , 0 
D = 0  , ABCDy 

（順時針如果他們沒有標籤，那麼「內在於」爲您在第2步是行不通的，所以一定要確保在atan2(...)調用中使用的是VERT頂點逆時針從最低點開始）。

第2步。現在我們可以很容易地分析一個形狀是否位於ABCD矩形內，例如， if (thisVert.x >= 0 && thisVert.y >= 0 && thisVert.x <= ABCDx && thisVert.y <= ABCDy)。遍歷形狀的鏈接列表，並檢查以確保每個形狀的每個頂點位於ABCD內。如果一個形狀的一個頂點不在ABCD內，那麼該形狀不是ABCD/EFGH交點的一部分。將其標記爲不是交叉點的一部分並跳到下一個形狀。

第3步。撤消步驟1B的旋轉，然後撤消步驟1A的翻譯。

第4步。用EFGH而不是ABCD重複步驟1-3，您將擁有交集。

---

如果兩組之間唯一的交集是一條直線，那麼上述將不返回任何交集。如果交點== NULL，則檢查相交的線。

如果交點仍爲NULL，則檢查相交點。

Answer 5

我想出應該涵蓋所有可能的情況下，合理的方法：

我們需要的是基本上3個步驟：

第1步：

for each side Si of R1 
    for each side Sj of R2 
      Check if Si and Sj intersect. If they do, push the point in results array 
      (This also has to take care of the case in case Si and Sj overlap, which is 
      basically checking if they have the same equation or not - if so, push in 
      the points of overlap. This also takes care of the case where a vertex of 
      R2 lies on Si). 
    next 
next 

第2步：

for each vertex Vi of R1 
    Check if Vi lies inside R2, If so, push it in the results array. 
next 

步驟3：

for each vertex Vi of R2 
    Check if Vi lies inside R1, If so, push it in the results array. 
next 

現在，責令結果陣列，並返回

對於第2步& 3（如何找到一個點是否位於矩形內） - 我會用this excellent article（表示有最後的算法）。