c++ - エッジの始点と終点の配列からポリゴンを構築するにはどうすればよいですか?

Question

ボロノイ ポリゴンを使用してマップをレイアウトし、ポリゴンのエッジのリストを返す関数を使用しているため、描画するとエッジは次のようになります。これが私の目標でした。ただし、保持する地形のタイプなど、個々のポリゴンに関する情報を保存する必要がありますが、そのためには、エッジのリストのみを指定してポリゴンを構築する必要があります。私の質問は、これらのポリゴンをエッジのリストからどのように構築するのですか?

疑似コード、C++、または Objective-C を受け入れる

Answer 1

リストをトラバースして、各頂点の内積を取ることができます。結果が最も低いベクトルに従って先に進みます。検索を開始したポイントにループバックすると、ポリゴンが見つかりました。

私の C++ はさびているので、質問ごとにいくつかの疑似コードを提供します。パターンは、ポイントに基づいて単一のポリゴンを見つける必要があります。タイプは自明です。

class Point {int x, y;}
class Vector 
{
    Point StartPoint, EndPoint;
    Contains(Vector vector)
    {
        return StartPoint == vector || EndPoint == vector;
    }
}
class Polygon /*Array of Vectors */ 
{  
    TopVector /* Last vector to be added */
}

Polygon findPolygon(Vector startVector)
    Polygon returnValue = new Polygon(startVector);
    do
    {
        Polygon.Add(getLowestDotProduct(vector, getConnectingVectors(vector, vector.EndPoint)))
    } while (!Polygon.TopVector.Contains(startVector));
}

Point [] getConnectingVectors(Vector vector, endPoint)
{
    //find all vectors that start or end at endPoint
}

Vector getLowestDotProduct(Vector startVector, Vector[] connectedVectors)
{
    // get the lowest dot product
}