Minimum Area bounding box

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Minimum Area bounding box

triplederby100-propos
I need to find a minimum area bounding box for a given polygon - which could be convex or concave. Is this something possible to find using JTS? I see that there is a MinimumDiameter class but I am not sure if/how it can be used for this purpose. Any pointers are highly appreciated.

Jatin

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Minimum Area bounding box

Stefan Steiniger
there is a MBR implementation for the OpenJUMP map generalization plugin,

but I am not sure if it is "Minimum Area"

see:
http://jump-pilot.svn.sourceforge.net/viewvc/jump-pilot/plug-ins/MapGenToolboxPlugin/src/mapgen/measures/OrientationMBR.java?view=markup

so you may extract the code you need

stefan
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Minimum Area bounding box

Johnathan Kool
In reply to this post by triplederby100-propos

You might want to try the .getEnvelope() or .getEnvelopeInternal() methods of Geometry (inherited by Polygon).  .getEnvelope() will return the bounding box as a Geometry (and if you want the outline, then use .getBoundary()).  .getEnvelopeInternal() will return an Envelope – useful for pulling minx, miny, maxx and maxy values.

 

J

 

From: [hidden email] [mailto:[hidden email]] On Behalf Of [hidden email]
Sent: Wednesday, June 03, 2009 2:02 AM
To: [hidden email]
Subject: [jts-devel] Minimum Area bounding box

 

I need to find a minimum area bounding box for a given polygon - which could be convex or concave. Is this something possible to find using JTS? I see that there is a MinimumDiameter class but I am not sure if/how it can be used for this purpose. Any pointers are highly appreciated.

Jatin


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

mbedward
In reply to this post by triplederby100-propos
HI Jatin

I assume you're referring to an enclosing rectangle rotated to
minimize its area - yes ?

Here is an old but still very nice explanation of an algorithm to do
that with a demo applet:

http://cgm.cs.mcgill.ca/~orm/maer.html

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

Sandro Zacchino
In reply to this post by triplederby100-propos
Hi,

if someone need a Minimum Enclosure implementation that can be plugged into JTS you can find one at

http://www.keepintech.it/files/minimumenclosure.zip

The implementation I made, is a port of minimum area rectangle algorithm as found in http://www.geometrictools.com/

The comments are in italian but the methods you need are the ones named "computeMER" (I think they are quite readable)

If someone modify the code, please redistribute the code.

Sandro Zacchino

[hidden email] ha scritto:
I need to find a minimum area bounding box for a given polygon - which could be convex or concave. Is this something possible to find using JTS? I see that there is a MinimumDiameter class but I am not sure if/how it can be used for this purpose. Any pointers are highly appreciated.

Jatin

_______________________________________________ jts-devel mailing list [hidden email] http://lists.refractions.net/mailman/listinfo/jts-devel


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

mbedward
Hi Sandro,

Many thanks for the code !

I've just had a quick look at your code and tried it out with some
randomly generated convex polygons  If found a couple of little
problems...

In the Vector2 class, I think you want to make those public final
fields static members:

        private static final double ZERO_TOLERANCE = 1e-06f;
        public static final Vector2 ZERO = new Vector2(0.0d, 0.0d);
        public static final Vector2 UNIT_X = new Vector2(1.0d, 0.0d);
        public static final Vector2 UNIT_Y = new Vector2(0.0d, 1.0d);

And in the method Box2.computeVertices I think this line:

            akVertex[1] = center.add(akEAxis[0]).add(akEAxis[1]);

should be:

            akVertex[1] = center.add(akEAxis[0]).sub(akEAxis[1]);

...otherwise you get a triangle instead of a rectangle :-)

Once I made those changes the code seemed to work well.

I think that this would be a nice facility to add to JTS.

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

mbedward
Sandro,

Here's a little demo app for your code.  It displays a random convex
polygon and the associated MER.  Click on the display panel to
generate new polygons.

Michael


package jtsdemos.minimumenclosure;

import com.vividsolutions.jts.algorithm.ConvexHull;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.Polygon;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.image.BufferedImage;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;


/**
 * A simple app to demonstrate Sandro Zacchino's minimum enclosing
 * rectangle (MER) code.  It generates a random convex polygon, calculates the
 * MER, and displays both on screen.  Mouse click on the display panel to
 * generate new polygons.
 *
 * @author Michael Bedward
 */
public class Demo {

    private static final double CLOUD_MIN = 150;
    private static final double CLOUD_W = 200;
    private static final int IMGW = (int)(CLOUD_W + 2 * CLOUD_MIN);

    private Polygon hullPoly;
    private Polygon merPoly;

    public static void main(String[] args) {
        (new Demo()).doDemo();
    }

    private void doDemo() {
        generatePolys();

        final JPanel panel = new JPanel() {

            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);

                BufferedImage bufImg = new BufferedImage(IMGW, IMGW,
BufferedImage.TYPE_INT_ARGB);
                Graphics2D gr = (Graphics2D) bufImg.getGraphics();

                gr.setColor(Color.BLUE);

                Coordinate[] hullCoords = hullPoly.getCoordinates();
                Coordinate c0 = hullCoords[0];
                for (int i = 1; i < hullCoords.length; i++) {
                    gr.fillOval((int)c0.x-4, (int)c0.y-4, 9, 9);
                    Coordinate c1 = hullCoords[i];
                    gr.drawLine((int)c0.x, (int)c0.y, (int)c1.x, (int)c1.y);
                    c0 = c1;
                }

                gr.setColor(Color.MAGENTA);
                Coordinate[] merCoords = merPoly.getCoordinates();
                c0 = merCoords[0];
                for (int i = 1; i < merCoords.length; i++) {
                    Coordinate c1 = merCoords[i];
                    gr.drawLine((int)c0.x, (int)c0.y, (int)c1.x, (int)c1.y);
                    c0 = c1;
                }

                ((Graphics2D)g).drawImage(bufImg, null, 0, 0);
            }
        };

        panel.addMouseListener(new MouseAdapter() {

            @Override
            public void mouseClicked(MouseEvent e) {
                generatePolys();
                panel.repaint();
            }
        });

        panel.setToolTipText("click for new polygon");

        final JFrame frame = new JFrame("MER demo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(panel);
        frame.setSize(IMGW, IMGW);

        SwingUtilities.invokeLater(new Runnable() {

            public void run() {
                frame.setVisible(true);
            }
        });
    }

    private void generatePolys() {
        hullPoly = randomConvexPoly();
        merPoly = MinimumEnclosure.computeMER(hullPoly);
    }

    private Polygon randomConvexPoly() {
        Random rand = new Random();
        final Coordinate[] cloud = new Coordinate[10];

        for (int i = 0; i < cloud.length; i++) {
            cloud[i] = new Coordinate(
                    CLOUD_MIN + CLOUD_W * rand.nextDouble(),
                    CLOUD_MIN + CLOUD_W * rand.nextDouble());
        }

        ConvexHull hull = new ConvexHull(cloud, new GeometryFactory());
        return (Polygon) hull.getConvexHull();
    }

}
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

Sandro Zacchino
Thank you Michael!

I'll debug the code as soon as possible.

Thank you also for you little example.

Bye

Sandro


Michael Bedward ha scritto:

> Sandro,
>
> Here's a little demo app for your code.  It displays a random convex
> polygon and the associated MER.  Click on the display panel to
> generate new polygons.
>
> Michael
>
>
> package jtsdemos.minimumenclosure;
>
> import com.vividsolutions.jts.algorithm.ConvexHull;
> import com.vividsolutions.jts.geom.Coordinate;
> import com.vividsolutions.jts.geom.GeometryFactory;
> import com.vividsolutions.jts.geom.Polygon;
> import java.awt.Color;
> import java.awt.Graphics;
> import java.awt.Graphics2D;
> import java.awt.event.MouseAdapter;
> import java.awt.event.MouseEvent;
> import java.awt.image.BufferedImage;
> import java.util.Random;
> import javax.swing.JFrame;
> import javax.swing.JPanel;
> import javax.swing.SwingUtilities;
>
>
> /**
>  * A simple app to demonstrate Sandro Zacchino's minimum enclosing
>  * rectangle (MER) code.  It generates a random convex polygon, calculates the
>  * MER, and displays both on screen.  Mouse click on the display panel to
>  * generate new polygons.
>  *
>  * @author Michael Bedward
>  */
> public class Demo {
>
>     private static final double CLOUD_MIN = 150;
>     private static final double CLOUD_W = 200;
>     private static final int IMGW = (int)(CLOUD_W + 2 * CLOUD_MIN);
>
>     private Polygon hullPoly;
>     private Polygon merPoly;
>
>     public static void main(String[] args) {
>         (new Demo()).doDemo();
>     }
>
>     private void doDemo() {
>         generatePolys();
>
>         final JPanel panel = new JPanel() {
>
>             @Override
>             protected void paintComponent(Graphics g) {
>                 super.paintComponent(g);
>
>                 BufferedImage bufImg = new BufferedImage(IMGW, IMGW,
> BufferedImage.TYPE_INT_ARGB);
>                 Graphics2D gr = (Graphics2D) bufImg.getGraphics();
>
>                 gr.setColor(Color.BLUE);
>
>                 Coordinate[] hullCoords = hullPoly.getCoordinates();
>                 Coordinate c0 = hullCoords[0];
>                 for (int i = 1; i < hullCoords.length; i++) {
>                     gr.fillOval((int)c0.x-4, (int)c0.y-4, 9, 9);
>                     Coordinate c1 = hullCoords[i];
>                     gr.drawLine((int)c0.x, (int)c0.y, (int)c1.x, (int)c1.y);
>                     c0 = c1;
>                 }
>
>                 gr.setColor(Color.MAGENTA);
>                 Coordinate[] merCoords = merPoly.getCoordinates();
>                 c0 = merCoords[0];
>                 for (int i = 1; i < merCoords.length; i++) {
>                     Coordinate c1 = merCoords[i];
>                     gr.drawLine((int)c0.x, (int)c0.y, (int)c1.x, (int)c1.y);
>                     c0 = c1;
>                 }
>
>                 ((Graphics2D)g).drawImage(bufImg, null, 0, 0);
>             }
>         };
>
>         panel.addMouseListener(new MouseAdapter() {
>
>             @Override
>             public void mouseClicked(MouseEvent e) {
>                 generatePolys();
>                 panel.repaint();
>             }
>         });
>
>         panel.setToolTipText("click for new polygon");
>
>         final JFrame frame = new JFrame("MER demo");
>         frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
>         frame.add(panel);
>         frame.setSize(IMGW, IMGW);
>
>         SwingUtilities.invokeLater(new Runnable() {
>
>             public void run() {
>                 frame.setVisible(true);
>             }
>         });
>     }
>
>     private void generatePolys() {
>         hullPoly = randomConvexPoly();
>         merPoly = MinimumEnclosure.computeMER(hullPoly);
>     }
>
>     private Polygon randomConvexPoly() {
>         Random rand = new Random();
>         final Coordinate[] cloud = new Coordinate[10];
>
>         for (int i = 0; i < cloud.length; i++) {
>             cloud[i] = new Coordinate(
>                     CLOUD_MIN + CLOUD_W * rand.nextDouble(),
>                     CLOUD_MIN + CLOUD_W * rand.nextDouble());
>         }
>
>         ConvexHull hull = new ConvexHull(cloud, new GeometryFactory());
>         return (Polygon) hull.getConvexHull();
>     }
>
> }
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>
>  

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

Martin Davis
In reply to this post by triplederby100-propos
On the MinimumDiameter class there is a method getMininumRectangle().  
That should give you what you need.

Martin

[hidden email] wrote:

> I need to find a minimum area bounding box for a given polygon - which
> could be convex or concave. Is this something possible to find using
> JTS? I see that there is a MinimumDiameter class but I am not sure
> if/how it can be used for this purpose. Any pointers are highly
> appreciated.
>
> Jatin
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Minimum Area bounding box

mbedward
2009/6/5 Martin Davis wrote:
> On the MinimumDiameter class there is a method getMininumRectangle().  That
> should give you what you need.

Ah - another hidden gem :-)

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...