Algorithm for constructing a simple closed polygonal curve

Question

I need an algorithm to create a closed simple (without self-intersection) polygonal curve. This would create the perfect maze for my game.

Could you give me the right keywords?

Answer 1

One idea: generate a bunch of random dots, then attach them using alpha shapes .

There is a parameter here that you can adjust to determine how a “dense” resulting polygon is.

---

Another idea: create a bunch of random shapes (for example, create random simpler polygons or use metaballs ), then calculate their union .

You may need to resort to some tricks to make sure that pooling is only one form.

Answer 2

Sorry, I do not have good search keywords.

I am trying to imagine a 3D landscape approximated by triangles in 3d. If the lake formed inside the contours, so that the lake did not have islands, then the contour of the lake would be your desired training ground - and it would probably be intuitive enough for the game, since it was based on the real world.

If you could find well-known algorithms for creating a 3D landscape from triangles, I would find the highest point and find a cyclic path around such that the smallest point of the cycle is maximized. Depending on the area, you can get interesting polygons.

once again - sorry, I don’t know any perfect algorithms for this, but I just think this is a very interesting question.

Answer 3

I wrote the following in C ++ for some unit tests on geometric algorithms that required non-self-intersecting polygons. It was not designed to be effective, not readable, and polygons sometimes have relatively small angles between the edges. See if you like it, expand it if you want. No guarantee.

rpoly.h file:

 #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 = (Ay-py) * (Bx-px) - (By-py) * (Ax-px); if (abs(d) < 1e-14) { return ((Ax <= px && px <= Bx) || (Ax >= px && px >= Bx)) && ((Ay <= py && py <= By) || (Ay >= py && py >= By)); } else return false; } bool edge_intersects_polygon(const Point& A, const Point& B) const { double dx = Bx-Ax; double dy = By-Ay; 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 = (Dy-Cy)*dx - (Dx-Cx)*dy; if (d != 0) { u1 = ((Dx-Cx)*(Ay-Cy) - (Dy-Cy)*(Ax-Cx)) / d; u2 = (dx*(Ay-Cy) - dy*(Ax-Cx)) / 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; } }