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.

Answer 1

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.

Answer 2

Actually, store the new GPolygon into a variable during the for loop rather than add it directly to the list:

    for(int n = 0; n < xValues.length; ++n){
        GPolygon polygon = new GPolygon();
        polygonsList.add(polygon);
        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]) ){
                polygon.addPoint((int)mGraphEdge.x1, (int)mGraphEdge.y1);
                polygon.addPoint((int)mGraphEdge.x2, (int)mGraphEdge.y2);
            }
        }
    }

This way you won't have to call get at all.

Answer 3

• make sure polygonsList is ArrayList, and not LinkedList.

The lines:

polygonsList.get(n).addPoint((int)mGraphEdge.x1, (int)mGraphEdge.y1);
polygonsList.get(n).addPoint

can be simpliefied by calling polygonsList.get(n) only once.

Further you can speed up by a factor 100 - 1000 if you have a really high number of edges,

Store your edges in a bucket based quadtree, either a line quadtree or bounding box quadtree, which I prefer). Then for each search point the quadtree gives you the e.g 16 edges nearby (asuming bucket size = 16). You don't have to iterate of all 10.0000, only for 16.