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.

Random Points in Polygon in JTS

Recently there was a thread on the PostGIS list about how to create "dot-density" maps. Essentially this involves creating a set of N randomly-placed points which lie within a given polygon.

JTS already has a lot of random shape creation functions provided in the TestBuilder (randomPoints, randomPointsInGrid, randomRadialPoints, randomRectilinearWalk, etc). But they aren't currently exposed as a class in the API. This seemed like a good use case to initiate the development of such a class.

So now JTS has a RandomShapeFactory class. The class allows setting an extent using either a rectangular Envelope or a polygonal geometry, and will create sets of N points within the defined extent.

Here's a screenshot of the TestBuilder showing the new function at work:


Update: it's been pointed out that what is really desired is to have the points evenly distributed through the polygon. This will take a bit more thinking... At least the API won't have to change much to support this.