Java中组合区域时的舍入误差？

Question

我正在使用Java中的Areas。

我的测试程序绘制三个随机三角形并将它们组合成一个或多个多边形。在将Areas相加后，我使用PathIterator来跟踪边缘。

然而，有时候Area对象无法正确组合...正如您在我发布的最后一张图片中所看到的，会出现额外的边缘绘制。

我认为问题是由于Java的Area类中的舍入误差引起的（当我调试测试程序时，在使用PathIterator之前Area显示了间隙），但我不认为Java提供了其他结合形状的方法。

有什么解决方案吗？ 示例代码和图像：

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

一个成功的案例：

一个失败的案例：

- Peter

Answer 1

这里：

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

实际上，在第一个循环中添加了1个三角形，在第二个循环中添加了2个三角形，在第三个循环中添加了3个三角形。

这就是您的不准确之处所在。请尝试此方法，看看您的问题是否仍然存在。

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

请注意每次循环后路径都会重置。

编辑说明：为了更好地解释不准确之处，这里展示了您尝试合并的三条路径。从中可以看出错误可能出现的位置。

- stryba

---

在我的实际实现中，我重置了路径。我猜我忘记把它添加到演示中了...但这不是答案。 - Peter

@Peter：那你能提供一个实际的例子吗？这个例子不仅要每次都会失败，而且还需要包括你正在使用的实际源代码。 - stryba

@Peter：我的意思是，我尝试了数百个随机生成的组合，在添加“reset”后没有一个失败。所以如果你能找出你的随机生成器的种子或实际坐标，那就太好了。否则这将非常麻烦。 - stryba

有趣。我进行了一些测试，使用.reset()方法似乎确实更可靠。然而，在我的实现中（代理通过速度障碍物避免彼此），即使重置方法一直存在，我仍然会偶尔看到错误。也许这些错误来自不同的源头。我将进行更多的测试。 - Peter

我认为@stryba已经回答了原问题。如果您有其他问题，也许在一个新的问题中会更好？当一个问题从“修复X”漂移到“顺便请修复我的代码中的所有错误”时，这有点令人烦恼/困惑/不公平... - andrew cooke

@andrewcooke：我没有意图那样做。我只是想说，我会进行进一步的测试以确保这个特定的问题已经解决。如果没有解决，我会更新示例。如果问题出在其他地方，或者如果这解决了问题，我会接受stryba提供的答案。 - Peter

Answer 2

我已经重构了你的示例，以使测试更加容易，并添加了两个答案的特性。恢复triangle.reset()似乎对我消除了这些问题。此外，

• 在事件分派线程上构建GUI。

• 为渲染，扩展JComponent，例如JPanel，并覆盖paintComponent()。

• 如果没有子组件具有首选大小，则覆盖getPreferredSize()。

• 使用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 https://dev59.com/wGHVa4cB1Zd3GeqPjRIF */
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);
            }
        });
    }
}

- trashgod

---

我在我的应用程序中通过重写JPanel使用主动渲染。在演示中，我想保持简单。此外，问题是计算问题而不是渲染问题...我在从PathIterator获取边缘后将其用于进一步计算。 - Peter

Answer 3

我尝试了一下，找到了一种摆脱这些问题的方法。我不能百分之百肯定这种方式在所有情况下都有效，但可能有效。

在阅读了Area.transform的Java文档之后，我有一个想法：

使用指定的仿射变换转换此区域的几何图形。 几何图形会在原地被转换，从而永久更改由该对象定义的包围区域。

我猜测添加了旋转区域的可能性，通过按住键盘上的某个键来实现。当区域旋转时，“向内”的边缘开始逐渐消失，直到只剩下轮廓线。我怀疑“向内”的边缘实际上是非常靠近彼此的两条边（因此它们看起来像单条边），旋转区域会导致非常小的舍入误差，所以旋转会将它们融合在一起。

然后，我添加了一段代码，在按键时，以非常小的步骤旋转区域一圈，结果似乎没有产生缺陷：

左侧的图像是由10个不同的随机三角形构建的区域（我增加了三角形的数量，以更频繁地获得“失败”的区域），右侧的图像是相同的区域，在非常小的增量（10000步）中旋转360度后的结果。

这是旋转区域的代码片段（比10000步更小的步骤对于大多数情况来说可能完全可以胜任）：

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

就像我之前所说的，我不确定这在所有情况下都有效，所需步骤的数量可能会因情况而异。你的经验可能会有所不同。

- esaj

---

如果这是问题的话，那么一个更简单的解决方法就是永远不生成完全重叠的两行。你可以通过将random.nextInt(400)更改为400*random.nextDouble()来实现这一点——在0-400区间内有许多double值，而不是int值，因此完全匹配的机会变得微不足道。 - andrew cooke

尝试我建议的做法并不能解决问题，顺便提一句。 - andrew cooke

这是一个聪明的解决方案，但它在计算上可行吗？我的程序将会进行很多这样的计算。 - Peter

@Peter：不是每个区域10000个旋转步骤（在我的电脑上每个区域需要几秒钟），虽然我没有测试额外边缘完全消失的最小步数，我只是随口说了10000步。如果实际所需步数要少得多，根据您的速度要求，这可能是可行的。 - esaj

@Peter：我进行了更多的测试，似乎有时候只需要3步就可以消除额外的边缘，有时则需要几百步。你可能需要一些逻辑来检查是否已经消除了额外的边缘，如果没有，就要进行更多的旋转（可能需要更多的步骤），这样步骤数量就会自动调整。我想知道是否可能通过检查轮廓中的任何点是否在形成它的三角形中的任何一个内部来检测“失败”的区域..？ - esaj