如何从一组边缘起点和终点构造多边形？

Question

我正在使用Voronoi多边形布局我的地图，并有一个函数返回多边形的边缘列表，所以当绘制边缘看起来像this，这是我的目标。但是，我需要存储有关每个单独多边形的信息，例如它包含的是哪种类型的地形，但为此我只需要给出边界列表来构造多边形。我的问题是如何从边缘列表构建这些多边形？

编辑：
我接受伪，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 
}