एक साधारण बंद बहुभुज वक्र उत्पादन एल्गोरिदम

Question

मुझे एक बंद सरल (कोई आत्म-चौराहे) बहुभुज वक्र उत्पन्न करने के लिए एक एल्गोरिदम की आवश्यकता है। यह मेरे खेल के लिए एक आदर्श भूलभुलैया बना देगा।

आप कृपया मुझे सही कीवर्ड को इंगित कर सकते हैं?

Answer 1

क्षमा करें मेरे पास देखने के लिए आपके पास कोई अच्छा कुंजी शब्द नहीं है।

मैं 3 डी में त्रिकोणों द्वारा अनुमानित कुछ 3 डी इलाके की कल्पना करने की कोशिश कर रहा हूं। यदि समतल के भीतर एक झील बनती है जैसे कि झील के पास कोई द्वीप नहीं था - तो झील की रूपरेखा आपकी वांछित बहुभुज होगी - और यह संभवतः एक गेम देखने के लिए काफी सहज होगी क्योंकि यह वास्तविक दुनिया के परिदृश्य पर आधारित है।

यदि आप त्रिभुजों से 3 डी परिदृश्य बनाने के लिए जाने-माने एल्गोरिदम पा सकते हैं, तो मुझे उच्चतम बिंदु मिलेगा और इस तरह चक्रवात पथ मिलेगा कि चक्र में सबसे निचला बिंदु अधिकतम है। इलाके के आधार पर आपको कुछ दिलचस्प बहुभुज मिल सकते हैं।

एक बार फिर - क्षमा करें मुझे इसके लिए कोई सही एल्गोरिदम नहीं पता है, लेकिन मुझे लगता है कि यह एक बहुत ही रोचक सवाल है।

Answer 2

मैंने ज्यामितीय एल्गोरिदम पर कुछ यूनिट परीक्षणों के लिए सी ++ में निम्नलिखित लिखा है जिसके लिए गैर-आत्म-अंतरंग बहुभुज पर काम करने की आवश्यकता है। यह कुशल होने के लिए डिज़ाइन नहीं किया गया था, कोई पठनीय नहीं है, और बहुभुजों के पास कभी-कभी किनारों के बीच छोटे कोण होते हैं। देखें कि आप इसे पसंद करते हैं, अगर आप चाहें तो इसे बढ़ाएं। कोई वारंटी नहीं

फ़ाइल 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 का उपयोग करें।)।

यद्यपि यह सुनिश्चित करने के लिए कि यूनियन केवल एक ही आकार है, आपको कुछ चाल का सहारा लेना पड़ सकता है।