Questions on Segment Voronoi diagram implementation details

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
Report Content as Inappropriate

Questions on Segment Voronoi diagram implementation details

Amit Pendharkar

I am working on the Segment Voronoi Diagrams. As per the paper "A robust and efficient implementation for the segment Voronoi diagram' by Menelaos Karavelas, the segment voronoi creation algorithm has following four distinct steps.

1. Find the first conflict of the site S with the existing voronoi skeleton.
2. Find the entire conflict region of S with the existing voronoi skeleton.
3. Construct the Voronoi diagram.
4. Update the location data structure.

As per the implementation, the voronoi adaptor actually works with the segment delaunay graph. Whenever you insert a site, that site is actually inserted in a segment delaunay graph.

My questions are
1. In which file is the code that actually finds the first conflict and then the entire conflict region?(first two steps) I specifically want the approximate line numbers.
There are several files that look related to this like -

I want to know the file name and how the code lines at that location work (i.e what variables hold, what the functions do etc)

2. Any inputs on how exactly it builds the voronoi diagram and how it updates & stores the data structure.

All the inputs are greatly appreciated.

Thanks & Regards,
Amit Pendharkar