Voronoi by boost geometry

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Voronoi by boost geometry

dxli
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
Reply | Threaded
Open this post in threaded view
|

Re: Voronoi by boost geometry

ravas


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

What is needed to finish the parabola and hyperbola tools?
Reply | Threaded
Open this post in threaded view
|

Re: Voronoi by boost geometry

dxli
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?
Reply | Threaded
Open this post in threaded view
|

Re: Voronoi by boost geometry

ravas