如何表示帶孔的多邊形？

Question

通常使用頂點在向量中排序爲CW或CCW的多邊形（2 * 1或1 * 2矩陣）。但是，如何聲明向量中帶有孔的多邊形？

我將對這些多邊形應用各種過程，所以我想要一種表達方式，使我可以輕鬆或有效地工作（即如何在我的程序中聲明這種多邊形以便簡化算法？）

多邊形是2D的，我在MATLAB中編程。

編輯1：我要計算這些多邊形（帶或不帶孔）的visibility graph。

Answer 1

正如其他人所提到的，帶孔的多邊形可以表示爲外部邊界，再加上零個或多個內部邊界，所有這些邊界都不相互重疊*。如果使用非零值winding number來確定內/外，一定要指定你的interio r的邊界與外部邊界相反（逆時針方向爲外部，順時針方向爲內部，反之亦然），這樣孔內的輪廓積分爲零。

僅供參考，這種定義/表示已經在OpenGIS Simple Features Specification（PDF）中正式化。

至於表示：

我可能會在細胞中的K NX2矩陣，其中所述單元陣列中的第一個元素是外部邊界，並且其餘元件的單元陣列（如果有的話）數組是內部邊界。我會使用單元格數組，因爲每個邊界上的點數可能不相同。

*不重疊=除了在各個點上，例如，一個正方形內鑽石：

Answer 2

一個多邊形，加上一個多邊形孔的列表。只要確保各個多邊形不相交。

你打算怎麼處理這件事？

Answer 3

聽起來像每個洞只是多邊形本身內的一個多邊形。也許你可以存儲一個向量，就像你爲外部多邊形描述的那樣，然後是一個更多的多邊形矢量向量。

Answer 4

你在「可見度圖」下的含義是什麼？

兩個「完整」poligons，可能有兩種狀態，+1或-1。

如果你代表的是一個洞，你有一個狀態爲+1，另一個狀態爲-1，表示一個洞，導致狀態爲0.
如果你有重疊的多邊形，最終狀態> 1。然後你可以計算一個新的多邊形的邊界。
如果你有兩個帶有相交孔的多邊形，那麼首先計算一個新的多邊形的狀態，該多邊形由兩個舊的多邊形的外邊框組成，然後處理孔。

無論如何，...我認爲你得到了一般原則。

不知道如何在matlab中做到這一點，目前爲止我只使用它，甚至對於非常簡單的事情。

Answer 5

你可以將一個帶有孔的多邊形分解爲兩個沒有孔的形狀。當你在一個複雜的平面上進行輪廓集成時，可以從多邊形的一個邊緣創建一個「切口」，將其引導至孔的邊緣;圍繞孔的一側並返回;然後圍繞第二個多邊形的另一邊進行遍歷。最後，每個剪輯之間會有兩個路徑積分相互抵消。

「可見性圖」 - 是否用於帶陰影的輻射視圖因子計算？還是光線追蹤圖形算法？

Answer 6

假如你想讓這個結構儘可能通用（即多邊形的多邊形孔內有多邊形，裏面有孔，...），你可能想要有一個樹形結構。 Matlab不是很高效地表示樹結構，但這裏有一個想法...

有一個多邊形結構數組。

每個多邊形都是一個帶有兩個字段的結構，'corner'和'children'。

「角」字段包含角（x，y）座標矩陣，以「data {polyIdx} .corners（：，cornerIdx）」的形式訪問。「兒童」字段是多邊形的結構數組。

下面是一些代碼示例，以與假的孩子，是孔三角形（他們是不是真的有效，但因爲他們很可能會重疊：

polygon = struct; 
npoints = 3; 
polygon.corners = rand(2,npoints); 
polygon.children = struct; 
nchildren = 5; 
for c=1:nchildren 
    polygon.children(c).corners = rand(2,npoints); 
    polygon.children(c).children = struct; 
end 

你可以繼續遞歸定義的孩子，備用在創建孔和填充它們之間