Ein einfacher Algorithmus zur Erzeugung einer geschlossenen polygonalen Kurve

Question

Ich brauche einen Algorithmus, um eine geschlossene, einfache Polygonalkurve (ohne Selbstdurchschnitte) zu erzeugen. Es wäre ein perfektes Labyrinth für mein Spiel.

Können Sie mir bitte auf die richtigen Keywords zeigen?

Answer 1

Entschuldigung, ich habe keine guten Schlüsselwörter für Sie, um nachzuschlagen.

Ich versuche mir etwas 3D-Gelände näherungsweise durch Dreiecke in 3d vorstellen. Wenn sich in den Konturen ein See formte, so dass der See keine Inseln hatte - dann wäre der Umriss des Sees Ihr gewünschtes Polygon - und es wäre wahrscheinlich ziemlich intuitiv für ein Spiel, da es auf der realen Welt basiert.

Wenn Sie wohlbekannte Algorithmen zum Erstellen der 3D-Landschaft aus Dreiecken finden könnten, würde ich den höchsten Punkt finden und einen zyklischen Pfad um so finden, dass der tiefste Punkt im Zyklus maximiert wird. Je nach Gelände können Sie interessante Polygone erhalten.

noch einmal - Entschuldigung, ich kenne keine perfekten Algorithmen dafür, aber ich denke nur, dass es eine sehr interessante Frage ist.

Answer 2

Ich schrieb das Folgende in C++ für einige Komponententests auf geometrische Algorithmen, die nicht selbstschneidende Polygone zur Bearbeitung benötigten. Es wurde nicht entworfen, um effizient zu sein, nicht lesbar, und auch die Polygone haben manchmal ziemlich kleine Winkel zwischen den Kanten. Sehen Sie, wenn es Ihnen gefällt, erweitern Sie es, wenn Sie es wünschen. Keine Garantien.

Datei 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

Eine Idee: ein Bündel von zufälligen Punkten erzeugen, dann schließen Sie sie alpha shapes verwenden.

Es gibt einen Parameter, den Sie einstellen können, um zu entscheiden, wie "eng" das resultierende Polygon ist.

---

Ein andere Idee: ein Bündel von zufälligen Formen erzeugt , dann compute their union (zB erzeugt zufälliges einfaches Polygone, oder verwenden Sie metaballs.).

Sie müssen möglicherweise auf einige Tricks zurückgreifen, um sicherzustellen, dass die Vereinigung nur eine einzige Form hat.