java.awt.geom.Area object duplicating points?

Question

I work with a lot of 2D floating point polygons. I came up with a use case where I need to subtract one from another, so I thought I'd use java.awt.geom.Area. I create an Area object with four points:

100.0, 50.0
150.0, 0.0
151.41421356237308, 2.8284271247461112
99.99999999999973, 54.242640687118936

And independent of how I order those points when creating the Area, I get back the following:

SEG_MOVETO, 150.0, 0.0
SEG_LINETO, 100.0, 50.0
SEG_LINETO, 99.99999999999973, 54.24264068711893
SEG_LINETO, 99.99999999999974, 54.24264068711893
SEG_LINETO, 151.41421356237308, 2.8284271247461112
SEG_LINETO, 150.0, 0.0
SEG_CLOSE, 150.0, 0.0

Note the almost identical dual 99.99999999999973, 54.24264068711893 coordinates.

Any clues in how to avoid that would be most welcome. Here's the code:

import java.awt.geom.Area;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;

class Main {
    public static final void main( String args[] ) {
        double[] myPoly = {100.0, 50.0, 150.0, 0.0, 151.41421356237308, 2.8284271247461112, 99.99999999999973, 54.242640687118936};
        final Area myArea = makeArea(myPoly);
        System.out.println(areaToString(myArea));
    }

    private static Area makeArea(double coords[]) {
        final Path2D path = new Path2D.Double();
        path.moveTo(coords[0], coords[1]);
        for (int i = 2; i < coords.length; i+=2) {
            path.lineTo(coords[i], coords[i+1]);
        }
        path.closePath();
        return new Area(path);
    }

    private static String areaToString(final Area area) {
        final StringBuffer out = new StringBuffer("Area [\n");
        double []pt = new double[6];
        for (PathIterator pi = area.getPathIterator(null); !pi.isDone(); pi.next()) {
            int type = pi.currentSegment(pt);
            out.append(type).append(", ").append(pt[0]).append(", ").append(pt[1]).append("\n");
        }
        return out.append(']').toString();
    }
}

score 0 · Answer 1 · answered Jun 07 '16 at 22:12

If you take a close look at those values, you will find that 99.99999999999973 and 99.99999999999974 are within one unit of least precision (ULP) of each other. This is a common problem with floating-point numbers. You can not represent every number exactly.

If you change things up and directly print out the Path2D object with a similar method, none of the duplicating happens.

The javadoc of Area states

An Area may take more path segments to describe the same geometry even when the original outline is simple and obvious. The analysis that the Area class must perform on the path may not reflect the same concepts of "simple and obvious" as a human being perceives.

So all in all, what likely happens is that area optimizes the Path object, and thus introduces the artifacts you see. I have not dug into the source code of Area to find out how exactly this particular decomposition of the path is chosen.

Looks like that bullet of the Area javadoc was written for exactly this case. Still, seems odd that the Area object would insert a point that's within one ULP. Anyway, the downside is that if you do successive `Area.subtract()` operations with objects like this, the duplicates accumulate. C'est la vie. I just wrote the code to filter out the dups when I convert it back from an Area to a polygon. Thanks for the tip. — Billy Hinners, Jun 08 '16 at 01:33
When using floating-point numbers, you will often have those problems. I would hazard a guess that Area does some internal computations, and then due to precision losses the points no longer match and the path is split. You might want to re-construct a path that combines points that are within certain ULPs of each other for better printing. — Polygnome, Jun 08 '16 at 07:48

java.awt.geom.Area object duplicating points?

1 Answers1