Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-10-17 08:18:16
Hey, very appealing! I have a soft place in my heart for
computational geometry, but it's been a long time since I've studied
it and I'd never seen a voronoi diagram for points *and* line segments
before. So (just guessing when I could look it up), every line
segment gets a perpendicular line through its endpoints and the curved
lines are equidistant between each line segment and its nearest
The voronoi diagram is constructed using the bisectors (the locus of
points equidistant from the two objects) between pairs of objects.
Bisector of two points is a line. While the bisector of two disjoint
segments is a simple curve that may consist up to seven sections (line
or parabola). To simplify everything each segment is divided onto three
parts: two endpoints and segment itself. This way the bisector between
any two objects consists of one section (line or parabola) and falls into
one of four categories:
1) both objects are points - bisector is the line bisecting them;
2) a segment and its endpoint - bisector is the line perpendicular to
segment through endpoint;
3) a segment and disjoint point - bisector is the section of parabola;
4) both objects are segments - bisector is the line segment.
I guess this simplified explanation will help to understand how it
works for people who haven't seen voronoi of segments before.
Indeed, congratulations to student and mentor alike!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk