algorithm - 一种简单的封闭多边形曲线生成算法

Question

我需要一种算法来生成封闭的简单（无自相交）多边形曲线。这将为我的游戏打造一个完美的迷宫。

你能指点我正确的关键字吗？

Answer 1

一个想法：生成一堆随机点，然后使用alpha 形状将它们包围起来。

您可以调整一个参数来决定生成的多边形有多“紧密”。

---

另一个想法：生成一堆随机形状（例如，生成随机更简单的多边形，或者使用metaballs），然后计算它们的 union。

不过，您可能需要使用一些技巧来确保联合只是一个单一的形状。

Answer 2

我用 C++ 编写了以下关于几何算法的单元测试，这些算法需要非自相交的多边形才能工作。它的设计目的不是高效，不可读，而且多边形有时在边缘之间具有相当小的角度。看看你喜不喜欢，如果你愿意，可以扩展它。没有保证。

文件rpoly.h：

#include <vector>
#include <list>
#include <algorithm>
#include <iterator>
#include <stdexcept>
#include <iostream>

using namespace std;

struct HalfEdge
{
    HalfEdge() {};
    HalfEdge(size_t start, size_t end) : start(start), end(end) {};

    size_t start;
    size_t end;
};

typedef vector<HalfEdge>::iterator edge_iterator;
typedef vector<HalfEdge>::const_iterator const_edge_iterator;

template <class Point>
struct non_intersecting_edges
{
    non_intersecting_edges(const vector<Point>& vertices, vector<HalfEdge>& edgelist)
        : vertices(vertices), edgelist(edgelist) {}

    void operator() (size_t i)
    {
        const Point &p = vertices[i];
        for (edge_iterator it=edgelist.begin(); it!=edgelist.end(); ++it)
        {
            HalfEdge edge = *it;
            Point start_vertex = vertices[it->start];
            Point end_vertex   = vertices[it->end];

            if (point_intersects_edge(p, start_vertex, end_vertex))
                return; // skip this point

            if(!edge_intersects_polygon(start_vertex, p) &&
               !edge_intersects_polygon(end_vertex, p) )
            {
                edgelist.push_back( HalfEdge(i,it->end) );
                it->end = i;
                return;
            }
        }

        cerr << "[rpoly] Warning: no possible edge found for vertex " << p << endl;
    }

private:
    bool point_intersects_edge(const Point& p, const Point& A, const Point& B) const
    {
        double d = (A.y-p.y) * (B.x-p.x) - (B.y-p.y) * (A.x-p.x);
        if (abs(d) < 1e-14)
        {
            return ((A.x <= p.x && p.x <= B.x) || (A.x >= p.x && p.x >= B.x))
                && ((A.y <= p.y && p.y <= B.y) || (A.y >= p.y && p.y >= B.y));
        }
        else return false;
    }

    bool edge_intersects_polygon(const Point& A, const Point& B) const
    {
        double dx = B.x-A.x;
        double dy = B.y-A.y;

        for (const_edge_iterator it=edgelist.begin(); it!=edgelist.end(); ++it)
        {
            double d,u1,u2;

            const Point &C = vertices[it->start];
            const Point &D = vertices[it->end];

            d  = (D.y-C.y)*dx - (D.x-C.x)*dy;

            if (d != 0) {
                u1 = ((D.x-C.x)*(A.y-C.y) - (D.y-C.y)*(A.x-C.x)) / d;
                u2 = (dx*(A.y-C.y) - dy*(A.x-C.x)) / d;

                if (u1 > 0 && u1 <= 1 && u2 > 0 && u2 <= 1) // half-open edges
                    return true;
            }
        }

        return false;
    }

    const vector<Point>& vertices;
    vector<HalfEdge>& edgelist;
};

bool start_index_less(const HalfEdge &a, const HalfEdge &b)
{
    return a.start < b.start;
}

bool start_index_equals(const HalfEdge &a, size_t idx)
{
    return a.start == idx;
}

template <class Point>
struct random_point
{
    Point operator () () const
    {
        return Point( rand() % 1000 - 500, rand() % 1000 - 500 );
    }
};

const HalfEdge& find_edge(const vector<HalfEdge>& list, size_t start)
{
    for (const_edge_iterator it=list.begin(); it!=list.end(); ++it)
        if (it->start == start) return *it;

    throw runtime_error("find_edge: requested edge not found");
}

/// \brief Outputs random, non self-intersecting polygon with \a N vertices
template <class Point, class OutputIterator>
void generate_random_polygon(unsigned int N, OutputIterator out)
{
    if (N<3) return;

    vector<Point> vertices(N);
    generate(vertices.begin(), vertices.end(), random_point<Point>());

    vector<HalfEdge> edgelist(2);
    edgelist.reserve(N);
    edgelist[0] = HalfEdge(0,1);
    edgelist[1] = HalfEdge(1,0);

    non_intersecting_edges<Point> generator(vertices,edgelist);
    for (size_t i=2; i<vertices.size(); ++i)
        generator(i);

    int index=0;
    for (unsigned int i=0; i<N; ++i)
    {
        const HalfEdge &edge = find_edge(edgelist, index);
        *out++ = vertices[edge.start];
        index = edge.end;
    }
}

Answer 3

抱歉，我没有任何好的关键字供您查找。

我试图想象一些由 3d 中的三角形近似的 3d 地形。如果在等高线内形成了一个湖泊，使得该湖没有岛屿——那么湖泊的轮廓将是你想要的多边形——并且对于基于现实世界景观的游戏来说，这可能是相当直观的。

如果你能找到用三角形制作 3d 风景的众所周知的算法，我会找到最高点并找到一条循环路径，以使循环中的最低点最大化。根据地形，您可能会得到一些有趣的多边形。

再一次 - 抱歉，我不知道任何完美的算法，但我只是认为这是一个非常有趣的问题。