A simple closed polygonal curve generation algorithm

Question

I need an algorithm to generate a closed simple (no self-intersections) polygonal curve. It would make a perfect labyrinth for my game.

Can you please point me to the correct keywords?

Orlon

Answer 1

One idea: generate a bunch of random points, then enclose them using alpha shapes.

There's a parameter you can tune to decide how "tight" the resulting polygon is.

---

Another idea: generate a bunch of random shapes (eg. generate random simpler polygons, or use metaballs), then compute their union.

You may need to resort to some tricks to make sure the union is only a single shape, though.

Satanism

Answer 2

Sorry I don't have any good key-words for you to look up.

I'm trying to imagine some 3d terrain approximated by triangles in 3d. If a lake formed within the contours such that the lake had no islands - then the outline of the lake would be your desired polygon - and it would probably be fairly intuitive for a game seeing as it's based on real world landscape.

If you could find well known algorithms for making the 3d landscape out of triangles, I would find the highest point and find a cyclic path around such that the lowest point in the cycle is maximized. Depending on the terrain you may get some interesting polygons.

once again - sorry I don't know any perfect algorithms for this but I just think it's a very interesting question.

Sparling

Answer 3

I wrote the following in C++ for some unit tests on geometrical algorithms which required non-self-intersecting polygons to work on. It was not designed to be efficient, no readable, and also the polygons sometimes have rather small angles between edges. See if you like it, extend it if you wish. No warranties.

File 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;
    }
}

Saffier