Animating a recursive triangulation algorithm using swingworker

Question

This is kind of the next question to the question I asked here about how to draw an applet / window when using SwingWorker

In this particular case, I use the separation and rest algorithm proposed by Guibas and stolfi to compute the Delaunay triangulation with many points, say P.

The algorithm is as follows: 1. If sizeof (p) == 2, add an edge; return 2. If sizeof (p) == 3, add a counterclockwise triangle; return 3. if sizeof (p)> 3, divide (p) into left and right halves. Triangulate individual halves to merge halves together

I have a triangulation class whose triangulation method (as shown in the code block) will implement the division and conquest algorithm (in accordance with the pseudocode provided by Guibas and Stolfi)

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

I have a DrawingPanel that acts like a Canvas class and draws triangles, points on the drawing surface.

I use SwingWorker in my main Triangulate class to call the triangulation method.

Here is the code for 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) {

            }
        }
    };

Now I would like to animate this triangulation, showing the triangulation that appears after the recursive call of the triangulation, and then the merge function.

Does anyone have pointers to help me implement the solution?

I thought about using the publish method and the process in the SwingWorker class, but then I found out that it would be superfluous, since the divide and conquer algorithm directly encounters the final triangulation.

.

Answer 1

. , 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().