2

我正在开发一个使用 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);
            }
        }
    }

WherexValues和yValues是我生成 Voronoi 图的点坐标，并且GPolygon是我创建的 Polygon 类，它从java.awt.Polygon. 这些是我测量的时间：

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

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

4

3 回答 3

5

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

因此，像以下这样简单的事情应该可以很好地解决它：

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

于 2013-06-12T19:17:12.307 回答
1

实际上，在 for 循环期间将新 GPolygon 存储到变量中，而不是将其直接添加到列表中：

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

这样你就不必调用 get 了。

于 2013-06-12T18:40:22.847 回答
1
  • 确保polygonsList 是ArrayList，而不是LinkedList。

这些行：

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

可以通过只调用一次 polygonsList.get(n) 来简化。

此外，如果您的边数非常多，您可以将速度提高 100 - 1000 倍，

将边缘存储在基于桶的四叉树中，我更喜欢线四叉树或边界框四叉树）。然后对于每个搜索点，四叉树为您提供附近的例如 16 条边（假设桶大小 = 16）。您不必迭代所有 10.0000，只需 16 个。

于 2013-06-12T18:41:10.340 回答