Convert unordered list of points to polygon.

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By RoniPerson

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?

What module are you using?

Bernard Cloutier | 2020-10-01 13:21

I guess you’re using this one: GitHub - rakai93/godot_voronoi: Godot module computing a Voronoi diagram (based on https://github.com/JCash/voronoi)

Looking at the example from GitHub - JCash/voronoi: A C implementation for creating 2D voronoi diagrams, 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)

Bernard Cloutier | 2020-10-01 14:05

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.

RoniPerson | 2020-10-01 15:20

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 :

Bernard Cloutier | 2020-10-01 15:26

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.

RoniPerson | 2020-10-01 15:50

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()

RoniPerson | 2020-10-01 15:56

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

Bernard Cloutier | 2020-10-01 16:59

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

Bernard Cloutier | 2020-10-01 17:05

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.

RoniPerson | 2020-10-01 18:00

:bust_in_silhouette: Reply From: RoniPerson

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.