在SVG路徑中查找最大的矩形

給定由SVG路徑製作的不規則形狀，您如何計算最大的矩形（只有水平和垂直邊框）可以放入其中？在SVG路徑中查找最大的矩形

來源

2012-05-08 waigani

定義最大：area？周長？最大的單一維度？ – abeyer

最大=內部面積最大的矩形。 – waigani

你的意思是圍繞形狀的_bounding box_？即延伸至形狀接觸的minX，minY，maxX和maxY笛卡爾座標的矩形形狀？ – halfer

我不認爲你可以在一般情況下找到最大的矩形。你應該更好地考慮這個問題，找到適合在網格中繪製的形狀內的最大的矩形，它會給你一個你正在尋找的東西的一個很好的近似值，並通過減少網格的步驟，你可以提高精度你的近似值。

在網格上，問題可以在O（n）中解決，其中n是網格中單元的數量。

來源

2012-05-08 23:56:34 Thomash

SVG路徑由線段，三次貝塞爾路徑，二次貝塞爾路徑和橢圓弧組成。因此它是分段微分的。它由有限數量的段組成，而不是無限重複。不要笑，像Haskell這樣的「懶惰」編程語言可以很容易地表現出這樣的東西，但它們在SVG中是不允許的。特別是，雖然SVG路徑可能看起來像我們眼中的分形，但它在數學上不可能是分形。此外，常量只能是整數或IDL浮點數，它們是IEEE單精度浮點數。因此，網格的分辨率可能會被認爲很大，但它肯定是有限的。

使用這些事實，我聲稱一般情況下，如果一個SVG路徑包圍一個區域，那麼存在一個封閉在該路徑中的矩形的最大區域;並且有一個易於理解的算法來查找（至少）一個面積最大的矩形。

任何算法都需要考慮諸如（近似於）空間填充曲線這樣的困難情況，該曲線可能有大量小但仍「最大」的矩形。我不知道算法，所以我們可以在這裏考慮如何開發一個算法。你能解決僅由線段組成的路徑的問題嗎？網格生成算法會有幫助嗎？是否有助於考慮具有相同中心和麪積的矩形在一對雙曲線上有拐角？它有助於瞭解凸包算法嗎？你是否需要稱爲max-min的微分學方法，或者不需要？那麼，如何擴展算法以允許其他類型的路徑段？將這些路徑段看作多邊形路徑會是必要的，還是有幫助的或不必要的？

來源

2012-05-09 01:35:19 minopret

哇 - 這看起來真的很累。我目前正在玩raphael.js。這個想法是定義一個最小尺寸矩形（150/100）並將它們拼湊起來。當我完成後，我會回到這裏。 – waigani

你是否認真相信它可以導致一個可用的算法？ – Thomash

沒有冒險，沒有收穫？ :-) – minopret

在SVG路徑中查找最大的矩形

回答

相關問題