Fast union of shapes in Java

Question

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?

Answer 1

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);