How to get the points around a voronoi cell?

Question

I am trying to get the points which form a polygon to fill it with some color. I have a set of points and then I calculate the Voronoi Diagram for it. The result is this:

Green points are the points I define and blue points are the calculated vertices for the Voronoi Diagram. I want to fill the polygon which is generated by an specific green point so I need to know which points are around it to form the polygon and fill it.

I have read about Gift Wrapping Algorithm and Convex Hull but it doesn't seems to be what I need. Is there any algorithms to suit this need ? I am programming in C++ but any help in Java or C# would be helpful.

Answer 1

The Gift Wrapping algorithm (which is a convex hull algorithm) is for finding the smallest convex polygon that contains a set of points in the plane. That's not what you want here.

Fortune's algorithm is a good solution for finding the actual boundaries of your Voronoi diagram. It's not a trivial algorithm, but a full pseudocode is provided on the linked Wikipedia page. At the bottom of the Wikipedia page, there are links to implementations of Fortune's algorithm in a few different languages.