Page 1 of 3 123 LastLast
Results 1 to 10 of 23

Thread: Weighted Centroidal Voronoi Stippling using JTS

  1. #1
    Software Dev/Rep Hai-Etlik's Avatar
    Join Date
    May 2009
    Location
    48° 28′ N 123° 8′ W
    Posts
    1,333
    Blog Entries
    1

    Default Weighted Centroidal Voronoi Stippling using JTS

    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:

    Click image for larger version. 

Name:	foo.png 
Views:	2340 
Size:	98.3 KB 
ID:	35062

    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.

  2. #2
    Administrator Redrobes's Avatar
    Join Date
    Dec 2007
    Location
    England
    Posts
    7,193
    Blog Entries
    8

    Default

    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.

  3. #3
    Software Dev/Rep Hai-Etlik's Avatar
    Join Date
    May 2009
    Location
    48° 28′ N 123° 8′ W
    Posts
    1,333
    Blog Entries
    1

    Default

    Quote Originally Posted by Redrobes View Post
    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.
    Last edited by Hai-Etlik; 04-13-2011 at 04:15 PM.

  4. #4
    Software Dev/Rep Hai-Etlik's Avatar
    Join Date
    May 2009
    Location
    48° 28′ N 123° 8′ W
    Posts
    1,333
    Blog Entries
    1

    Default

    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:

    Click image for larger version. 

Name:	test.png 
Views:	339 
Size:	401.2 KB 
ID:	35255

  5. #5
    Administrator Redrobes's Avatar
    Join Date
    Dec 2007
    Location
    England
    Posts
    7,193
    Blog Entries
    8

    Default

    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.

  6. #6
    Community Leader Facebook Connected Ascension's Avatar
    Join Date
    Jun 2008
    Location
    St. Charles, Missouri, United States
    Posts
    8,392

    Default

    Fully automated mapping (given some input), pretty cool.
    If the radiance of a thousand suns was to burst at once into the sky, that would be like the splendor of the Mighty One...I am become Death, the Shatterer of worlds.
    -J. Robert Oppenheimer (father of the atom bomb) alluding to The Bhagavad Gita (Chapter 11, Verse 32)


    My Maps ~ My Brushes ~ My Tutorials ~ My Challenge Maps

  7. #7
    Software Dev/Rep Hai-Etlik's Avatar
    Join Date
    May 2009
    Location
    48° 28′ N 123° 8′ W
    Posts
    1,333
    Blog Entries
    1

    Default

    Quote Originally Posted by Redrobes View Post
    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)

  8. #8

    Default

    Quote Originally Posted by Hai-Etlik View Post
    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>

  9. #9
    Software Dev/Rep Hai-Etlik's Avatar
    Join Date
    May 2009
    Location
    48° 28′ N 123° 8′ W
    Posts
    1,333
    Blog Entries
    1

    Default

    Quote Originally Posted by RobA View Post
    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)

  10. #10
    Software Dev/Rep Hai-Etlik's Avatar
    Join Date
    May 2009
    Location
    48° 28′ N 123° 8′ W
    Posts
    1,333
    Blog Entries
    1

    Default

    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:
    Code:
    <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:
    Code:
    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.

Page 1 of 3 123 LastLast

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •