java - 如何优化此循环？

我正在研究使用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是我创建的从java.awt.Polygon扩展的Polygon类。这些是我测量的时间：


Voronoi时间：283 mS（生成Voronoi图的时间）
多边形搜索时间：34589毫秒（完成用于生成多边形的for循环的时间）
多边形填充时间：390毫秒（填充多边形并保存到图像的时间，这是可选的）
点数：26527（生成Voronoi的点数）
地图生成完成
多边形数量：26527（多边形数量，每个点一个）


如您所见，与其他时间相比，时间确实很重要，我如何加快for循环的速度？我还有什么其他选择？提前非常感谢您。

最佳答案

嗯，如果性能真的很差，那么现在是考虑选择算法的好时机。您已经注意到输入集中每个位置周围都有一个多边形-换句话说，形成多边形的边具有相同的位置。

因此，如下所示的简单操作应该可以很好地解决它：

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倍。

关于java - 如何优化此循环？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17072832/