Note: these pages are no longer maintained

Never the less, much of the information is still relevant.
Beware, however, that some of the command syntax is from older versions, and thus may no longer work as expected.
Also: external links, from external sources, inside these pages may no longer function.

	recipe #15 Tightly bounded Populated Places
2011 January 28

Previous Slide

Table of Contents

Next Slide

The problem

Yet another problem based on the populated_places dataset. This time the question is:

Identify any possible couple of Populated Places laying at very close distance: < 1 Km

Please note: this problem hides an unpleasant complication.

the Populated Places dataset is in the 4236 SRID (Geographic, WGS84, long-lat)
accordingly to this, distances are naturally measured in decimal degrees
but the imposed range limit is expressed in meters/Km

PopulatedPlace #1	Distance (meters)	PopulatedPlace #2
Vallarsa	49.444299	Raossi
Raossi	49.444299	Vallarsa
Seveso	220.780551	Meda
Meda	220.780551	Seveso
...	...	...

SELECT pp1.name AS "PopulatedPlace #1",
  GeodesicLength(
    MakeLine(pp1.geometry, pp2.geometry))
      AS "Distance (meters)",
  pp2.name AS "PopulatedPlace #2"
FROM populated_places AS pp1,
  populated_places AS pp2
WHERE GeodesicLength(
    MakeLine(pp1.geometry, pp2.geometry)) < 1000.0
  AND pp1.id <> pp2.id
  AND pp2.ROWID IN (
    SELECT pkid
    FROM idx_populated_places_geometry
    WHERE pkid MATCH RTreeDistWithin(
      ST_X(pp1.geometry),
      ST_Y(pp1.geometry), 0.02))
ORDER BY 2;

This time we'll go straight forward to final solution.
I suppose that's now very clear to everyone that using a Spatial Index is absolutely required to get a decently well-performing query.
And that a JOIN between two different instances of the same table is required to perform this kind of Spatial Analysis, and so on ...

So we'll simply focus our attention on the most notable highlights:

the MakeLine() function builds a segment connecting two extreme POINT
the GeodesicLength() function calculates the total length (expressed in meters) for any long-lat LINESTRING.
This function gives very accurate results, because is taken directly on the ellipsoid.
Unhappily, this requires lots of complex calculations, so computing a Geodesic length is intrinsically an heavy (and slow) process.
Anyway, a savvy usage of the Spatial Index strongly reduces complexity.
using the MATCH RTreeDistWithin() clause allows to make a first distance estimation directly on the Spatial Index.
Please note: the 0.02 constant means 2/100 of degree (about 2Km, on the Great Circle).
Coordinates into the Spatial Index are long-lat (this is because Populated Places are into the 4326 SRID), so an angular measure is required here.
defining the pp1.id <> pp2.id clause avoids to evaluate the distance between a Populated Place and itself (not surprisingly, always exactly equal to0.0)

Performing a Spatial query like this one in the most naive way requires an extremely long time, even if you'll use the most recent and powerful CPU.
But carefully applying a little bit of optimization is not too much difficult.
And a properly defined an well optimized SQL query surely runs in the smoothest and fastest way.

Previous Slide

Table of Contents

Next Slide

	Author: Alessandro Furieri a.furieri@lqt.it
	This work is licensed under the Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) license.

	Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.