Re: [boost] [polygon] [GSOC] voronoi diagram of line segments

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

point(s)?

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!

Thanks.

Best,
Andrii Sydorchuk