How to optimize this loop?

Question

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 (http://sourceforge.net/projects/simplevoronoi/).

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. It 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 I can speed up the for loop? What other alternatives I have? Thank you very much in advance.

For optimization of working code, you might consider codereview.stackexchange.com — James Montagne
Try to size the list to the appropriate capacity if you know its final size beforehand. — assylias

meriton meriton · Accepted Answer · 2013-06-12T19:17:12

Erm, if performance is really bad, it is a good time to think about your choice of algorithm. You have already noted that there is a polygon around each site in the input set - or put differently, the edges that form a polygon have an identical site.

Therefore, something as simple as the following should solve it quite nicely:

Map<Integer, List<GraphEdge>> edgesByPolygon = new HashMap<>();
for (GraphEdge edge : edgesList) {
    List<GraphEdge> list = edgesByPolygon.get(edge.site1);
    if (list == null) {
        list = new ArrayList<>();
        edgesByPolygon.put(edge.site1, list);
    }
    list.add(edge);

    list = edgesByPolygon.get(edge.site2);
    if (list == null) {
        list = new ArrayList<>();
        edgesByPolygon.put(edge.site2, list);
    }
    list.add(edge);
}

for (List<GraphEdge> list : edgesByPolygon.valueSet()) {
    // order the edges by adjacency and construct the polygon instance
    // (a naive algorithm will do, as the average number of edges is small)
}

This being a nearly O(n) algorithm (instead of your O(n^2)), I estimate this should be about 1000 times faster.

How to optimize this loop?

3 Answers