[PanoTools-devel] Inner rectangle of an image

[dmg <dm...@uv...>]

Max mentioned that the problem was more difficult than it
looks. Unfortunately he wasn't willing to share his solution.

I spent some time thinking about it today. The main problem is that
for a given polygon, the number of rectangles that are bound by the
perimeter of the polygon could be infinite (in the continuous world).

So it is necessary to add constraints. The simplest two are:

1. maximize the rectangle's area, and
2. align the rectangle with the axis

This problem, I just learnt, is typical of many industries, including
the metal one.

I found this paper that solves it in the general domain

http://citeseer.ist.psu.edu/daniels97finding.html

@article{255874,
 author = {Karen Daniels and Victor Milenkovic and Dan Roth},
 title = {Finding the largest area axis-parallel rectangle in a polygon},
 journal = {Comput. Geom. Theory Appl.},
 volume = {7},
 number = {1-2},
 year = {1997},
 issn = {0925-7721},
 pages = {125--148},
 doi = {http://dx.doi.org/10.1016/0925-7721(95)00041-0},
 publisher = {Elsevier Science Publishers B. V.},
 address = {Amsterdam, The Netherlands, The Netherlands},
 }

And it cites a reference to the Orthogonal variant O(nlog^3(n)) which
is the one we are facing.

--
Daniel M. German
http://turingmachine.org/
http://silvernegative.com/
dmg (at) uvic (dot) ca
replace (at) with @ and (dot) with .