単純な閉じた多角形カーブ生成アルゴリズム

Question

閉じた単純な（自己交差しない）多角形カーブを生成するアルゴリズムが必要です。それは私のゲームに完璧な迷路を作るだろう。

正しいキーワードに私を指すしてくださいことはできますか？

Answer 1

申し訳ありませんあなたを検索するための良いキーワードがありません。

私は3Dで三角形で近似したいくつかの3D地形を想像しようとしています。もし湖が輪郭内に形成されていて、湖に島がないとすれば、湖の輪郭があなたの望むポリゴンになります。そして、実世界の景観に基づいて見ているゲームにとってはかなり直感的でしょう。

3Dランドスケープを三角形から外すためのよく知られたアルゴリズムが見つかった場合は、最も高い点を見つけて周りの周回経路を見つけてサイクルの最下点が最大になるようにします。地形に応じて、面白いポリゴンを得ることができます。

もう一度申し訳ありませんが、私はこれについて完璧なアルゴリズムはわかりませんが、とても興味深い質問だと思っています。

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

ひとつのアイデア：alpha shapesを使用してそれらを囲み、その後、ランダムな点の束を生成します。

結果として得られるポリゴンの「タイト」を決めるためのパラメータがあります。

---

もう一つのアイデア：ランダムな形状の束生成、その後、compute their union（例えば、ランダムな単純なポリゴンを生成する、またはmetaballsを使用してください。）。

ユニオンが単一のシェイプであることを確認するには、いくつかのトリックに頼る必要があります。