I have a concave polygon c and a set of points p[]. What I need is to have a set of polygons splitted by the voronoi-diagram.

My problem is the following: I already found a library to calculate the voronoi-graph out of a set of points - but it doesn't require any polygon. It only takes a set of points. The first question is: Can I work with this result or do I have to take care of my concave polygon somehow? What I got as the result is a set of edges (start-position, endposition, direction). Both start- and end-position can be infinite because I made no restrictions for the polygon.

How can I now split the polygon into the different parts of the voronoi diagram?

I'm pretty sure that I can't use this method because I need to include my polygon-structure into it...

How to do this? Can I somehow split my concave polygon to get convex polygons, calculate the voronoi diagram with this and then put them back together?

  • 1
    $\begingroup$ It sounds like what you need is an algorithm to take the intersection of two polygons. This would let you take the intersection of the concave polygon $c$ with each of the Voronoi cells. See this post on stackoverflow for a discussion of such algorithms. $\endgroup$ – Jim Belk Jan 20 '14 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.