Thursday, May 6, 2010

More Random Points in JTS

In my last post I talked about the request on the PostGIS list for a function to generate dot-density maps, and about a JTS class to implement it.

Currently the JTS implementation uses purely random points. Here's what a field of purely random points looks like:



As a few people pointed out, and as is obvious from the image, this doesn't look that great, since there tends to be a lot of clusters and blank areas. This doesn't give a very aesthetic effect when used for cartographic purposes.

So I experimented with a few other options.

Here's random points generated in a grid of cells (one point randomly located in each cell). Better, but there are still clusters and blank areas.


Following an idea by Paul Ramsey, here's a grid where the random points are located in circles centred on each grid cell. This is an improvementl, but still doesn't prevent points from ending up close together.

Next idea: use square cells, but add a "gutter" between each cell. No points are created in the gutter, ensuring that points cannot be closer than the gutter width. In this image the gutter width is 30% of the overall cell width.


Much better, I think. Although, as the gutter size increases, the underlying grid becomes apparent. Here's a 50% gutter:

Maybe's there's still improvements that can be made.... It would be nice to avoid the grid effect, and also to reduce the use of a gutter (which skews the density of the distribution).

As David William Bitner pointed out, these can all be restricted to polygonal areas by simply intersecting the point field with the polygon.

6 comments:

Sebastian Good said...

It seems you're wandering towards a methodology like Latin hypercube. Perhaps a partitioning of the geometry into triangles or grids could still allow more than one point per area?

Dr JTS said...

Wow - first Halton sequences and now Latin hypercubes. Clearly there's some deep waters once you get out of the shallow end of the random points pool...

For me this is really just a pleasant distraction from the mundane chores of geometric programming. So I think I'll be leaving the deep stuff to those better qualified than I am - and a real use case!

vincentp said...

Hi Martin,
From a post on OSGeo's list, an interesting entry linked to your kind-of-random points in plane issue :

http://www.johndcook.com/blog/2009/03/16/quasi-random-sequences-in-art-and-integration/

vincent

Unknown said...

How about Generalized Random Tessellation Stratified (GRTS), AFAIR sort of quad tree meets random points-- results in even distribution of random points:
http://www.epa.gov/nheerl/arm/documents/presents/grts_ss.pdf

Enrico Spinielli said...

Mike Bostock as a nice implementation of Poisson Disc sampling, here is the link to his Visualizing Algorithms. He shows various possibilities and how Bridson’s algorithm is best.
HTH

Dr JTS said...

Thanks for the link. A very nice algorithm, and of course the usual amazing presentation from Bostock.