[postgis-users] 'clustering' of points

Markus Schaber schabi at logix-tt.com
Mon Mar 13 01:55:16 PST 2006

Hi, Stephen,

Stephen Woodbridge wrote:
> I remember read somewhere years ago where someone at IBM did some
> interesting things by interleaving the digits of the lat and lon like:
> 42.987654, -072.123456 => -07422.192837465564
>                           LLLlLl.LlLlLlLlLlLl
> L = longitude digits
> l = latitude digits
> The an index was created on the interleaved string. You could then look
> at clustering at different resolutions by dropping digit pairs from the
> right side of the string. For example:

This looks like a Z-Curve index to me. Z-Curve indices belong to the
group of Space-Filling Curve indices (SFC), and are fast and easy to
grasp and implement if you have point-like objects, but one needs a
modified algorithm for good results when large objects have to be indexed.

IMHO, those SFC-indices would be a good supplement to the current R-Tree
GIST indices, but didn't have a close look at implementing them yet.

Markus Schaber | Logical Tracking&Tracing International AG
Dipl. Inf.     | Software Development GIS

Fight against software patents in EU! www.ffii.org www.nosoftwarepatents.org

More information about the postgis-users mailing list