Rounding Inaccuracies When Combining Areas in Java

Question

I'm working with Areas in Java.

My test program draws three random triangles and combines them to form one or more polygons. After the Areas are .add()ed together, I use PathIterator to trace the edges.

Sometimes, however, the Area objects will not combine as they should... and as you can see in the last image I posted, extra edges will be drawn.

I think the problem is caused by rounding inaccuracies in Java's Area class (when I debug the test program, the Area shows the gaps before the PathIterator is used), but I don't think Java provides any other way to combine shapes.

Any solutions?

Example code and images:

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Area;
import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.util.ArrayList;
import java.util.Random;

import javax.swing.JFrame;

public class AreaTest extends JFrame{
    private static final long serialVersionUID = -2221432546854106311L;


    Area area = new Area();
    ArrayList<Line2D.Double> areaSegments = new ArrayList<Line2D.Double>();

    AreaTest() {
        Path2D.Double triangle = new Path2D.Double();
        Random random = new Random();

        // Draw three random triangles
        for (int i = 0; i < 3; i++) {
            triangle.moveTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
            triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
            triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
            triangle.closePath();
            area.add(new Area(triangle));
        }       

        // Note: we're storing double[] and not Point2D.Double
        ArrayList<double[]> areaPoints = new ArrayList<double[]>();
        double[] coords = new double[6];

        for (PathIterator pi = area.getPathIterator(null); !pi.isDone(); pi.next()) {

            // Because the Area is composed of straight lines
            int type = pi.currentSegment(coords);
            // We record a double array of {segment type, x coord, y coord}
            double[] pathIteratorCoords = {type, coords[0], coords[1]};
            areaPoints.add(pathIteratorCoords);
        }

        double[] start = new double[3]; // To record where each polygon starts
        for (int i = 0; i < areaPoints.size(); i++) {
            // If we're not on the last point, return a line from this point to the next
            double[] currentElement = areaPoints.get(i);

            // We need a default value in case we've reached the end of the ArrayList
            double[] nextElement = {-1, -1, -1};
            if (i < areaPoints.size() - 1) {
                nextElement = areaPoints.get(i + 1);
            }

            // Make the lines
            if (currentElement[0] == PathIterator.SEG_MOVETO) {
                start = currentElement; // Record where the polygon started to close it later
            } 

            if (nextElement[0] == PathIterator.SEG_LINETO) {
                areaSegments.add(
                        new Line2D.Double(
                            currentElement[1], currentElement[2],
                            nextElement[1], nextElement[2]
                        )
                    );
            } else if (nextElement[0] == PathIterator.SEG_CLOSE) {
                areaSegments.add(
                        new Line2D.Double(
                            currentElement[1], currentElement[2],
                            start[1], start[2]
                        )
                    );
            }
        }

        setSize(new Dimension(500, 500));
        setLocationRelativeTo(null); // To center the JFrame on screen
        setDefaultCloseOperation(EXIT_ON_CLOSE);
        setResizable(false);
        setVisible(true);
    }

    public void paint(Graphics g) {
        // Fill the area
        Graphics2D g2d = (Graphics2D) g;
        g.setColor(Color.lightGray);
        g2d.fill(area);

        // Draw the border line by line
        g.setColor(Color.black);
        for (Line2D.Double line : areaSegments) {
            g2d.draw(line);
        }
    }

    public static void main(String[] args) {
        new AreaTest();
    }
}

A successful case:

A failing case:

Answer 1

I played around with this, and found a hacky way of getting rid of these. I'm not 100% sure that this will work in all cases, but it might.

After reading that the Area.transform's JavaDoc mentions

Transforms the geometry of this Area using the specified AffineTransform. The geometry is transformed in place, which permanently changes the enclosed area defined by this object.

I had a hunch and added possibility of rotating the Area by holding down a key. As the Area was rotating, the "inward" edges started to slowly disappear, until only the outline was left. I suspect that the "inward" edges are actually two edges very close to each other (so they look like a single edge), and that rotating the Area causes very small rounding inaccuracies, so the rotating sort of "melts" them together.

I then added a code to rotate the Area in very small steps for a full circle on keypress, and it looks like the artifacts disappear:

The image on the left is the Area built from 10 different random triangles (I upped the amount of triangles to get "failing" Areas more often), and the one on the right is the same Area, after being rotated full 360 degrees in very small increments (10000 steps).

Here's the piece of code for rotating the area in small steps (smaller amounts than 10000 steps would probably work just fine for most cases):

        final int STEPS = 10000; //Number of steps in a full 360 degree rotation
        double theta = (2*Math.PI) / STEPS; //Single step "size" in radians

        Rectangle bounds = area.getBounds();    //Getting the bounds to find the center of the Area
        AffineTransform trans = AffineTransform.getRotateInstance(theta, bounds.getCenterX(), bounds.getCenterY()); //Transformation matrix for theta radians around the center

        //Rotate a full 360 degrees in small steps
        for(int i = 0; i < STEPS; i++)
        {
            area.transform(trans);
        }

As I said before, I'm not sure if this works in all cases, and the amount of steps needed might be much smaller or larger depending on the scenario. YMMV.

Answer 2

I've re-factored your example to make testing easier, adding features of both answers. Restoring triangle.reset() seemed to eliminate the artifatcts for me. In addition,

• Build the GUI on the event dispatch thread.

• For rendering, extend a JComponent, e.g. JPanel, and override paintComponent().

• Absent subcomponents having a preferred size, override getPreferredSize().

• Use RenderingHints.

SSCCE:

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.event.ActionEvent;
import java.awt.geom.AffineTransform;
import java.awt.geom.Area;
import java.awt.geom.Line2D;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import javax.swing.AbstractAction;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JSpinner;
import javax.swing.SpinnerNumberModel;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

/** @see http://stackoverflow.com/q/9526835/230513 */
public class AreaTest extends JPanel {

    private static final int SIZE = 500;
    private static final int INSET = SIZE / 10;
    private static final int BOUND = SIZE - 2 * INSET;
    private static final int N = 5;
    private static final AffineTransform I = new AffineTransform();
    private static final double FLATNESS = 1;
    private static final Random random = new Random();
    private Area area = new Area();
    private List<Line2D.Double> areaSegments = new ArrayList<Line2D.Double>();
    private int count = N;

    AreaTest() {
        setLayout(new BorderLayout());
        create();
        add(new JPanel() {

            @Override
            public void paintComponent(Graphics g) {
                Graphics2D g2d = (Graphics2D) g;
                g2d.setRenderingHint(
                    RenderingHints.KEY_ANTIALIASING,
                    RenderingHints.VALUE_ANTIALIAS_ON);
                g.setColor(Color.lightGray);
                g2d.fill(area);
                g.setColor(Color.black);
                for (Line2D.Double line : areaSegments) {
                    g2d.draw(line);
                }
            }

            @Override
            public Dimension getPreferredSize() {
                return new Dimension(SIZE, SIZE);
            }
        });

        JPanel control = new JPanel();
        control.add(new JButton(new AbstractAction("Update") {

            @Override
            public void actionPerformed(ActionEvent e) {
                create();
                repaint();
            }
        }));
        JSpinner countSpinner = new JSpinner();
        countSpinner.setModel(new SpinnerNumberModel(N, 3, 42, 1));
        countSpinner.addChangeListener(new ChangeListener() {
            @Override
            public void stateChanged(ChangeEvent e) {
                JSpinner s = (JSpinner) e.getSource();
                count = ((Integer) s.getValue()).intValue();
            }
        });
        control.add(countSpinner);
        add(control, BorderLayout.SOUTH);
    }

    private int randomPoint() {
        return random.nextInt(BOUND) + INSET;
    }

    private void create() {
        area.reset();
        areaSegments.clear();
        Path2D.Double triangle = new Path2D.Double();

        // Draw three random triangles
        for (int i = 0; i < count; i++) {
            triangle.moveTo(randomPoint(), randomPoint());
            triangle.lineTo(randomPoint(), randomPoint());
            triangle.lineTo(randomPoint(), randomPoint());
            triangle.closePath();
            area.add(new Area(triangle));
            triangle.reset();
        }

        // Note: we're storing double[] and not Point2D.Double
        List<double[]> areaPoints = new ArrayList<double[]>();
        double[] coords = new double[6];

        for (PathIterator pi = area.getPathIterator(I, FLATNESS);
            !pi.isDone(); pi.next()) {

            // Because the Area is composed of straight lines
            int type = pi.currentSegment(coords);
            // We record a double array of {segment type, x coord, y coord}
            double[] pathIteratorCoords = {type, coords[0], coords[1]};
            areaPoints.add(pathIteratorCoords);
        }

        // To record where each polygon starts
        double[] start = new double[3];
        for (int i = 0; i < areaPoints.size(); i++) {
            // If we're not on the last point, return a line from this point to the next
            double[] currentElement = areaPoints.get(i);

            // We need a default value in case we've reached the end of the List
            double[] nextElement = {-1, -1, -1};
            if (i < areaPoints.size() - 1) {
                nextElement = areaPoints.get(i + 1);
            }

            // Make the lines
            if (currentElement[0] == PathIterator.SEG_MOVETO) {
                // Record where the polygon started to close it later
                start = currentElement;
            }

            if (nextElement[0] == PathIterator.SEG_LINETO) {
                areaSegments.add(
                    new Line2D.Double(
                    currentElement[1], currentElement[2],
                    nextElement[1], nextElement[2]));
            } else if (nextElement[0] == PathIterator.SEG_CLOSE) {
                areaSegments.add(
                    new Line2D.Double(
                    currentElement[1], currentElement[2],
                    start[1], start[2]));
            }
        }
    }

    public static void main(String[] args) {
        EventQueue.invokeLater(new Runnable() {

            @Override
            public void run() {
                JFrame f = new JFrame();
                f.add(new AreaTest());
                f.pack();
                f.setLocationRelativeTo(null);
                f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                f.setResizable(false);
                f.setVisible(true);
            }
        });
    }
}

Answer 3

Here:

    for (int i = 0; i < 3; i++) {
        triangle.moveTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
        triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
        triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
        triangle.closePath();
        area.add(new Area(triangle));
    }       

you are adding in fact 1 triangle in the first loop 2 triangles in the second loop 3 triangles in the third loop

This is where your inaccuracies come from. Try this and see if your problem still persists.

    for (int i = 0; i < 3; i++) {
        triangle.moveTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
        triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
        triangle.lineTo(random.nextInt(400) + 50, random.nextInt(400) + 50);
        triangle.closePath();
        area.add(new Area(triangle));
        triangle.reset();
    }    

Note the path reset after each loop.

EDIT: to explain more where the inaccuracies come from here the three paths you try to combine. Which makes it obvious where errors might arise.