Hello everybody
This page was made with the only proposal of solving the problem of find the greatest and horizontally oriented rectangle that fits in a given polygon.
Look at the picture, it shows a typical case of the problem. A closed polygon (the blue one) and its contained greatest, and horizontally oriented rectangle (the dashed one).
The solution is implemented in Java, but the algorithm is so simple that I've no doubts anybody will easily will transcribe it into any another language.
Well no more bullshit. Here's the code:
|
public static Rectangle findMaxRectinPolygon(Polygon p){ if(p!=null) { Rectangle init=p.getBounds(), tmp=new Rectangle(init), max=null; int x=init.x, y=init.y, area=0, maxarea=-1; for(int i=0;i<init.getWidth();i++) //left side for(int j=0;j<init.getHeight();j++) //upper side for(int k=1;k<=init.getWidth()-i;k++) //right side for(int l=1;l<=init.getHeight()-j;l++){//lower side tmp.setBounds(x+i,y+j,k,l);//make rectangle area=(int)(tmp.getWidth()*tmp.getHeight()); if(p.contains(tmp)&& area>maxarea){ maxarea=area; //saves area and max=new Rectangle(tmp); //polygon } } return max; } else return null; } |
Easy, no?
The source code is here:
|
The .java |
The .class |
The help |
See you later
Columbia University