анимация алгоритма рекурсивной триангуляции с использованием свингера - PullRequest
Новая
       39

анимация алгоритма рекурсивной триангуляции с использованием свингера

5 голосов
/ 15 марта 2012

Это своего рода дополнительный вопрос к вопросу, который я задавал более здесь относительно того, как рисовать апплет / окно при использовании SwingWorker

В этом конкретном случае я используюалгоритм «разделяй и властвуй», предложенный Гибасом и Столфи для вычисления триангуляции Делоне для набора точек, скажем, P.

Алгоритм выглядит следующим образом: 1. Если sizeof (p) == 2, добавить ребро;return 2. Если sizeof (p) == 3, добавить ориентированный против часовой стрелки треугольник;верните 3. если sizeof (p)> 3, разделите (p) на левую и правую половинки.Триангуляция отдельных половин слияние половин вместе

У меня есть класс триангуляции, метод триангуляции которого (как показано в блоке кода) будет реализовывать алгоритм «разделяй и властвуй» (согласно псевдокоду, предоставленному Гибасом и Столфи)

public QuadEdge[] partition(List<PlanarPoint> list) {
        QuadEdge[] convexHullEdges = new QuadEdge[2];
        if (list.size() == 2) {
            //Add edge
        } else if (list.size() == 3) {
            //Add a counter-clockwise oriented triangle
        } else if (list.size() > 3) {
            List<PlanarPoint> leftHalf = new ArrayList<PlanarPoint>();
            List<PlanarPoint> rightHalf = new ArrayList<PlanarPoint>();
            //Divide the list of points into 2 halves
            QuadEdge[] leftDelaunay = triangulate(leftHalf);
            QuadEdge ldo = leftDelaunay[0];
            QuadEdge ldi = leftDelaunay[1];

            QuadEdge[] rightDelaunay = triangulate(rightHalf);
            QuadEdge rdi = rightDelaunay[0];
            QuadEdge rdo = rightDelaunay[1];
            // Merge the two halves
            merge(ldo,ldi,rdi,rdo);
        }
        return convexHullEdges;
    }

У меня есть DrawingPanel, который действует как класс Canvas и рисует треугольники, точки на поверхности рисования.

Я использую SwingWorker в своем основном классе Triangulate для вызова триангуляцииmethod.

Вот код для SwingWorker: 

private class GuibasStolfiWorker extends
            SwingWorker<List<QuadEdge>, PlanarPoint> {

        @Override
        protected List<QuadEdge> doInBackground() throws Exception {
           // retrieve the points added by the user on the drawing surface
            List<PlanarPoint> list = drawingPanel.pointsList();
            Trinagulation dt = new Triangulation(list);
            dt.preprocess(); // removes duplicate points
            dt.triangulate();// calls the recursive divide and conquer algorithm
            return dt.edgeList(); //returns the list of edges which form the final triangulation.
        }

        protected void process(List<PlanarPoint> chunks) {
            drawingPanel.repaint();
        }

        public void done() {
            try {
                List<QuadEdge> triangles = get();
                drawingPanel.setTrianglesList(triangles);
                drawingPanel.repaint();
            } catch (InterruptedException e) {

            } catch (ExecutionException e) {

            }
        }
    };

Теперь я хотел бы анимировать эту триангуляцию, показывая триангуляцию, появляющуюся после рекурсивного вызова триангуляции, а затем слияниеfunction.

У кого-нибудь есть какие-нибудь указатели, которые помогут мне реализовать решение?

Я думал об использовании метода publish и process в классе SwingWorker, но потом выяснил, что это будет излишним, посколькуАлгоритм разделяй и властвуйh финальная триангуляция.

Заранее спасибо.

1 Ответ

2 голосов
/ 15 марта 2012

Комментарии на правильном пути.Я бы попытался сделать так, чтобы метод partition() сообщал о каждом треугольнике, который он вычисляет (каждый раз, когда он проходит 3 точки), обратно в SwingWorker, который затем publish() получает треугольник.Примерно так: 

public interface TriangleListener {
    public void reportTriangle(final QuadEdge triangle);
}

public QuadEdge[] partition(List<PlanarPoint> list, TriangleListener listener) {
    QuadEdge[] convexHullEdges = new QuadEdge[2];
    if (list.size() == 2) {
        //Add edge
    } else if (list.size() == 3) {
        //Add a counter-clockwise oriented triangle
        listener.reportTriangle(new QuadEdge(list));
    }
    ...
}

private class GuibasStolfiWorker extends
        SwingWorker<Void, QuadEdge> implements TriangleListener 
{
    ...
    protected void process(List<QuadEdge> chunks) {
        drawingPanel.addTrianglesToList(chunks);

        drawingPanel.repaint();
    }

    public void done() {
        // Nothing to do - panel has all triangles already
    }

    @Override
    public void reportTriangle(final QuadEdge triangle) {
        publish(triangle);
    }
}

public interface TriangleLsitener {
    public void reportTriangle(final QuadEdge triangle);
}

Извините, если я не правильно понял нюансы - я предполагаю, что QuadEdge - это треугольник, и все такое ...

И определеннопримите во внимание совет @ kleopatra - возможно, конструктор вашего SwingWorker мог бы взять List<PlanarPoint> вместо того, чтобы получить от панели в doInBackground().

...