java - 如何优化这个循环？

Question

我正在开发一个使用 Voronoi 创建 map 的 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 是我创建的一个多边形类，它从java.awt.多边形。这些是我测量的时间:

• Voronoi Time:283 mS(生成 Voronoi 图的时间)
• 多边形搜索时间:34589 毫秒(完成生成多边形的 for 循环的时间)
• 多边形填充时间:390 毫秒(填充多边形并保存到图像的时间，这是可选的)
• 点数:26527(生成 Voronoi 的点数)
• map 生成完成
• 多边形数量: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 倍。