How do I construct polygons from an array of edge start points and end points?

Question

I am using Voronoi polygons to lay out my map, and have a function that returns a list of edges of the polygons, so when drawn the edges look like this, which was my goal. However, I need to store information about each individual polygon, such as what type of terrain it holds, but for this I need to construct polygons given only the list of edges. My question is how do I construct these polygons from a list of edges?

I'm open to pseudocode, C++, or Objective-C

Answer 1

You could traverse the list and take the dot product of each vertex. Follow the vector with the lowest result and move on, once you've looped back onto a the point you started searching, you've found your polygon.

My C++ is rusty, so I'll provide you with some pseudo code per your question. The pattern should find a single polygon based on a point. The types are fairly self explanatory:

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
}