Algoritmo de generación de curva poligonal cerrada simple

Question

Necesito un algoritmo para generar una curva poligonal cerrada (sin autointersecciones). Sería un laberinto perfecto para mi juego.

¿Me podría apuntar a las palabras claves correctas?

Answer 1

Lo siento, no tengo buenas palabras clave para que busques.

Estoy tratando de imaginar un terreno tridimensional aproximado por triángulos en 3d. Si se formara un lago dentro de los contornos de tal manera que el lago no tuviera islas, entonces el contorno del lago sería el polígono deseado, y probablemente sería bastante intuitivo para un juego ya que está basado en el paisaje del mundo real.

Si pudieras encontrar algoritmos bien conocidos para hacer el paisaje tridimensional a partir de triángulos, encontraría el punto más alto y encontraría una ruta cíclica alrededor de modo que se maximice el punto más bajo del ciclo. Dependiendo del terreno, puedes obtener algunos polígonos interesantes.

una vez más, lo siento, no conozco ningún algoritmo perfecto para esto, pero creo que es una pregunta muy interesante.

Answer 2

Escribí lo siguiente en C++ para algunas pruebas unitarias de algoritmos geométricos que requerían que los polígonos que no se intersecaban solos trabajaran. No fue diseñado para ser eficiente, no legible, y también los polígonos a veces tienen ángulos bastante pequeños entre los bordes. Vea si le gusta, extiéndalo si lo desea. Sin garantías

Archivo 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

Una idea: generar un montón de puntos al azar, entonces se encierra usando alpha shapes.

Hay un parámetro que puede ajustar para decidir qué tan "apretado" es el polígono resultante.

---

Otra idea: generar un grupo de formas aleatorias , entonces compute their union (por ejemplo, generar polígonos simples aleatorias, o utilizar metaballs.).

Puede que necesite recurrir a algunos trucos para asegurarse de que la unión tiene una sola forma.