给定由 SVG 路径构成的不规则形状，如何计算可以容纳在其中的最大矩形（只有水平和垂直边框）？
问问题
1114 次
2 回答
2
I don't think you can find the largest rectangle in the general case. You should better consider the problem to find the largest rectangle that fits inside a shape that is drawn on a grid, it will give you a good approximation of what you are looking for and by decreasing the step of the grid, you can increase the precision of your approximation.
On a grid the problem can be solved in O(n) where n is the number of cells in the grid.
于 2012-05-08T23:56:34.633 回答
0
SVG 路径由线段、三次贝塞尔路径、二次贝塞尔路径和椭圆弧组成。因此它是分段可微的。它由有限数量的段组成，而不是无限循环。别笑，像 Haskell 这样的“懒惰”编程语言可以很容易地表示这样的事情，但在 SVG 中是不允许的。特别是，尽管 SVG 路径在我们看来可能看起来像分形，但它在数学上不可能是分形。此外，常量只能是整数或 IDL 浮点数，它们是 IEEE 单精度浮点数。因此，在网格点处具有所有这些数字的网格的分辨率可能被认为很大，但它肯定是有限的。
使用这些事实，我声称一般来说，如果 SVG 路径包含一个区域，那么路径中包含的矩形存在最大区域；并且有一种易于处理的算法可以找到（至少）一个面积最大的矩形。
任何算法都需要考虑困难的情况，例如（近似）空间填充曲线，它可能有大量小但仍然“最大”的矩形。我不知道算法，所以我们可以在这里考虑如何开发一个。你能解决仅由线段构成的路径的问题吗？网格生成算法会有帮助吗？考虑具有相同中心和面积的矩形的角在一对双曲线上是否有帮助？了解凸包算法是否有帮助？您是否需要称为 max-min 的微分方法，或者可能不需要？那么，您将如何扩展您的算法以允许其他类型的路径段？将这些路径段近似为多边形路径是否有必要、有帮助或没有必要？
于 2012-05-09T01:35:19.153 回答