algorithm - 単純な閉じた折れ線生成アルゴリズム

Question

閉じた単純な（自己交差のない）折れ線を生成するアルゴリズムが必要です。それは私のゲームにとって完璧な迷路になるでしょう。

正しいキーワードを教えていただけますか？

Answer 1

1つのアイデア：ランダムなポイントの束を生成し、アルファ形状を使用してそれらを囲みます。

結果のポリゴンがどれだけ「タイト」であるかを決定するために調整できるパラメータがあります。

---

別のアイデア：ランダムな形状の束を生成し（たとえば、ランダムで単純なポリゴンを生成したり、メタボールを使用したり）、それらの和集合を計算します。

ただし、結合が単一の形状にすぎないことを確認するために、いくつかのトリックに頼る必要がある場合があります。

Answer 2

申し訳ありませんが、検索するのに適切なキーワードがありません。

3D の三角形で近似された 3D 地形を想像しようとしています。湖に島がないように湖が等高線内に形成された場合 (湖の輪郭が目的のポリゴンになります)、現実世界の風景に基づいているため、ゲームにとってはおそらくかなり直感的です。

三角形から 3D ランドスケープを作成するためのよく知られたアルゴリズムを見つけることができれば、最高点を見つけて、サイクルの最低点が最大になるように巡回パスを見つけるでしょう。地形によっては、興味深いポリゴンが得られる場合があります。

繰り返しになりますが、これに対する完璧なアルゴリズムはわかりませんが、非常に興味深い質問だと思います。

Answer 3

自己交差しないポリゴンを処理する必要がある幾何学的アルゴリズムの単体テスト用に、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;
    }
}