查找網格對齊方塊聯合的輪廓

Question

如何獲得使用較小網格塊形成的輪廓形狀的座標。

例如，如果我使用32x32單位塊來構造形狀（任何形狀）。 那麼我怎樣才能得到形狀的整體座標，包括消極的空間。

例如： 人們可以安排這樣的塊： （每塊32×32和座標參考塊的左下角）

Block 1 - (0,0) 
BLock 2 - (32,0) 
Block 3 - 64,0) 
Block 4 - (64,32) 
Block 5 - (64, 64) 
BLock 6 - (32, 64) 
BLock 6 - (0 64) 
Block 7 - (0, 32) 

現在你可以看到這將創建一個空的空間在中間。

所以我想知道的是，如何讓上述形狀的座標是什麼，這樣我得到：

Main Block = (0,0), (96,0), (0,96) 
Empty space = (32,32), (64,32), (64,64), (32,64) 

有任何數學解決這個？

最終我會做複雜的形狀。

感謝

********編輯**** 嗨，

如何應對這種情況？

<------------------^<----^ 
|     || | 
V------------------>| | 
<------^   /^| | 
|  |<------^/|| | 
|  ||  |/ || | 
V------>V------>V-->V----> 

我想結果是這樣

<-------------------<----^ 
|      | 
V  ^----------->  | 
|  |  / | 
|  <-------^/  | 
|    |/  | 
V------>------->--->-----> 

Answer 1

將每個方形看作由四個向量逆時針鏈組成的大綱。

<-----^ 
|  | 
|  | 
V-----> 

因此，對於您的形狀中的所有正方形，請使用它們的輪廓矢量的聯合。如果聯合中的兩個輪廓矢量是相同的，但方向相反，則它們相互抵消並從聯合中移除。

例如，對於兩個正方形是並排的聯合是8個矢量

<-----^<-----^ 
|  ||  | 
|  ||  | 
V----->V-----> 

其減少至6個載體，因爲在中間的兩個垂直矢量取消：

​​

對於你給的例子，結果是（取消後）：

<-----<-----<-----^ 
|     | 
|     | 
V  ^-----> ^
|  |  |  | 
|  |  |  | 
V  <-----V ^
|     | 
|     | 
V----->----->-----> 

Yo你只需要連接最終簡化聯盟中的向量來讀取輪廓路徑。請注意，內部輪廓（「孔」）順時針旋轉。

Answer 2

你可能會需要把重點放在Boolean Polygon Operations，你的情況的工會。有許多論文討論了二維布爾多邊形操作和建設性平面幾何，參見維基百科：http://en.wikipedia.org/wiki/Boolean_operations_on_polygons。