Thread Subject: find axis aligned rectangle within convex hull

Hello everyone,

Is there a way within matlab to find the largest rectangle inside of a polygon? And also making sure the axes of this rectangle are aligned with the axes of a coordinate system (e.g., cartesian)?

Many thanks for reading!

Joe

On Jan 3, 4:04 pm, "Joe McGlinchy" <jmcglin...@esri.com> wrote:
> Hello everyone,
>
> Is there a way within matlab to find the largest rectangle inside of a polygon? And also making sure the axes of this rectangle are aligned with the axes of a coordinate system (e.g., cartesian)?
>
> Many thanks for reading!
>
> Joe

-----------------------------------------------------------------------------
Maybe you can adapt this:

http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle

Description

Inscribed_Rectangle package provides 2 low level computer vision /
image analysis functions able to locate largest square or rectangle
inscribed inside arbitrary shape defined by a binary mask (black and
white image). Only rectangles with vertical/horizontal edges are
considered. The functions proved can be used as tools for larger image
segmentation problems

--------------------------------------------------------------
> Maybe you can adapt this:
>
> http://www.mathworks.com/matlabcentral/fileexchange/28155-inscribedrectangle
>
> Description
>
> Inscribed_Rectangle package provides 2 low level computer vision /
> image analysis functions able to locate largest square or rectangle
> inscribed inside arbitrary shape defined by a binary mask (black and
> white image). Only rectangles with vertical/horizontal edges are
> considered. The functions proved can be used as tools for larger image
> segmentation problems

This has the similar idea.. but I am looking to do this with a polygon defined by vertices, not necessarily an image mask. Is there much in there to adapt the algorithm or is there another way?

"Joe McGlinchy" wrote in message <jdvqg8$fno$1@newscl01ah.mathworks.com>...
> Hello everyone,
>
> Is there a way within matlab to find the largest rectangle inside of a polygon? And also making sure the axes of this rectangle are aligned with the axes of a coordinate system (e.g., cartesian)?
===================

If you have the Optimization Toolbox, you could use QUADPROG. Supposing that the vector x contains the coordinates of the rectangle corners, then the problem sounds to me like,

max x'*Q*x
s.t.
A*x<=b

where A*x<=b are the inequalities for your polygon. Given the polygon vertices, you can obtain the corresponding inequalities using

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities

I leave it to you to derive the appropriate Q matrix.

Hi Matt, thank you for your reply. I do not know the coordinates of the rectangle's corners, I am trying to extract those from an enclosed polygon. Does that change things? I haven't worked much with the optimization toolbox.

Joe

> If you have the Optimization Toolbox, you could use QUADPROG. Supposing that the vector x contains the coordinates of the rectangle corners, then the problem sounds to me like,
>
> max x'*Q*x
> s.t.
> A*x<=b
>
> where A*x<=b are the inequalities for your polygon. Given the polygon vertices, you can obtain the corresponding inequalities using
>
> http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
>
> I leave it to you to derive the appropriate Q matrix.

On Jan 3, 6:04 pm, "Joe McGlinchy" <jmcglin...@esri.com> wrote:
> This has the similar idea.. but I am looking to do this with a polygon defined by vertices, not necessarily an image mask. Is there much in there to adapt the algorithm or is there another way?


----------------------------------------------------------
I have no idea. I've never used it. Why is it so important that the
rectangle be aligned with the raster lines?

Joe:
You could always use the brute force approach. If you want to
quantize your coordinates onto an integer grid (an image), then you
can do it numerically on the quantized image. That is to
1. Call bwboundaries to find all the points on the convex hull - 1 or
2 points for every single row in the convex hull.
2. Start at the top of your convex hull
3. Find the two points that define the start and stop of the row.
4. Find the bottom row for each column found in step 3.
5. Calculate the area of that rectangle.
6. Go to next row and repeat steps 3-5 keeping track of all rectangle
areas.
7. Pick the rectangle that was largest after all rows have been
visited.

It should actually be very very fast.

On 4 Jan, 04:27, ImageAnalyst <imageanal...@mailinator.com> wrote:
> Joe:
> You could always use the brute force approach.  If you want to
> quantize your coordinates onto an integer grid (an image), then you
> can do it numerically on the quantized image.  That is to
> 1. Call bwboundaries to find all the points on the convex hull - 1 or
> 2 points for every single row in the convex hull.
> 2. Start at the top of your convex hull
> 3. Find the two points that define the start and stop of the row.
> 4. Find the bottom row for each column found in step 3.
> 5. Calculate the area of that rectangle.
> 6. Go to next row and repeat steps 3-5 keeping track of all rectangle
> areas.
> 7. Pick the rectangle that was largest after all rows have been
> visited.
>
> It should actually be very very fast.

I'd try a variation inspired by morphological processing. Will only
work for convex binary shapes:

1) Select the point of gravity inside the black convex shape
    in the B&W image. Mark this point as 'blue'.
2) Expand the blue patch incrementally in a spiral
    pattern, until at least one blue corner has an 8-connected
    white neighbour.
3) Fix this (these) corner(s) and expand the blue patch
    in such a way that it retains its rectangular shape,
    until it is impossible to expand the blue rectangle
    without including white points.

At this point you should be left with a candidate for the
largest inscribed rectangle inside the convex polygon.

Rune

"Joe McGlinchy" wrote in message <je03og$g66$1@newscl01ah.mathworks.com>...
> Hi Matt, thank you for your reply. I do not know the coordinates of the rectangle's corners, I am trying to extract those from an enclosed polygon. Does that change things? I haven't worked much with the optimization toolbox.
>
> Joe
>
> > If you have the Optimization Toolbox, you could use QUADPROG. Supposing that the vector x contains the coordinates of the rectangle corners, then the problem sounds to me like,
> >
> > max x'*Q*x
> > s.t.
> > A*x<=b
> >
> > where A*x<=b are the inequalities for your polygon. Given the polygon vertices, you can obtain the corresponding inequalities using
> >
> > http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or-inequalities
> >
> > I leave it to you to derive the appropriate Q matrix.

It is a good idea. If (x1,y1) and (x2,y2) are two corners, and x = [x1 y1 y2 y2]';

-Q=-0.5*[0 0 1 -1;
              0 0 -1 1;
              1 -1 0 0;
              -1 1 0 0]

Note that -Q is NOT positive matrix. It is degenerated and having eigen values with opposite signs. That can cause some numerical issue for QUADPROG.

It is also recommended to enforce x2>=x1 and y2>=y1 in addition to the constraints A*b <= b from the convex hull.

Bruno

On Jan 4, 2:48 am, Rune Allnor <all...@tele.ntnu.no> wrote:
>I'd try a variation inspired by morphological processing. Will only
> work for convex binary shapes:
>
> 1) Select the point of gravity inside the black convex shape
>     in the B&W image. Mark this point as 'blue'.
> 2) Expand the blue patch incrementally in a spiral
>     pattern, until at least one blue corner has an 8-connected
>     white neighbour.
> 3) Fix this (these) corner(s) and expand the blue patch
>     in such a way that it retains its rectangular shape,
>     until it is impossible to expand the blue rectangle
>     without including white points.
>
> At this point you should be left with a candidate for the
> largest inscribed rectangle inside the convex polygon.
>
> Rune
---------------------------------------------------------------------------------------------
Yes I thought of this at first. You can do it using bwdist(). And I
think it would work with a square but I'm not sure it would work with
(i.e. ever find) a rectangle, though I'm not sure if a rectangle would
ever be the largest area - maybe the largest rectangle would ALWAYS be
a square - I'm just not sure. I guess I'd have to try some shapes but
it may be a square if the shape is convex. I think the distance
transform, which I think operates by repeated dilations like you said,
would involve more operations than running around the border checking
for corner points. Tic/toc would be able to figure that out if you
programmed it up both ways.
ImageAnalyst

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <je14b0$i9r$1@newscl01ah.mathworks.com>...
>
> Note that -Q is NOT positive matrix. It is degenerated and having eigen values with opposite signs. That can cause some numerical issue for QUADPROG.
==============

I would have expected that the default trust-region method would be good at handling quadratic saddle points, but I could be wrong.

"Matt J" wrote in message <je1mcg$cho$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <je14b0$i9r$1@newscl01ah.mathworks.com>...

>
> I would have expected that the default trust-region method would be good at handling quadratic saddle points, but I could be wrong.

I check the doc of QUADPROG but did not see any restriction mentioned about the positiveness (accept the a warning about non existence of solution for unconstrained case). So I think it should be alright to use it. The surface is trully a 2D saddle point problem since

area = 1/4 ( s^2 -d^2)

where s = (y2-y1)+(x2-x1) (sum of the sides of the rectangle)
          d = (y2-y1)-(x2-x1) (difference of the sides of the rectangle)

(caution: I did not check carefully)

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <je1oll$kme$1@newscl01ah.mathworks.com>...
>
> I check the doc of QUADPROG but did not see any restriction mentioned about the positiveness (accept the a warning about non existence of solution for unconstrained case). So I think it should be alright to use it. The surface is trully a 2D saddle point problem since
>
> area = 1/4 ( s^2 -d^2)
>
> where s = (y2-y1)+(x2-x1) (sum of the sides of the rectangle)
> d = (y2-y1)-(x2-x1) (difference of the sides of the rectangle)
>
> (caution: I did not check carefully)
===============

True, but the saddle point lies at s=d=0, i.e., a rectangle of area zero. You could obviously apply additional constraints to steer the optimization away from this problematic point.

"Matt J" wrote in message <je1pnc$oge$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <je1oll$kme$1@newscl01ah.mathworks.com>...
> >
> > I check the doc of QUADPROG but did not see any restriction mentioned about the positiveness (accept the a warning about non existence of solution for unconstrained case). So I think it should be alright to use it. The surface is trully a 2D saddle point problem since
> >
> > area = 1/4 ( s^2 -d^2)
> >
> > where s = (y2-y1)+(x2-x1) (sum of the sides of the rectangle)
> > d = (y2-y1)-(x2-x1) (difference of the sides of the rectangle)
> >
> > (caution: I did not check carefully)
> ===============
>
> True, but the saddle point lies at s=d=0, i.e., a rectangle of area zero. You could obviously apply additional constraints to steer the optimization away from this problematic point.

IMO where the saddle point is located is not really relevant for optimization algorithm, what relevant is direction of convexity/concavity.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <je1rjc$225$1@newscl01ah.mathworks.com>...
>
> IMO where the saddle point is located is not really relevant for optimization algorithm, what relevant is direction of convexity/concavity.
================

I'm not sure why that matters on a bounded constraint set.

Although, I once heard that minimizing a concave function is NP hard, but I don't know why that is, or if that's what you mean.

"Matt J" wrote in message <je20s5$kor$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <je1rjc$225$1@newscl01ah.mathworks.com>...
> >
> > IMO where the saddle point is located is not really relevant for optimization algorithm, what relevant is direction of convexity/concavity.
> ================
>
> I'm not sure why that matters on a bounded constraint set.

Actually that matters a big deal since the active constrained set is much harder to be estimated. If the constrained set would be known, solution can be derived easily from the Euler Lagrange's equation.

>
> Although, I once heard that minimizing a concave function is NP hard, but I don't know why that is, or if that's what you mean.

I can't recall the exact detail either, but I think you are right in the fact that there is certainly a huge difference (in both theoretical and practical aspects) when the eigen values of the quadratic form has opposite signs.

Bruno

Wow, a lot of really good ideas here! Thank you all for responding so quickly!

Unfortunately, I would like to look into doing this WITHOUT needing a uniform grid, as in an image. something similar to this

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/

I am terrible with Java though, so translating it looks to be a huge pain. I was hoping MATLAB had something similar to this?

"Joe McGlinchy" wrote in message <je2tf3$o1e$1@newscl01ah.mathworks.com>...
> Wow, a lot of really good ideas here! Thank you all for responding so quickly!
>
> Unfortunately, I would like to look into doing this WITHOUT needing a uniform grid, as in an image.
=================


And that's what you've been given.

"Matt J" wrote in message <je3amt$24l$1@newscl01ah.mathworks.com>...
> "Joe McGlinchy" wrote in message <je2tf3$o1e$1@newscl01ah.mathworks.com>...
> > Wow, a lot of really good ideas here! Thank you all for responding so quickly!
> >
> > Unfortunately, I would like to look into doing this WITHOUT needing a uniform grid, as in an image.
> =================
>
>
> And that's what you've been given.

I.e., the QUADPROG method does not use an image.
The advantage of the Daniel Sud algorithm is that it is O(logN) whereas with QUADPROG, it will probably be O(N), but you have to assess whether N is so large as to make the effort of implementing the Daniel Sud algorithm worthwhile for you.

Thank you, Matt

"Matt J" wrote in message <je3fkc$fm1$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <je3amt$24l$1@newscl01ah.mathworks.com>...
> > "Joe McGlinchy" wrote in message <je2tf3$o1e$1@newscl01ah.mathworks.com>...
> > > Wow, a lot of really good ideas here! Thank you all for responding so quickly!
> > >
> > > Unfortunately, I would like to look into doing this WITHOUT needing a uniform grid, as in an image.
> > =================
> >
> >
> > And that's what you've been given.
>
> I.e., the QUADPROG method does not use an image.
> The advantage of the Daniel Sud algorithm is that it is O(logN) whereas with QUADPROG, it will probably be O(N), but you have to assess whether N is so large as to make the effort of implementing the Daniel Sud algorithm worthwhile for you.