1
\$\begingroup\$

I am working on a Java program which creates a map using Voronoi. I am using a Java library which generates Voronoi and it is very fast.

The problem I am facing is that, then, I have to scan every Voronoi edge to know what point is on the left and on the right of the edge to create the polygon which contains each point.

This is the class which contains every Voronoi edge:

public class GraphEdge
{
    public double x1, y1, x2, y2;

    public int site1;
    public int site2;
}

The coordinates x1, y1, x2, y2 are the edge start and end coordinates and site1 and site2 are the indexes of the points which are on the left and on the right of the edge. So, to create the polygon which contains every point I do this:

for(int n = 0; n < xValues.length; ++n){
        polygonsList.add(new GPolygon());
        for(GraphEdge mGraphEdge : edgesList){
            if( (xValues[mGraphEdge.site1] == xValues[n] || xValues[mGraphEdge.site2] == xValues[n])
                && (yValues[mGraphEdge.site1] == yValues[n] || yValues[mGraphEdge.site2] == yValues[n]) ){
                polygonsList.get(n).addPoint((int)mGraphEdge.x1, (int)mGraphEdge.y1);
                polygonsList.get(n).addPoint((int)mGraphEdge.x2, (int)mGraphEdge.y2);
            }
        }
    }

Where xValues and yValues are the points coordinates from which I generate the Voronoi diagram and GPolygon is a Polygon class I created which extends from java.awt.Polygon.

These are the times I measured:

  • Voronoi Time: 283 ms (time to generate Voronoi diagram)
  • Polygon Search Time: 34589 ms (time to complete the for loop which generates the polygons)
  • Polygon Fill Time: 390 ms (time to fill the polygons and save to image, which is optional)
  • Points quantity: 26527 (number of points from which Voronoi is generated)
  • Map Generation Finished
  • Polygon quantity: 26527 (number of polygons, one for each point)

As you can see, the time is really significant compared to the others. How can I speed up the for loop? What other alternatives do I have?

\$\endgroup\$
1
\$\begingroup\$

To improve the speed of your code, you'd really have to profile it, and know what the bottleneck is (use a profiler, and find out in what methods most of the time is spent).

Here's what I would have a look at (no promise it will yield significant improvements).

  • polygonsList.get(n) is evaluated twice per iteration.
  • The polygon class you're using (I assume java.awt.Polygon) takes ints as coordinates, while the library calculates them in doubles. Yo may want to consider writing a custom Polygon class that takes doubles, in order to avoid the casts.
  • if you only need the Polygon class for drawing, you may even forego that entirely and make a class that can draw a line given a GraphEdge. This will avoid creating Polygon objects, and you can reuse the same drawing instance.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.