CODEWITHSUNDEEP
algorithmgraph-theoryvoronoi
M A
M A

Reputation: 33

Convert voronoi edges into polygons

Currently I am trying to get Voronoi polygons dividing a plane of a certain size (e.g. 1000x1000 with 500 random points).

For this purpose, I used Delaunay's triangulation - Bowyer Watson's algorithm. Thanks to this, I am able to generate points and properly connect the edges included in the Voronoi diagram. Unfortunately, in my case, I need a list of polygons (of which each polygon contains a list of its edges).

I tried to create a naive algorithm that would take the edges one by one and look for the next ones to create a final polygon and so on - unfortunately without success. I was also thinking about taking the vertices of the triangles and creating a circle until the polygon is formed (from the existing edges), but I am not sure if this is a good solution?

Is there any way to do it? Or should I use a different algorithm to get the Voronoi polygon list? I have not found a suitable solution to this problem on the Internet, if there is one, I will be grateful for the link

Upvotes: 3

Views: 456

Answers (1)

ravenspoint
ravenspoint

Reputation: 20616

  • Select E an arbitrary edge
  • Add vertices in E to polygon
  • Select point P slightly to one side of E
  • If point inside plane
    • Select one vertex of selected edge
    • Select E2 new edge from vertex with smallest angle on side with point P
    • Add second vertex in E2 to polygon
    • Repeat last two steps until reach other vertex in E
    • Add polygon to solution, if not already included
  • Repeat with point on other side of edge
  • Repeat until all edges processed

enter image description here

Upvotes: 1

Related Questions