# Convert unordered list of points to polygon.

Attention Topic was automatically imported from the old Question2Answer platform.

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

``````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

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.