一个简单的闭合多边形曲线生成算法

Question

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

请问您能否指导我正确的关键词？

- Hedin

Answer 1

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

有一个参数可以调整，以决定结果多么“紧密”的多边形。

---

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

你可能需要采用一些技巧来确保并集只是一个单一的形状。

- BlueRaja - Danny Pflughoeft

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;
    }
}

- Hendrik

Answer 3

很抱歉我没有任何好的关键词给你查找。

我在想象一些由三角形在3D中逼近的3D地形。如果一个湖泊在轮廓线内形成，使得湖泊没有岛屿-那么湖泊的轮廓线就是您所需的多边形-并且它可能会对游戏产生相当直观的影响，因为它是基于真实世界的景观。

如果您能够找到众所周知的算法来制作由三角形组成的3D地形，我将找到最高点，并找到一个循环路径，使得循环中的最低点被最大化。根据地形的不同，您可能会得到一些有趣的多边形。

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

- Rusty Rob