From: Aaron Spike <aaron@ek...>  20070425 00:15:16

Bill Baxter wrote: > On 4/25/07, bulia byak <buliabyak@...> wrote: >> On 4/24/07, Terry Brown <terry_n_brown@...> wrote: >>> I don't think inkscape has that. Looks like the POVray pattern >>> 'Crackle': >>> >>> http://www.povray.org/documentation/view/3.6.1/372/ >>> >>> clip >>> Mathematically, the set crackle(p)=0 is a 3D Voronoi diagram of a >>> field of semi random points and crackle(p) < 0 is the distance from >>> the set along the shortest path (a Voronoi diagram is the locus of >>> points equidistant from their two nearest neighbors from a set of >>> disjoint points, like the membranes in suds are to the centers of >>> the bubbles). >> By the way, this might make a useful Python effect for Inkscape: Fill >> the inside of a path with random points and build a Voronoi diagram >> (as a set of polygon paths) of these points, or of the path's nodes, >> or both. Any takers? >> >> See http://en.wikipedia.org/wiki/Voronoi >> > > Doing Voronoi diagrams (and delaunay triangulations) robustly is > tricky. Simpler algorithms tend to barf on input that has too many > collinear points, or has points placed exactly on a grid. And the > textbook implementations usually avoid constraints altogether. > But the Triangle lib by Jonathan Shewchuk handles all that and more > quite beautifully and can create both Voronoi diagrams and Delaunay > triangulations of the interiors of arbitrary polygons. (Arbitrary in > the sense of being concave and having holes. Probably not > selfintersecting ones, though I haven't tried that). Livarot used to do Voronoi diagrams. http://livarot.sourceforge.net/ :) Aaron Spike 