Weighted Centroidal Voronoi Stippling using JTS

[Hai-Etlik]

I've been wanting to try this for a while now and after attending a talk by Martin Davis about JTS Topology Suite, a Java library he wrote (along with others) for computational geometry, I decided to give it a shot.

Basically, Weighted Centroidal Voronoi Stippling is a way to produce an image like a stipple drawing, with many little dots that get denser to make a dark tone, and wider to make a light tone, and within a tone, are approximately evenly spaced.

Basically it goes like this: 1) Spread out a bunch of points over the area in question. 2) Compute the Voronoi tessellation for the points. 3) Replace the points with the the centroids for the Voronoi polygons, but weight the polygons' areas with a scalar field (Like an inverted greyscale image) 4) Repeat 2 and 3 many times.

My implementation is a bit odd at the moment in that it supports a vector mask (I clip the Voronoi polygons at each step), and it currently uses just a simple function rather than an image. It's also very, very slow: I was able to speed it up a fair bit by splitting the weighted centroid computation across multiple threads but it's still really slow. I compute the centroid by iterating over a grid of points, adding together the point times the weight function, and the weight function by itself, then divide the first sum by the second.

So, here's what I can produce so far:

foo.png

The mask is just an OGC Simple Features WKT string, the weight function is (x/width)^2, there are 6000 stipples, and I gave it 50 iterations. Output is an SVG file which I rendered in Inkscape. The seed points are distributed randomly with a further random rejection factor based on the weight function.

It took several minutes to run but hopefully I can improve it. Eventually I plan to use it to distribute terrain symbology like trees, mountains, hills, etc.

The code is nowhere near ready for distribution but I'll probably release it under the GPL if it ever is.

[Redrobes]

This looks nice but your text fails to say why one might want to use this technique over the usual error distribution ones like say Floyd Steinberg dithering.

[Hai-Etlik]

This looks nice but your text fails to say why one might want to use this technique over the usual error distribution ones like say Floyd Steinberg dithering.

Dithering takes place on a pixel grid while Weighted Voronoi doesn't have a grid, giving it a more natural look. I might switch to a dithering algorithm for the initial placement of points though.

Also, the Voronoi tesselation itself could be handy. I've been thinking of ways to use it for a forest symbolizer by considering inner and outer edges and their orientation.

[Hai-Etlik]

More progress. I've spent most of the intervening time playing with various different ways of getting XML in and out of my program but I've finally got it doing a very basic version of what I'm ultimately after:

I feed in a GML file, it breaks the polygons up using Centroidal Voronoi, and then symbolizes it to an SVG file.

So here's my latest test output:

test.png

[Redrobes]

Right, I think I see what your driving at now. Your using the dot placement as a position for an icon so as to create wide seamless expanse of textured area but not using bitmaps. Although this looks 2D Im guessing that your calculating it in 3D so as to get the Z order correct for the trees. Presumably you could zoom in on an area and it would still be in vector format.

[Ascension]

Fully automated mapping (given some input), pretty cool.

[Hai-Etlik]

Right, I think I see what your driving at now. Your using the dot placement as a position for an icon so as to create wide seamless expanse of textured area but not using bitmaps. Although this looks 2D Im guessing that your calculating it in 3D so as to get the Z order correct for the trees. Presumably you could zoom in on an area and it would still be in vector format.

Actually, after generating the points, I just sort them by their Y coordinates. I am thinking it would be interesting to add a Y shift based on the height of an underlying DEM though. I'm also planning on trying to write some more interesting symbolizers that work by splitting polygons into many smaller, roughly equal size polygons; I think I could manage a way of drawing forests as contiguous entities rather than bunches of individual trees (As in Ascension's recent practice maps)

[RobA]

Actually, after generating the points, I just sort them by their Y coordinates. I am thinking it would be interesting to add a Y shift based on the height of an underlying DEM though. I'm also planning on trying to write some more interesting symbolizers that work by splitting polygons into many smaller, roughly equal size polygons; I think I could manage a way of drawing forests as contiguous entities rather than bunches of individual trees (As in Ascension's recent practice maps)

Use the bottom y coordinate where possible, so different symbols of different heights will stack properly (assuming they all sit on the ground )

-Rob A>

[Hai-Etlik]

Use the bottom y coordinate where possible, so different symbols of different heights will stack properly (assuming they all sit on the ground )

-Rob A>

In this case I have the 'true' place that whatever it is is so I don't need to worry about that at this level. Instead it's a matter of drawing the symbol correctly, which means that the origin for the symbol should be wherever it is (the base of something like a tree or hill)

[Hai-Etlik]

OK, back at this project again and I'm working on importing SVG data into JTS. This is really much harder than it would seem at first as SVG is really, really loose and flexible compared to GIS formats.

So far I've manage to make a little program that loads up an SVG file, looks for paths, and converts them to linestrings or multilinestrings depending on whether it has multiple subpaths. It only understands moveto, lineto, and closepath commands at the moment and chokes on anything else. It then spits it all out in OGC WKT format.

Roughly speaking, that means it takes this:

<path d="M 258.59905,189.69191 80.812204,365.45845 264.65997,692.74788 220.21325,510.92042 519.21841,434.14883 385.87827,246.26045 z" />

Which can be exported from Inkscape, and produces this:

LINESTRING (258.59905 189.69191, 80.812204 365.45845, 264.65997 692.74788, 220.21325 510.92042, 519.21841 434.14883, 385.87827 246.26045, 258.59905 189.69191)

Which can be loaded into at least some GIS software such as OpenJUMP.