How can i convert a polygon into a rectangle?

I have a 4 side polygon that i draw on a video frame. I would like to take this polygon and make it a rectangle so i will be able to treat it as a matrix.I want to take the smallest rectangle i can have but still be as close as i can to the original vertices. Can anyone help me with that please? I've been trying to do it for a several days and with no success. Keep in mind that my polygon can be completely not parallel to the axes and in that case i want to get a rectangle that is also not parallel to the axes.

Answer 1

[Image Analyst]

It's not trivial. But luckily John D'Errico has done it for you. See his File Exchange: http://www.mathworks.com/matlabcentral/fileexchange/34767-a-suite-of-minimal-bounding-objects

[Simon]

As far as I understood the user draws a bounding box (here: polygon) interactively ... but maybe I'm wrong.

[Image Analyst]

They draw a polygon that is supposed to be, or should be able to be, a tilted rectangle. At least that's what I got from this "Keep in mind that my polygon can be completely not parallel to the axes and in that case i want to get a rectangle that is also not parallel to the axes." So that's why John's solution will do what is requested while a bounding box won't.

[Maayan]

<file:///C:/Users/lab/Desktop/klynf.png> Can you see the picture i added?If you can i will explain what i meant again. I think that maybe Image Analyst understood me better.The green circles are what i want to bound, so interactively i draw a polygon around them- this is the blue lines. I want the program to take this polygon and convert it into the red rectangle you see. What John did will be able to do that? and another little question, I'm not sure i understand what are the inputs of the function John did for the rectangles.

[Simon]

I don't see a picture ...

[Maayan]

Ok, i thought i added a link. I can see the link in my comment. Maybe i'm the only one who can see it. How can i add an image?

<file:///C:/Users/lab/Desktop/klynf.png>

[Simon]

Sorry, but we cannot see a picture/link that points to your local file system ...

[Maayan]

Ok so how can i load the pic? I have no idea,never done that before. Do you know how maybe?

[Image Analyst]

Copy your picture into the clipboard with Ctrl-C, then go to http://snag.gy and paste it in, then tell us the URL. Or else go to someplace like http://www.tinypic.com and upload it. Or look here for other web sites: http://www.mathworks.com/matlabcentral/answers/7924-where-can-i-upload-images-and-files-for-use-on-matlab-answers

[Maayan]

[IMG]http://i41.tinypic.com/2uigdpc.png[/IMG] Does it work now? and thanks a lot for the help.

[Maayan]

Another question I have about the miniboundrect program John D'Errico wrote is that you get a 5x1 vectors that supposedly define the bounded rectangle. I don't understand how do they define it? Don't i need just 4 vertices? I don't understand what the vectors represent.

[Simon]

So, now I see what you are talking about. My idea was to calculate from the polygon a rectangle which is parallel to the axes.

How is your red rectangle supposed to be calculated from the corners of the blue rectangle? I don't see a correlation.

[Maayan]

It doesn't really have to be correlated.It just needs to be the smallest rectangle that still contains the polygon. I'm trying to see if what Image Analyst posted can help me but i don't understand what the two 5x1 vectors i receive back from the function represent and how do they define the rectangle.

[Simon]

As far as I see it is not obvious what the smallest rectangle that still contains the polygon is. One way is

• search for the longest side of the polygon
• Take this side as the base of the new rectangle (has two points in common with the polygon)
• Get the distance of the furthermost remaining point
• Construct the opposite edge of the rectangle, crossing this point
• Construct the remaining two connecting edges perpendicular to the first edge

This will give you a rectangle with small size (I don't know if it is the minimum size!). And it is all pure 2d-geometry, easy to implement, nothing fancy

[Image Analyst]

I haven't used John's function for rectangle but I imagine it would give the coordinates of the corners. If there are 5 instead of 4 it could be because the last point is the same as the first point to "close off" the rectangle instead of it being a "U" shape.

Imagine that you put a box around your points. Now, as you rotate the box around your points, the sides of the box will have to lengthen or shorten to still contain your points. With one of those shapes of boxes, the area will be a minimum. That is the box he returns to you.

Answer 2

[Simon]

Hi!

You have your polygon coordinates in (x/y) pairs? Take their min/max values and cut from the video frame the rectangle R(xmin:xmax, ymin:ymax).

Maybe you post your code, then it's easier to help.

[Maayan]

This is the relevant part of my code:

 filename = uigetfile; %get the file name
obj = VideoReader(filename);
nFrames=obj.NumberOfFrames;
thisfig = figure();

 for k = 1 : nFrames  
this_frame = read(obj, k);
thisax = axes('Parent', thisfig);
image(this_frame, 'Parent', thisax);
if k==nFrames
title(thisax, sprintf('Frame #%d', k));
end

 if k==1
    result=input('How many polygons would you like to draw? ');
    pos=zeros(4,2,result);
    for i=1:result
    handle=impoly;
    accepted_pos = wait(handle)
    pos(:,:,i) = getPosition(handle);

    end
end
end

I didn't really understand what was your solution to my problem, can you please elaborate?

[Simon]

Hi!

You have your variable "pos". Now you get the minimum and maximum x and y values. This are the coordinates of your rectangle, it contains all polygons.

[Image Analyst]

Simon is saying to use the "bounding box" of your polygon, which will have be aligned with the axes and probably larger than what I suggested. What I suggested may give a tilted rectangle but it will have a smaller size than the bounding box.