distance between two Shapes/Areas in Java?

Question

If I have two java.awt.geom.Area's made out of the union of various simple Shapes (Polygons and Ellipses), is there a method out there to find the distance (i.e. closest distance) between the two Areas?

To clarify: suppose I have two arbitrary Areas, each of which is created from the union of shapes of any sort:

//Define the first area
Area a = new Area(new Ellipse2D.Double(50, 50, 100, 100));
a.add(new Area(new Rectangle2D.Double(100, 100, 100, 100)));

//Define the second area
Area b = new Area(new Ellipse2D.Double(200, 300, 100, 100));
b.add(new Area(new Ellipse2D.Double(250, 250, 100, 100)));

What I want is a method getDistance(Area a, Area b) that gives me a double representing the shortest distance between any point in Area a and any point in Area b. Here's an image of the above two Areas with a line in blue indicating the distance I'm interested in:

Is there a method out there to do this? If not, how might I implement one?

Oestrogen

Answer 1

There doesn't seem to be a method that does that exactly; however, using PathIterators, you should be able to compare point to point along the outline of the shapes and find the distance manually.

http://docs.oracle.com/javase/6/docs/api/java/awt/geom/PathIterator.html

This Wikipedia article describes how you could efficiently implement this to avoid the quadratic obvious implementation.

Protamine

Thanks! The PathIterator works well for my purposes so far, especially the flattened path iterator. – Oestrogen

Answer 2

Use Hausdorff Distance

Check this very clear explanation of how to use hausdorff Distance: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

Classieclassification