用矩形填充多邊形

Question

我有一個相當平滑的多邊形，比如一個橢圓形，凸起和凹痕轉換爲多邊形直線。我想用盡可能少的矩形填充這個多邊形，但是儘可能多地保持多邊形中小角部的精度。矩形可以是任何大小，任何數量。

這樣做的原因是在多邊形上的網頁上進行命中測試。唯一可行的方法是用div填充它，並對所有div進行打擊測試。

當然，對於任何矩形都會有一個最小的方形尺寸，以免我們不僅僅逼近多邊形並用像素尺寸矩形重新創建它。

Answer 1

在一般情況下，如果要確切地說表示具有矩形的數字形狀，則至少需要與輪廓成形拐角上的像素一樣多的矩形。如果您想到45°的數字直邊，那意味着每個像素一個矩形。這是一個嚴重的限制。 （並且甚至不考慮非數字形狀）。

這就是說，您接受近似具有某種錯誤的形狀，並且我建議您首先將形狀縮小一個常數因子，直到您：你將在形狀上疊加一個網格，決定每個瓦片是否屬於該形狀。做到這一點，你可以用「大像素」將你的形狀變成二進制圖像，現在的挑戰是將這個圖像分解成矩形（正是這一次）。

我建議一個簡單的貪婪策略，以便您嘗試找到完全適合的大矩形，然後重複剩下的部分。

如果您對較大和較大的矩形結構元素應用morphological erosion操作，則會找到適合形狀圖像的最大矩形。理論上，你應該嘗試所有寬度和高度的組合，並保持最大面積或周長;這是一項大量的工作。我會建議先嚐試使用正方形，並且當你找到最大的正方形繼續朝着允許的方向繼續時。

找到大矩形後，將其從形狀圖像中清除並重新開始，直至完全擦除。