2

Voronoi を使用してマップを作成する Java プログラムに取り組んでいます。Voronoi を生成する Java ライブラリを使用していますが、非常に高速です ( http://sourceforge.net/projects/simplevoronoi/ )。

私が直面している問題は、各ポイントを含むポリゴンを作成するために、エッジの左右にあるポイントを知るために、すべてのボロノイ エッジをスキャンする必要があることです。すべてのボロノイ エッジを含むクラスです。

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は、ボロノイ図を生成するためのポイント座標であり、GPolygonから拡張して作成した Polygon クラスですjava.awt.Polygon。これらは私が測定した時間です：

  • ボロノイ時間: 283 mS (ボロノイ図を生成する時間)
  • ポリゴン検索時間: 34589 ミリ秒 (ポリゴンを生成する for ループを完了する時間)
  • ポリゴンの塗りつぶし時間: 390 ミリ秒 (オプションで、ポリゴンを塗りつぶして画像に保存する時間)
  • ポイント数: 26527 (ボロノイが生成されるポイントの数)
  • マップ生成完了
  • ポリゴン数: 26527 (ポリゴン数、各ポイントに 1 つ)

ご覧のとおり、他のループに比べて非常に時間がかかります。どうすれば for ループを高速化できますか? 他にどのような選択肢がありますか? 事前にどうもありがとうございました。

4

3 に答える 3

1

実際には、新しい GPolygon をリストに直接追加するのではなく、for ループ中に変数に格納します。

    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 が LinkedList ではなく ArrayList であることを確認してください。

台詞：

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

polygonsList.get(n) を 1 回だけ呼び出すことで簡略化できます。

さらに、非常に多くのエッジがある場合は、100 ～ 1000 倍高速化できます。

エッジをバケツ ベースのquadtree、ライン クォードツリーまたはバウンディング ボックス クォードツリーのいずれか (私が好む) に保存します。次に、各検索ポイントに対して、四分木はたとえば近くの 16 個のエッジを提供します (バケット サイズ = 16 と仮定)。すべての 10.0000 を反復する必要はなく、16 だけです。

于 2013-06-12T18:41:10.340 に答える