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:

success

A failing case:

failure

stryba · Accepted Answer · 2012-03-05T09:28:45.820

4

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.

First path

Second path

Third path

edited Mar 05 '12 at 09:28

answered Mar 04 '12 at 17:17

stryba

1,979
13
19

In my actual implementation, I reset the Path. I guess I forgot to add it to the demo... but this is not the answer. – Peter Mar 04 '12 at 17:21
@Peter: Then can you provide an actual example that produces failures every time not just randomly, including the actual source you are using? – stryba Mar 04 '12 at 17:25
@Peter: I mean I tried like hundreds of random generated combinations and none failed after adding `reset`. So if you can figure out a seed for your random generator or actual coordinates, that would be nice. It's very cumbersome otherwise. – stryba Mar 04 '12 at 17:31
Interesting. I've done some testing and it does indeed seem more reliable with the `.reset()` method. However, in my implementation (agents avoiding each other with velocity obstacles), I see occasional errors even though the reset method has been there all along. Perhaps the errors are from a different source. I'll do some more testing. – Peter Mar 04 '12 at 17:56
i think @stryba has answered the original question. if you have some other issue perhaps it would be better in a new question? it's a bit annoying/confusing/unfair when a question drifts from "fix X" to "while i have your attention please fix all the bugs in my code"... – andrew cooke Mar 05 '12 at 01:04
@andrewcooke: I had no intention of doing that. I simply meant to say that I'll do some further testing to ensure that this particular problem has been solved. If it hasn't, I'll update the example. If the problem lies elsewhere, or if this fixes it, I'll accept the answer stryba provided. – Peter Mar 05 '12 at 02:16

score 2 · Answer 2 · answered Mar 04 '12 at 23:21

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

I use active rendering in my application via an overridden `JPanel`. In the demo, I wanted to keep it simple. Additionally, the problem is one of calculation and not of rendering... I use the edges for further computation after they're taken from the `PathIterator`. — Peter, Mar 05 '12 at 02:15

score 1 · Answer 3 · answered Mar 04 '12 at 10:56

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:

enter image description here

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.

if that is the problem then a simpler way to remove it is to never generate two lines that overlap exactly. you can do that by changing random.nextInt(400) to 400*random.nextDouble() - there are many more doubles than reads for the interval 0-400 so the chance of an exact match becomes negligable. — andrew cooke, Mar 04 '12 at 11:41
This is a clever solution, but is it computationally feasible? My program will be doing a LOT of these calculations. — Peter, Mar 04 '12 at 16:58
@Peter: Not with 10000 rotation steps per Area (it took a couple of seconds per Area on my own computer), although I didn't test for a minimum amount of steps where the extra edges completely disappear, I just pulled the 10000 steps out of my hat. If the actual number of steps required is much lower, it *could* be feasible, depending on your speed requirement. — esaj, Mar 04 '12 at 17:41
@Peter: I tested a bit more, it seems that sometimes the extra edges disappear with as low as 3 steps, sometimes they require several hundred steps. You'd probably need some logic to check if the extra edges have disappeared, and if not, do some more rotations (probably with more steps), so the step-amount would sort of adjust itself. I wonder if it would be possible to detect "failing" Areas by checking if any of the points in the outline is inside any of the triangles forming it..? — esaj, Mar 04 '12 at 18:02

Rounding Inaccuracies When Combining Areas in Java?

3 Answers3

Linked