Convert unordered list of points to polygon.

Question

I am using a module for 2d voronoi. And want to get polygons.
The problem is that the module only returns the edges of a voronoi cell.
And the edges are not sorted. So I have points which could make a polygon if they where sorted correct.
But I dont know how to sort them.

Are there any ideas?

Comments

What module are you using?

---

I guess you're using this one: https://github.com/rakai93/godot_voronoi

Looking at the example from https://github.com/JCash/voronoi, looks like you can just iterate through the sites, and then build your polygon from the site's edges.

Here's how he suggests creating triangles (each triangle has a point at the center of the site). You could simply use a bunch of triangles instead of polygons.

void draw_cells(const jcv_diagram* diagram)
{
    // If you want to draw triangles, or relax the diagram,
    // you can iterate over the sites and get all edges easily
    const jcv_site* sites = jcv_diagram_get_sites( diagram );
    for( int i = 0; i < diagram->numsites; ++i )
    {
        const jcv_site* site = &sites[i];

        const jcv_graphedge* e = site->edges;
        while( e )
        {
            draw_triangle( site->p, e->pos[0], e->pos[1]);
            e = e->next;
        }
    }
}

Are you sure the edges of a site aren't sorted? I had a look at how he generates his voronoi diagram, but couldn't tell for sure. If they aren't you can sort them yourself like so:

var diagram = generator.generate_diagram()

# Iterate over sites
for site in diagram.sites():
    var sorted_edges = get_sorted_edges(site)
    # create polygon from sorted edges

function get_sorted_edges(voronoi_site):
    var next_edge = site.edges()[0]
    var sorted_edges = [next_edge]
    var edges_to_sort = site.edges().slice(1, site.edges().size())
    while (edges_to_sort.size() > 0):
        for edge in edges_to_sort:
            if next_edge.end() == edge.start():
                next_edge = edge
                break
        sorted_edges.append(next_edge)
        edges_to_sort.erase(next_edge)

---

Yes I am using the package
I use a polygon2d node and extract the points like this:

var edges = site.edges()

for edge in edges:
    points.append(edge.end()-site.center())

$Polygon.polygon(points)

But this dont shows the polygons correct. So the sites are unordered.
I already tried something simular to your sort function and also tried your implementation. But in both cases the engine stops on the splash screen.
I think that the while loop never finishes.

---

Maybe it's a precision issue when comparing the vectors?

Does it work if you replace if next_edge.end() == edge.start(): with if next_edge.end().distance_to(edge.start()) < 0.2 :

---

Might be. But there are definitly edges with the same points in the list i already tested it.
But maybe sometimes start() and end() are flipped. That would explain why the loop freezes.

---

Tested it. Start and end are sometime flipped

______|__________Start____________|__________End____________
Edge0 |  (188.746689, 462.919708) | (185.655029, 476.426758)
Edge1 |  (170.876312, 477.670715) | (185.655029, 476.426758)

Here are not end() and start() the same but end() and end()

---

Right. How about this:

var diagram = generator.generate_diagram()

# Iterate over sites
for site in diagram.sites():
    var sorted_points = to_sorted_points(site)
    $Polygon.polygon(sorted_points)

function to_sorted_points(voronoi_site):
    var next_edge = site.edges()[0]
    var sorted_points = [next_edge.start()]
    var edges_to_sort = site.edges().slice(1, site.edges().size())
    while (edges_to_sort.size() > 0):
        for edge in edges_to_sort:
            if next_edge.start() == edge.start():
                next_edge = edge
                sorted_points.append(edge.end())
                break
            elif next_edge.start() == edge.end():
                next_edge = edge
                sorted_points.append(edge.start())
                break
        edges_to_sort.erase(next_edge)
    return sorted_points

---

You might have to append the first point at the end if your polygon expects a closed shaped.

---

I solved it by adding an swap method in the c code which swaps start and end. I used this method in your get_sorted_edges.

func get_sorted_edges(site):
    var next_edge = site.edges()[0]
    var sorted_edges = [next_edge]
    var edges_to_sort = site.edges().duplicate().slice(1, site.edges().size())
    var nothing=true
    while (edges_to_sort.size() > 0):
        nothing = true
        for edge in edges_to_sort:
            if equal_vectors(next_edge.end(), edge.start()):
                next_edge = edge
                nothing=false
                break
            elif equal_vectors(next_edge.end(), edge.end()):
                next_edge = edge
                next_edge.swap()
                nothing=false
                break
            if nothing:
                print("Error")
                break
            sorted_edges.append(next_edge)
            edges_to_sort.erase(next_edge)
        return sorted_edges

equal_vectors compares two vectors but ignores very small differences.
nothing is a killswitch for the while loop in case something goes wrong.

And this seems to work.

Answer 1

I finished the project but in case someone has a simular problem.
While reading the documentation of Geometry if found the method convex_hull_2d which could be used because voronoi only produces convex polygons (as far as I know). I haven't tested it but it seems as if this method would solve the problem.