Fast union of shapes in Java

geometry, java, shapes, union

Solution

You can try to create a `java.awt.geom.Path2D` (`Path2D.Float` or `Path2D.Double`), append your Shapes to it and create an Area using that path. This way is much faster than adding shapes to an Area but I'm not 100% sure if the results are exactly the same. Something like:

            List<Shape> shapes = ....
            Path2D path = new Path2D.Float();
            for (Shape shape : shapes) {
              path.append(shape, false);
            }
            Area compound = new Area(path);

Problem

I am working on a library for extracting outlines of SVG images. Using Batik in Java makes the process of transforming the SVG file into expanded shapes (`java.awt.geom.Shape` instances) a charm -- for a relatively complex shape we're on the order of milliseconds for this operation. However, as I need a combined outline, I create a `java.awt.geom.Area` and union each of the shapes using `.add(shape)`. Unexpectedly, this is incredibly slow even for relatively simple shapes. By "incredibly" I mean on the order of 36 seconds to add together 8 shapes of 6-10 points per shape. Running the code with `-Xrunhprof` hints that a majority of time is spent in `java.awt.geom.AreaOp.pruneEdges(..)` with `java.lang.StrictMath.acos` being the biggest culprit. Combining an alternative implementation (`AreaX`) with `FastMath` has only yielded insignificant improvements while my search for Java libraries for handling arbitrary geometrical shapes has come up empty. The question then is, what is the way to go about creating a union of shapes in Java without this insane performance penalty? Is there some library or approach that can help the performance of this -- seemingly -- simple operation?

Original source