<HTML><BODY style="word-wrap: break-word; -khtml-nbsp-mode: space; -khtml-line-break: after-white-space; "><DIV><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><SPAN class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; ">I just spent the last two weeks solving this.<BR class="Apple-interchange-newline"></SPAN></SPAN></SPAN> </DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>In general, clustering is a hard problem. See <A href="http://en.wikipedia.org/wiki/Data_clustering">http://en.wikipedia.org/wiki/Data_clustering</A> for a long overview. Even the basic algorithms (k-means, etc.) usually assume a fixed parameter (k) = the number of clusters you expect.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>It is easier in the plane, though, and my case had some special restrictions that made it pretty simple. Unfortunately, one of those restrictions was that I have discrete zoom levels, so that may not work for you. The other restriction was that at each zoom level, the cluster extents could be defined precisely (basically, it was "how many pixels apart should the clusters be" and "on average, how many meters equal one pixel at that zoom level"). I just ended up merging clusters from the bottom level up until they merged into one cluster.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>What you might end up creating is a dendrogram: <A href="http://en.wikipedia.org/wiki/Dendrogram">http://en.wikipedia.org/wiki/Dendrogram</A>. That will give you all of the information you need to cluster at various levels of granularity, in real time. That is sort of what I ended up with (except the dendrogram is partitioned, instead of storing every level, so we have something like 200,000 rows instead of a million.) Inserts are O(N) unless you have an R-tree index or something.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>It turns out that one of the tricky parts is storing the data relationally. I saw the nested sets method mentioned somewhere; this is great if you never, ever update your tree. The final method I decided on was an ancestor list: tuples of (leaf_id, cluster_id, level). One row for each leaf at each level. (For example, 20,000 leaf nodes at 20 zoom levels give you 400,000 rows.) Make sure you vacuum often, even if you're only inserting new nodes, because updating all of those clusters chews through tuples like nobody's business.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>Point of comparison: I built a dendrogram with 20,000 nodes on a quad-core Xeon 2.66 with 1 GB of RAM in about 1.5 hours.</DIV><DIV><BR class="khtml-block-placeholder"></DIV><DIV>HTH,</DIV><DIV>be</DIV><BR><DIV><DIV>On Mar 8, 2007, at 2:30 PM, Abe Gillespie wrote:</DIV><BR class="Apple-interchange-newline"><BLOCKQUOTE type="cite"><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Hey all,</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">This is definitely off topic so please ignore if you could care less.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I'm not really sure where to go for this advice so PostGIS gets my</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">abuse.<SPAN class="Apple-converted-space"> </SPAN>Sorry.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">I'm looking for a GIS algorithm (or an idea of an implementation) that</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">clumps scattered, overlapping point data into simple clumps that do</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">not overlap.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">For instance:</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Say we have a point for every building and house in a city.<SPAN class="Apple-converted-space"> </SPAN>Initially</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">we start zoomed such that the city boundary is entirely in view.<SPAN class="Apple-converted-space"> </SPAN>At</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">this view I'd like to have single non-overlapping points that</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">represent clumps of buildings.<SPAN class="Apple-converted-space"> </SPAN>Now say a specific clump right</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">downtown gets my attention.<SPAN class="Apple-converted-space"> </SPAN>I want to zoom in there and get a closer</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">look.<SPAN class="Apple-converted-space"> </SPAN>As I zoom in the clumps break apart into new clumps.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Eventually I'll zoom in enough to where the clump points are just each</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">single building.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">At the most extreme zoomed-out level you'd see one single clump point</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">representing every single building (imagine you're zoomed way WAY</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">out).<SPAN class="Apple-converted-space"> </SPAN>At the most extreme zoomed-in level you'd have each individual</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">building point.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">The biggest requirement here is having no points overlapping at any</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">zoom level.<SPAN class="Apple-converted-space"> </SPAN>The exact placement of these clumps is not an issue</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">though it should be roughly the average x,y of all the points the</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">clump represents.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Is there any algorithm in the GIS space that solves this problem?<SPAN class="Apple-converted-space"> </SPAN>It</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">doesn't seem like a very unique problem, but I've never run across it.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Perhaps even PostGIS can do this (though I'm really looking for a</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">general solution)?</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Also, adding to the complexity is the fact that my point locations are</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">dynamic.<SPAN class="Apple-converted-space"> </SPAN>So I couldn't just set up a set of layers for set zoom</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">levels.<SPAN class="Apple-converted-space"> </SPAN>I.e. the algorithm would have to run every time the map is</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">rendered.</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><BR></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">Thanks for your help / ideas!</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">-Abe</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">_______________________________________________</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">postgis-users mailing list</DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><A href="mailto:postgis-users@postgis.refractions.net">postgis-users@postgis.refractions.net</A></DIV><DIV style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><A href="http://postgis.refractions.net/mailman/listinfo/postgis-users">http://postgis.refractions.net/mailman/listinfo/postgis-users</A></DIV> </BLOCKQUOTE></DIV><BR></BODY></HTML>