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?

in Engine

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, e->pos);
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()
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()`

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

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.