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">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">
Christopher Brown</b> <<a href="mailto:chris@basebloc.com">chris@basebloc.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><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;">Hi Josh,</span></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; 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></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; 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></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;">Regards,</span></font></p><span class="q">
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;">Chris</span></font></p>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;"> </span></font></p>
<div>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">~~~~~~~~~~~~~~~~~~~~~~~~~~~</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Christopher Brown</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Head of Internet Development</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Base Bloc Cambodia</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">#33, 123, Phnom Penh, Cambodia.
</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">P.O. Box</span></font><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">
2086</span></font><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;"></span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;"><a href="http://www.basebloc.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">www.basebloc.com
</a></span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Mobile (+855) 12 315 302</span></font><font color="navy"><span style="color: navy;"></span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Office (+855) 23 222 015</span></font></p>
</div>
<p><font color="navy" face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial; color: navy;"> </span></font></p>
</span><div>
<div style="text-align: center;" align="center"><font face="Times New Roman" size="3"><span style="font-size: 12pt;">
<hr align="center" size="2" width="100%">
</span></font></div>
<p><b><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma; font-weight: bold;">From:</span></font></b><font face="Tahoma" size="2"><span style="font-size: 10pt; font-family: Tahoma;"> Josh Livni
[mailto:<a href="mailto:josh@livniconsulting.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">josh@livniconsulting.com</a>] <span class="q"><br>
<b><span style="font-weight: bold;">Sent:</span></b> 21 October 2006 22:34<br></span>
<b><span style="font-weight: bold;">To:</span></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><span style="font-weight: bold;">Subject:</span></b> RE: [ka-Map-users]
Efficient Point Collision</span></font><font size="3"><span style="font-size: 12pt;"></span></font></p>
</div><div><span class="e" id="q_10e707583a45276b_5">
<p><font face="Times New Roman" size="2"><span style="font-size: 11pt;"> </span></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; 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></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; color: rgb(31, 73, 125);"> </span></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; 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></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; color: rgb(31, 73, 125);"> </span></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; color: rgb(31, 73, 125);"> -Josh</span></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; color: rgb(31, 73, 125);"> </span></font></p>
<p><font color="#1f497d" face="Calibri" size="2"><span style="font-size: 11pt; font-family: Calibri; color: rgb(31, 73, 125);"> </span></font></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><font face="Segoe UI" size="1"><span style="font-size: 9pt; font-weight: bold;">From:</span></font></b><font face="Segoe UI" size="1"><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><span style="font-weight: bold;">On Behalf Of
</span></b>Christopher Brown<br>
<b><span style="font-weight: bold;">Sent:</span></b> Friday, October 20, 2006
11:53 PM<br>
<b><span style="font-weight: bold;">To:</span></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><span style="font-weight: bold;">Subject:</span></b> [ka-Map-users] Efficient
Point Collision</span></font></p>
</div>
</div>
<p><font face="Times New Roman" size="2"><span style="font-size: 11pt;"> </span></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">Hi Guys,</span></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">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></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">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></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">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></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">I don't need code, just some inspiration on how to
achieve this, all ideas and suggestions welcome!</span></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">Cheers,</span></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;">Chris</span></font></p>
<p><font face="Arial" size="2"><span style="font-size: 10pt; font-family: Arial;"> </span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">~~~~~~~~~~~~~~~~~~~~~~~~~~~</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Christopher Brown</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Head of Internet Development</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Base Bloc Cambodia</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">#33, 123, Phnom Penh, Cambodia.
</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">P.O. Box</span></font><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">
2086</span></font><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;"></span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;"><a href="http://www.basebloc.com" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">www.basebloc.com
</a></span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Mobile (+855) 12 315 302</span></font></p>
<p><font color="navy" face="Arial" size="1"><span style="font-size: 8pt; font-family: Arial; color: navy;">Office (+855) 23 222 015</span></font></p>
<p><font face="Times New Roman" size="2"><span style="font-size: 10pt;"> </span></font></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