用Voronoi图的边构造多边形

Question

我正在编写一个Java程序，它使用Voronoi创建一个地图。我正在使用一个生成Voronoi的Java库，它非常快。

我面临的问题是，然后，我必须扫描每个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扩展的多边形类。

这是我测量的时间：

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

正如你所看到的，与其他时间相比，时间真的很重要。如何加快for循环？我还有别的选择吗？

Answer 1

为了提高代码的速度，您必须对代码进行分析，并了解瓶颈是什么(使用分析器，并找出大部分时间用在哪些方法中)。

下面是我要看的内容(没有承诺会带来重大的改进)。

• 每次迭代对polygonsList.get(n)进行两次评估。
• 您使用的多边形类(我假设是java.awt.Polygon)以ints作为坐标，而库在doubles中计算它们。Yo可能会考虑编写一个自定义多边形类，该类需要双倍，以避免转换。
• 如果您只需要多边形类来绘制，您甚至可以完全放弃这一点，并创建一个类，该类可以绘制给定GraphEdge的线。这将避免创建Polygon对象，并且可以重用相同的绘图实例。