-1

I am writing some 2D graphic software. And in my project i used Voronoi algorithm. And result is correct as I expected (Pic 1). Then i want to add some feature on boundary points just like (Pic 2). So i think i need to implement Concave hull on boundary points and then create arcs on it.

Pic 1. enter image description here

But my concave hull is not working correct because of concavity parameter. What is the best way and best algorithm to transform my software result into Pic 2.

Pic 2. enter image description here

Edmon
  • 108
  • 2
  • 5

2 Answers2

1

You can create a b/w bitmap with the concave hull and compare it with every point of the voronoi diagram. I used a php function imagefilledpolygon in my php implementation contour plot:https://cntm.codeplex.com/.

You can also try this answer and reconstruct voronoi edges at the border, usually infinity edges:Colorize Voronoi Diagram.

Community
  • 1
  • 1
Micromega
  • 12,486
  • 7
  • 35
  • 72
1

You should be able to do a walk around the voronoi looking for vertices with only a single adjacent edge (not a bad idea to start with a vertex that has just one adjacent edge). Find the first one, walk to the next one, then connect the edges with an arc, repeat until your back at the first edge. The algorithm should be rather efficient O(N) if the voronoi is structured as a graph.

The walk:

The walk is done by angle-sorting the edges and taking the next clockwise edge to the one you started on.

For example:

If the angles (in degrees) are 40, 50, 60, 70, and the previus edge was in the direction of the 50, then you would follow the 60 or 40 edge (depending on if you've decided to go clockwise or counterclockwise) but you wouldn't follow the 70 regardless as that leads inside rather than sticking to the outside.

Nuclearman
  • 5,029
  • 1
  • 19
  • 35