간단한 닫힌 다각형 곡선 생성 알고리즘

Question

닫힌 단순 (자체 교차 없음) 다각형 곡선을 생성하는 알고리즘이 필요합니다. 그것은 내 게임을위한 완벽한 미로를 만들 것입니다.

은 올바른 키워드 날 지점시겠습니까?

Answer 1

죄송합니다. 귀하가 찾으실만한 핵심 단어가 없습니다.

3D로 삼각형으로 근사 된 일부 지형을 상상해 봅니다. 호수가 윤곽선에 형성되어 호수에 섬이없는 경우 - 호수의 윤곽이 원하는 다각형이 될 것입니다 - 실제 세계 경관을 기반으로 한 게임을 보는 것은 상당히 직관적입니다.

삼각형에서 3D 화면을 없애기위한 잘 알려진 알고리즘을 찾을 수 있다면 가장 높은 지점을 찾아 주위의 순환 경로를 찾아주기의 가장 낮은 지점을 최대화 할 수 있습니다. 지형에 따라 흥미로운 다각형을 얻을 수 있습니다.

다시 한번 미안하지만이 알고리즘에 대한 완벽한 알고리즘을 모르지만 매우 흥미로운 질문이라고 생각합니다.

Answer 2

필자는 non-self-intersecting polygon이 작동해야하는 기하학적 알고리즘에 대한 일부 단위 테스트를 위해 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를 사용하여 묶 임의 점의 무리를 생성합니다.

결과 다각형이 얼마나 단단한 지 결정할 수있는 매개 변수가 있습니다.

---

또 다른 아이디어는 : (. 예를 들어 임의 단순한 다각형을 생성하거나 metaballs 사용) 임의 모양의 무리를 생성 한 후 compute their union.

유니온이 하나의 셰이프 만 사용하고 있는지 확인하려면 몇 가지 트릭을 사용해야 할 수도 있습니다.