在凹/凸多邊形內部查找有界矩形

Question

我正在尋找一種在凹或多邊形內查找軸對齊矩形的方法。

我一直在尋找網絡，我能找到的最接近的解決方案只適合凸多邊形，而不是一個凹多邊形。例如 -

Finding an axis-aligned rectangle inside a polygon

說實話，我不是一個偉大的數學奇才，所以我寧願找代碼示例或代碼庫，但我想我可以通過自己處理一些數學運算，或找人幫助我。

這將是非常好的，如果該解決方案可以在Java中也一樣，但也許我太貪婪：P

編輯：針對羅素的評論，我加入多一點的信息。

有界的矩形應該儘可能大。該矩形旨在包含其中的文本。最多1到4個單詞，支持文字換行。因此，如果例如它太薄，我會垂直放置文本而不是水平放置。因此對於寬高比，我想它應該足以包含1-4個單詞，或者垂直或水平地包裝單詞。如果矩形很小，我可以調整文本的大小，但最好是文本應儘可能大。

如果多邊形的大體方向是對角線，並且文本在對角線定向時適合好得多，那麼矩形不一定與軸對齊，但是而是與多邊形的對角線對齊。我想這個要求使得這個技巧非常棘手，但是如果你們認爲它是可能的，那麼它會很棒！

我想我已經涵蓋了所有的要求。 ：P

謝謝！

Answer 1

既然你想這樣做的文字，我會假設速度很重要，精度不那麼重要。我建議如下：

1. 將多邊形放置在網格上，單元格與文本尺寸成比例。
2. 使用Bresenham's line algorithm.刪除邊界上的單元格。
3. 卸下邊界單元（外部單元通過從電網向內。
4. 的邊緣擦拭發現剩餘的細胞的最大矩形，例如該方法所示here。

參見Puzzle: Find largest rectangle (maximal rectangle problem)。

編輯：我只注意到這個算法調整的要求，如果多邊形是在一個角度定向。我的建議是找到多邊形的principle axes以檢查方向，旋轉它以將主軸與x軸對齊，並應用上述算法。

另外，我想說明的是，「移除單元格」實際上意味着在代表網格單元的二維數組中設置一個位。

Answer 2

我曾經通過對可能的矩形進行搜索並在其上使用Shape.contains()，以一種非常奇怪的方式實現了類似的系統。它有點慢 - 可能是1s，用於佈局Gettsburg地址的橢圓形 - 但對於靜態文本和簡單形狀的小文本很有用。

如果你有興趣，你可以解壓縮jar文件here並看看TextWrappingLayout。這可能比你需要的複雜得多，因爲它不是在一個矩形中進行佈局，而是儘可能地將每條線放在邊緣附近，但是你可以看到基本的想法。