Rounding up inaccuracies when combining areas in Java?

Question

I work with Areas in Java.

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

Sometimes, however, Area objects will not merge as they should ... and, as you can see in the last image I posted, additional edges will be highlighted.

I think the problem is due to rounding errors in the Java Area class (when debugging the Area test program, it shows spaces before using PathIterator ), but I don't think Java provides any other way to combine the 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(); } } 

Success case:

Bad case:

Answer 1

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 actually add 1 triangle in the first cycle 2 triangles in the second cycle 3 triangles in the third cycle

This is where your inaccuracies come from. Try this and see if your problem 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(); } 

Pay attention to the reset path after each cycle.

EDIT: to explain more where inaccuracies come from here are three paths that you are trying to combine. This makes it obvious where errors may occur.

Answer 2

I repeated your example to simplify testing by adding the functions of both answers. Restoring triangle.reset() seemed to fix artifatcts for me. Besides,

• Create a GUI in the event dispatch thread .

• To render, expand a JComponent , for example. JPanel and override paintComponent() .

• Missing 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

I played with this and found a hacker way to get rid of them. I am not 100% sure that this will work in all cases, but it can be.

After reading Area.transform, JavaDoc mentions

Transforms the geometry of this Region using the specified AffineTransform. The geometry is transformed into a place, which constantly changes the closed region defined by this object.

I had a hunch and added the ability to rotate the Area by holding the key. As the Area rotates, the “inner” edges began to slowly disappear until only the outline remained. I suspect that the “inner” edges are actually two edges very close to each other (therefore, they look like one edge), and that the rotation of the Region causes very small rounding errors, so the rotating view “fuses” them together.

Then I added code to rotate the area in very small steps for a full circle when a key is pressed, and it looks like artifacts disappear:

The image on the left is an area built of 10 different random triangles (I increased the number of triangles to get “glitches” of the areas more often), and on the right - the same Area, after it was completely rotated 360 degrees with a very small step (10,000 steps).

Here is the part of the code for turning the area in small steps (in most cases there will be less than 10,000 steps):

  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, I'm not sure if this works in all cases, and the number of steps required can be much less or more depending on the scenario. YMMV.