Given an irregular shape made by an SVG path, how do you calculate the largest rectangle (with only horizontal and vertical borders) that can fit inside it?
Asked
Active
Viewed 1,215 times
1
-
Define largest: area? perimeter? largest single dimension? – abeyer May 08 '12 at 23:40
-
largest = the rectangle that has the most area inside it. – waigani May 09 '12 at 03:31
-
Do you mean a _bounding box_ around the shape? i.e. a rectangular shape that stretches to the minX, minY, maxX and maxY cartesian coordinates the shape touches? – halfer May 09 '12 at 09:40
-
Its basically the "maximal rectangle problem". Does that make it clearer? – waigani May 09 '12 at 21:12
2 Answers
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.
Thomash
- 6,339
- 1
- 30
- 50
0
An SVG path consists of segments of lines, cubic Bezier paths, quadratic Bezier paths, and elliptic arcs. Therefore it is piecewise differentiable. It consists of a finite number of segments, not an infinite recurrence. Don't laugh, things like that can be represented easily in a "lazy" programming language such as Haskell, but they're not allowed in SVG. In particular, although an SVG path can look like a fractal to our eyes, it can't mathematically be a fractal. Furthermore the constants can only be integers or IDL floats, which are IEEE single-precision floating-point numbers. So the resolution of a grid that would have all of those numbers at grid points might be considered large, but it is surely finite.
Using those facts I claim that in general, if an SVG path encloses an area, then there exists a largest area for rectangles enclosed in the path; and that there is a tractable algorithm to find (at least) one rectangle whose area is the largest area.
Any algorithm needs to account for difficult cases such as (approximations to) space-filling curves, which could have a large number of small but still "largest" rectangles. I don't know an algorithm, so we can consider here how to develop one. Could you solve the problem for paths made only of line segments? Would a mesh generation algorithm help? Does it help to consider that rectangles that have the same center and area have their corners on a pair of hyperbolas? Does it help to know about convex hull algorithms? Would you need the differential calculus method called max-min, or perhaps not? Then, how would you extend your algorithm to allow the other types of path segments? Would it be necessary, or helpful, or unnecessary to approximate those path segments as polygonal paths?
minopret
- 4,726
- 21
- 34
-
wow - this looks really involved. I'm currently playing with raphael.js. The idea is to define a minimum sized rect (150 / 100) and tiling them up. I'll post back here when I'm done. – waigani May 09 '12 at 03:34
-
-
-
I'm going to implement this idea. It is not perfect but hopefully good enough. http://stackoverflow.com/questions/7332065/what-is-the-best-algorithm-to-find-the-largest-black-convex-area-in-an-image/7497967#7497967 – waigani May 09 '12 at 21:08