<b><span class="nw" id="_user_discuss@mail.osgeo.org"></span></b>The question of different methods for point grouping or point collision
keeps coming up on a number of lists. I have created a page on the
OSGeo wiki to try to track some of the methods that folks have come up
with. Right now it is completely empty aside from a title, but
hopefully we can fill it in with some details that have come from this
and previous discussions. As you experiment (or if you have something
that works great) please describe some different approaches (even if
they didn't really work well, just throw in a brief description of why
that path was bad). If you've got something that works great, please
fill in the details and perhaps some snippets of code. As a community,
if y'all pick up on this question coming through the different lists,
hopefully we can build this into a resource we can point folks to
rather than having the same discussions ten times over.
<br><br>The page is at:<br><a href="http://wiki.osgeo.org/index.php/Point_Clustering" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://wiki.osgeo.org/index.php/Point_Clustering</a><br><br><br>
David<br><br><div><span class="gmail_quote">On 10/22/06, <b class="gmail_sendername">Josh Livni</b> <<a href="mailto:josh@livniconsulting.com">josh@livniconsulting.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div link="blue" vlink="purple" lang="EN-US">
<div>
<p><span style="color: rgb(31, 73, 125);">Chris,</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">I
think as long as your algorithm, server or client-side, knows how to turn the interleave
back into lat/lon (so it's a 1:1 mapping), then it doesn't really matter if you
have extra 0's in front or not. The project I used this on was based in
the Pacific Northwest, not globally, and so I never had to deal anything too
far left of the decimal place. </span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">My
script was server-side, and it returned somewhere between 80 100 pts for
every view if there would be more than 100 I'd loop through some of the pts
again with a couple more digits lopped off the interleave (bigger grid). </span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">In
python, an early draft of the main clustering function looked something like
this: <a href="http://rafb.net/paste/results/ePwPB010.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://rafb.net/paste/results/ePwPB010.html</a>
(I think this might be online for just a couple days). Later I added
stuff so you could add to different clusters based on what 'type' of point it
was, so each cluster had only similar points within it
</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">The
script was fast enough and worked great in the map I was using because it
didn't have panning capability. However, I had hoped to use it in a
Google Maps, and like a ka-map style application, you don't want to have to
re-request new points every time you pan the map. Basing it on difference
between pixels implies you could come up with an algorithm that works on the
entire layer for each zoom level. Then you can precalculate, and put the
cluster results in a new table. As people add new pts to the database,
you could either add a trigger if it's a rare occurrence, or deal with the
additional few points manually and re-calculate nightly or whatever. </span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">This
would work great assuming people aren't needing to make arbitrary queries
for subsets of points, but in my case they were, so points really had to be
dynamically created, and I never got around to coming up with a good way to
figure out how to tell how many pts to put on a given screen, and not have to
deal with re-requesting new pts for every major pan action.</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">A
couple weeks ago on #openlayers I was discussing this with bitner, and he had
some great ideas on the topic. He just mentioned another great idea
which is starting a wiki on the topic as you can see I'm certainly no expert
on it, but maybe someone will be able to come up with a wiki link to this
really interesting subject.</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">
-Josh</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<div>
<div style="border-style: solid none none; border-color: rgb(145, 192, 255) -moz-use-text-color -moz-use-text-color; border-width: 1pt medium medium; padding: 3pt 0in 0in;">
<p><b><span style="font-size: 9pt;">From:</span></b><span style="font-size: 9pt;"> Christopher Brown
[mailto:<a href="mailto:chris@basebloc.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">chris@basebloc.com</a>] <br>
<b>Sent:</b> Sunday, October 22, 2006 7:37 AM<br>
<b>To:</b> 'Josh Livni'; <a href="mailto:ka-map-users@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">ka-map-users@lists.maptools.org</a><div><span class="e" id="q_10e70d65ab1ddfe1_1">
<br>
<b>Subject:</b> RE: [ka-Map-users] Efficient Point Collision</span></div></span></p>
</div>
</div><div><span class="e" id="q_10e70d65ab1ddfe1_3">
<p> </p>
<p><span style="font-size: 10pt; color: navy;">Hi Josh,</span></p>
<p><span style="font-size: 10pt; color: navy;">I just read through the whole thread on the PostGIS list more
thoroughly than I did before I made the last post and the discussion was very
interesting especially in relation to breaking the extent into a grid as this
is the only way I can think to reduce the size of the server-side loops. I have
a couple of questions though, the example in the thread states that the
interleave is produced in the following format "42.987654, -072.123456 =>
-07422.192837465564 LLLlLl.LlLlLlLlLlLl" this will work for collision when it
is just a case of number order but for determining which marker is in which
square within a grid wouldn't it need to be in the following format
"042.987654, -072.123456 => -007422.192837465564 LILlLl.LlLlLlLlLlLl" as to
query if a point is somewhere within the extent x1/y1 and x2/y2 we need x and y
to have an equal unit length if we are to achieve this through the interleave
value (as apposed to a series of If statements) by appending zero's to the
front of the value? This way we can determine if the point is within the grid
square extent simply by checking if our point interleave is bigger than extent
interleave one and smaller than extent interleave two.</span></p>
<p><span style="font-size: 10pt; color: navy;">Did you arrive at a final solution after the discussions on this
PostGIS list, if so what was your end solution and how did it work out?</span></p>
<p><span style="font-size: 10pt; color: navy;">Regards,</span></p>
<p><span style="font-size: 10pt; color: navy;">Chris</span></p>
<p><span style="font-size: 10pt; color: navy;"> </span></p>
<div>
<p><span style="font-size: 8pt; color: navy;">~~~~~~~~~~~~~~~~~~~~~~~~~~~</span></p>
<p><span style="font-size: 8pt; color: navy;">Christopher Brown</span></p>
<p><span style="font-size: 8pt; color: navy;">Head of Internet Development</span></p>
<p><span style="font-size: 8pt; color: navy;">Base Bloc Cambodia</span></p>
<p><span style="font-size: 8pt; color: navy;">#33, 123, Phnom Penh, Cambodia. </span></p>
<p><span style="font-size: 8pt; color: navy;">P.O. Box 2086</span></p>
<p><span style="font-size: 8pt; color: navy;"><a href="http://www.basebloc.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">www.basebloc.com</a></span></p>
<p><span style="font-size: 8pt; color: navy;">Mobile (+855) 12 315 302</span><span style="color: navy;"></span></p>
<p><span style="font-size: 8pt; color: navy;">Office (+855) 23 222 015</span></p>
</div>
<p><span style="font-size: 10pt; color: navy;"> </span></p>
<div>
<div style="text-align: center;" align="center"><span style="font-size: 12pt;">
<hr align="center" size="2" width="100%">
</span></div>
<p><b><span style="font-size: 10pt;">From:</span></b><span style="font-size: 10pt;"> Josh Livni
[mailto:<a href="mailto:josh@livniconsulting.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">josh@livniconsulting.com</a>] <br>
<b>Sent:</b> 21 October 2006 22:34<br>
<b>To:</b> 'Christopher Brown'; <a href="mailto:ka-map-users@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">ka-map-users@lists.maptools.org</a><br>
<b>Subject:</b> RE: [ka-Map-users] Efficient Point Collision</span><span style="font-size: 12pt;"></span></p>
</div>
<p> </p>
<p><span style="color: rgb(31, 73, 125);">I
think client side is always going to be slow for large numbers of markers (more
than a few hundred); just downloading all the marker pts and a most basic
javascript to go over them is reasonably time consuming. I personally
think some kind of clustering on server side might be the most reasonable thing
for large numbers of markers. </span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">That
said, one thing that might add to your current method of ordering of markers by
the xcoord, server or client-side, is to order by an interleave instead.
I once implemented something along the lines of what is described here, and it
was quite fast: <a href="http://www.postgis.org/pipermail/postgis-users/2006-March/011430.html" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://www.postgis.org/pipermail/postgis-users/2006-March/011430.html
</a>
</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);">
-Josh</span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<p><span style="color: rgb(31, 73, 125);"> </span></p>
<div>
<div style="border-style: solid none none; border-color: rgb(145, 192, 255) -moz-use-text-color -moz-use-text-color; border-width: 1pt medium medium; padding: 3pt 0in 0in;">
<p><b><span style="font-size: 9pt;">From:</span></b><span style="font-size: 9pt;">
<a href="mailto:ka-map-users-bounces@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">ka-map-users-bounces@lists.maptools.org</a>
[mailto:<a href="mailto:ka-map-users-bounces@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">ka-map-users-bounces@lists.maptools.org</a>] <b>On Behalf Of </b>Christopher
Brown<br>
<b>Sent:</b> Friday, October 20, 2006 11:53 PM<br>
<b>To:</b> <a href="mailto:ka-map-users@lists.maptools.org" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">ka-map-users@lists.maptools.org</a><br>
<b>Subject:</b> [ka-Map-users] Efficient Point Collision</span></p>
</div>
</div>
<p> </p>
<p><span style="font-size: 10pt;">Hi
Guys,</span></p>
<p><span style="font-size: 10pt;">Whilst
we're on the subject I have also been working on a point collision system,
except I'm using addObjectGeo() to lay down the marker instead of any of the
XML related methods. I have the script working fine and it behaves in the same
way as flickr ( <a href="http://flickr.com/map/" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">http://flickr.com/map/</a> )
with discs of relative sizes which show the number of points within. </span></p>
<p><span style="font-size: 10pt;">To
break it down each time a marker is placed it loops through each already placed
marker stored in a makers array to test for collision based on pixel distance
using "var distance = Math.sqrt(Math.pow((Math.pow((thisNodeLeft -
otherNodeLeft),2) + Math.pow((thisNodeTop - otherNodeTop),2)),1));", this
system works great for around 50 markers but often my apps will place 500+
makers which runs just fine until I collision check them as the loop just
becomes huge and obviously causes the browser to hang.</span></p>
<p><span style="font-size: 10pt;">To
counter this I made SQL output the markers in order of their X coordinate then
instead of checking every marker, I just check against the last 10 markers to
me drawn and the last 10 will generally be the closest ones as the X positions
will all be similar if they are colliding, this method works 99% of the time at
scales where the marker density is not too high, but clearly wouldn't work as
it does with flickr when zoomed right out so the density is extremely high and
the disks can contain 100+ markers, I would like to be able to achieve this
effect but just can't think of a way that is both dynamic and not going to
bring the server or the client to a crawl.</span></p>
<p><span style="font-size: 10pt;">I
don't need code, just some inspiration on how to achieve this, all ideas and
suggestions welcome!</span></p>
<p><span style="font-size: 10pt;">Cheers,</span></p>
<p><span style="font-size: 10pt;">Chris</span></p>
<p><span style="font-size: 10pt;"> </span></p>
<p><span style="font-size: 8pt; color: navy;">~~~~~~~~~~~~~~~~~~~~~~~~~~~</span></p>
<p><span style="font-size: 8pt; color: navy;">Christopher Brown</span></p>
<p><span style="font-size: 8pt; color: navy;">Head of Internet Development</span></p>
<p><span style="font-size: 8pt; color: navy;">Base Bloc Cambodia</span></p>
<p><span style="font-size: 8pt; color: navy;">#33, 123, Phnom Penh, Cambodia. </span></p>
<p><span style="font-size: 8pt; color: navy;">P.O. Box 2086</span></p>
<p><span style="font-size: 8pt; color: navy;"><a href="http://www.basebloc.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">www.basebloc.com</a></span></p>
<p><span style="font-size: 8pt; color: navy;">Mobile (+855) 12 315 302</span></p>
<p><span style="font-size: 8pt; color: navy;">Office (+855) 23 222 015</span></p>
<p><span style="font-size: 10pt;"> </span></p>
</span></div></div>
</div>
<br>_______________________________________________<br>ka-Map-users mailing list<br><a onclick="return top.js.OpenExtLink(window,event,this)" href="mailto:ka-Map-users@lists.maptools.org">ka-Map-users@lists.maptools.org</a>
<br><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://lists.maptools.org/mailman/listinfo/ka-map-users" target="_blank">http://lists.maptools.org/mailman/listinfo/ka-map-users</a><br><br><br></blockquote>
</div><br><br clear="all"><br>-- <br>************************************<br>David William Bitner