I managed to build the Voronoï diagram of n points using Fortune's algorithm.
This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point).
I'd like to restrict this diagram to a specific polygon P, by creating new vertices at the intersections of the polygon and the inifinite half-edges and connecting them in order to close all cells of the diagram.
If P is convex, I think I can perform it in O(n log p) where p is the size of P, by finding the intersecting edge of P for each half-edge.
My questions are :
- Is there some way to do better in the case of a convex polygon ?
- Can we do something in the general case (any polygon, not convex)