Неточности округления при объединении областей в Java?

Я работаю с Areas на Java.

Моя тестовая программа рисует три случайных треугольника и объединяет их в один или несколько многоугольников. После того, как Areas объединены .add(), я использую PathIterator для трассировки краев.

Однако иногда объекты Area не будут комбинироваться должным образом... и, как вы можете видеть на последнем изображении, которое я разместил, будут нарисованы дополнительные края.

Я думаю, что проблема вызвана неточностями округления в классе Area Java (когда я отлаживаю тестовую программу, Area показывает пробелы до того, как используется PathIterator), но я не думаю, что 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();
    }
}

Удачный кейс:

успех

Неудачный случай:

сбой


person Peter    schedule 02.03.2012    source источник


Ответы (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));
    }       

вы добавляете на самом деле 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();
    }    

Обратите внимание на сброс пути после каждого цикла.

РЕДАКТИРОВАТЬ: чтобы больше объяснить, откуда берутся неточности, три пути, которые вы пытаетесь объединить. Что делает очевидным, где могут возникнуть ошибки.

Первый путь

Второй путь

Третий путь

person stryba    schedule 04.03.2012
comment
В моей фактической реализации я сбрасываю Path. Наверное, я забыл добавить его в демо... но это не ответ. - person Peter; 04.03.2012
comment
@Peter: Тогда можете ли вы привести реальный пример, который вызывает сбои каждый раз, а не случайным образом, включая фактический источник, который вы используете? - person stryba; 04.03.2012
comment
@Peter: я имею в виду, что я пробовал сотни случайно сгенерированных комбинаций, и ни одна из них не потерпела неудачу после добавления reset. Так что, если вы можете вычислить начальное число для вашего генератора случайных чисел или фактических координат, это было бы неплохо. В противном случае это очень громоздко. - person stryba; 04.03.2012
comment
Интересно. Я провел несколько тестов, и метод .reset() действительно кажется более надежным. Однако в моей реализации (агенты избегают друг друга со скоростными препятствиями) я вижу случайные ошибки, даже несмотря на то, что метод сброса всегда был там. Возможно, ошибки из другого источника. Я сделаю еще несколько тестов. - person Peter; 04.03.2012
comment
я думаю, что @stryba ответил на исходный вопрос. если у вас есть какая-то другая проблема, возможно, было бы лучше в новом вопросе? это немного раздражает/сбивает с толку/несправедливо, когда вопрос переходит от исправления X к пока я прошу вашего внимания, исправьте все ошибки в моем коде... - person andrew cooke; 05.03.2012
comment
@andrewcooke: я не собирался этого делать. Я просто хотел сказать, что проведу дополнительное тестирование, чтобы убедиться, что эта конкретная проблема решена. Если это не так, я обновлю пример. Если проблема кроется в другом месте или если это исправит ее, я приму ответ, предоставленный stryba. - person Peter; 05.03.2012

Я реорганизовал ваш пример, чтобы упростить тестирование, добавив функции обоих ответов. Восстановление triangle.reset(), казалось, устранило артефакты для меня. Кроме того,

  • Создайте графический интерфейс в потоке отправки событий.

  • Для рендеринга расширьте 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 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);
            }
        });
    }
}
person trashgod    schedule 04.03.2012
comment
Я использую активный рендеринг в своем приложении через переопределенный JPanel. В демо я хотел, чтобы все было просто. Кроме того, проблема заключается в расчете, а не в рендеринге... Я использую края для дальнейших вычислений после того, как они взяты из PathIterator. - person Peter; 05.03.2012

Я поиграл с этим и нашел хакерский способ избавиться от них. Я не уверен на 100%, что это сработает во всех случаях, но может.

Прочитав, что Area.transform упоминает JavaDoc

Преобразует геометрию этой области, используя указанный AffineTransform. Геометрия преобразуется на месте, что навсегда изменяет замкнутую область, определяемую этим объектом.

У меня была догадка, и я добавил возможность вращать область, удерживая клавишу. По мере вращения области «внутренние» края начали медленно исчезать, пока не остался только контур. Я подозреваю, что «внутренние» ребра на самом деле являются двумя ребрами, очень близкими друг к другу (поэтому они выглядят как одно ребро), и что вращение области вызывает очень небольшие неточности округления, поэтому вращение как бы «плавит» их вместе.

Затем я добавил код для поворота области очень маленькими шагами для полного круга при нажатии клавиши, и похоже, что артефакты исчезли:

введите здесь описание изображения

Изображение слева — это область, построенная из 10 различных случайных треугольников (я увеличил количество треугольников, чтобы чаще получать «неудачные» области), а справа — та же самая область после поворота на 360 градусов в очень с небольшим шагом (10000 шагов).

Вот фрагмент кода для поворота области небольшими шагами (меньшее количество шагов, чем 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);
        }

Как я уже говорил, я не уверен, что это работает во всех случаях, и количество необходимых шагов может быть намного меньше или больше в зависимости от сценария. YMMV.

person esaj    schedule 04.03.2012
comment
если это проблема, то более простой способ ее устранения — никогда не генерировать две строки, которые точно перекрываются. вы можете сделать это, изменив random.nextInt(400) на 400*random.nextDouble() - в интервале 0-400 двойников намного больше, чем чтений, поэтому вероятность точного совпадения становится незначительной. - person andrew cooke; 04.03.2012
comment
попытка того, что я предлагаю, не решает проблему, кстати. - person andrew cooke; 04.03.2012
comment
Это умное решение, но осуществимо ли оно в вычислительном отношении? Моя программа будет делать МНОГО таких вычислений. - person Peter; 04.03.2012
comment
@Peter: Не с 10000 шагов вращения на область (это заняло пару секунд на каждую область на моем собственном компьютере), хотя я не проверял минимальное количество шагов, когда лишние края полностью исчезают, я просто вытащил 10000 шагов из моей шляпы. Если фактическое требуемое количество шагов намного меньше, это может быть выполнимым, в зависимости от ваших требований к скорости. - person esaj; 04.03.2012
comment
@Peter: Я проверил еще немного, кажется, что иногда лишние края исчезают всего за 3 шага, иногда для этого требуется несколько сотен шагов. Вам, вероятно, понадобится некоторая логика, чтобы проверить, исчезли ли дополнительные ребра, и если нет, сделать еще несколько вращений (возможно, с большим количеством шагов), чтобы величина шага как бы подстраивалась. Интересно, можно ли обнаружить неисправные области, проверив, находится ли какая-либо точка контура внутри какого-либо из образующих его треугольников? - person esaj; 04.03.2012