Voronoi by boost geometry

starting boost-1.54, there's Voronoi support.

While we can provide Voronoi cells as a feature, Voronoi could be used to detect the closest point pair among points in O(N lg N) time.

To fully support Voronoi, we need parabola and more.

http://www.boost.org/doc/libs/1_54_0/libs/polygon/doc/voronoi_main.htm

related link: http://rosettacode.org/wiki/Voronoi_diagram

What is needed to finish the parabola and hyperbola tools?

Voronoi cells are defined by neighborhood of entities (points, lines, circles, ...).

Therefore, the borders of Voronoi cells are defined by equidistant lines between entities.

1, between a pair of points, the equidistant line is a perpendicular bisector;
2, between a point (or a circle) and a straight line, the equidistant line is a parabola with the the point as focus and the straight line as directrix;
3, between two circles of distinct radii, the equidistant line is a parabola with focii at circle centers and major radius as half of the difference in radii;
4, we probably don't want to handle Voronoi by entities of ellipses/hyperbola/parabola. if we do, probably Bezier is the way to go. Then, we need to improve our Bezier.

ravas wrote

related link: http://rosettacode.org/wiki/Voronoi_diagram

What is needed to finish the parabola and hyperbola tools?

Maybe of interest:
http://www.sciencedirect.com/science/article/pii/S0925772110000982