如何从一组边的起始和结束点数组构建多边形？

Question

我正在使用沃罗诺伊多边形来布置我的地图，我有一个返回多边形边缘列表的函数，所以当绘制边缘时看起来像这样这样，这是我的目标。然而，我需要存储有关每个单独多边形的信息，例如它持有的地形类型，但为此我需要仅凭边缘列表构建多边形。我的问题是如何从边缘列表构建这些多边形？

我可以提供伪代码、C++或Objective-C。

- pasawaya

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
}

- Stickman