如何优化此循环？

Question

我正在研究一个使用Voronoi创建地图的Java程序.我正在使用一个生成Voronoi的Java库,它非常快(http://sourceforge.net/projects/simplevoronoi/).

我面临的问题是,然后,我必须扫描每个Voronoi边缘,以了解边缘左边和右边的点,以创建包含每个点的多边形.它是包含每个Voronoi边缘的类:

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

    public int site1;
    public int site2;
}

坐标x1, y1, x2, y2是边缘开始和结束坐标,site1并且site2是边缘左侧和右侧的点的索引.因此,要创建包含每个点的多边形,我会这样做:

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

在哪里xValues和yValues是我生成Voronoi图的点坐标,并且GPolygon是我创建的Polygon类,它是从java.awt.Polygon.这些是我测量的时间:

• Voronoi时间: 283 mS(生成Voronoi图的时间)
• 多边形搜索时间: 34589 mS(完成生成多边形的for循环的时间)
• 多边形填充时间: 390 mS(填充多边形并保存到图像的时间,这是可选的)
• 积分数量: 26527(生成Voronoi的点数)
• 地图生成完成
• 多边形数量: 26527(多边形数量,每个点数一个)

正如您所看到的,与其他时间相比,时间非常重要,我如何加快for循环？还有其他选择吗？非常感谢你提前.

Answer 1

嗯,如果表现真的很糟糕,那么现在是思考你选择算法的好时机.您已经注意到输入集中的每个站点周围都有一个多边形 - 或换句话说,形成多边形的边具有相同的站点.

因此,像下面这样简单的东西应该很好地解决它:

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

这是一个近O(n)算法(而不是你的O(n ^ 2)),我估计这应该快约1000倍.