<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:"Segoe UI";
panose-1:2 11 5 2 4 2 4 2 2 3;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoAutoSig, li.MsoAutoSig, div.MsoAutoSig
{mso-style-priority:99;
mso-style-link:"E-mail Signature Char";
margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.E-mailSignatureChar
{mso-style-name:"E-mail Signature Char";
mso-style-priority:99;
mso-style-link:"E-mail Signature";
font-family:"Calibri","sans-serif";}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Arial","sans-serif";
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'>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. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'>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">http://www.postgis.org/pipermail/postgis-users/2006-March/011430.html</a>
<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'>
-Josh<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Calibri","sans-serif";color:#1F497D'><o:p> </o:p></span></p>
<div>
<div style='border:none;border-top:solid #91C0FF 1.0pt;padding:3.0pt 0in 0in 0in'>
<p class=MsoNormal><b><span style='font-size:9.0pt;font-family:"Segoe UI","sans-serif"'>From:</span></b><span
style='font-size:9.0pt;font-family:"Segoe UI","sans-serif"'> ka-map-users-bounces@lists.maptools.org
[mailto:ka-map-users-bounces@lists.maptools.org] <b>On Behalf Of </b>Christopher
Brown<br>
<b>Sent:</b> Friday, October 20, 2006 11:53 PM<br>
<b>To:</b> ka-map-users@lists.maptools.org<br>
<b>Subject:</b> [ka-Map-users] Efficient Point Collision<o:p></o:p></span></p>
</div>
</div>
<p class=MsoNormal><o:p> </o:p></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Hi
Guys,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>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/">http://flickr.com/map/</a> )
with discs of relative sizes which show the number of points within. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>I
don’t need code, just some inspiration on how to achieve this, all ideas and
suggestions welcome!<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Cheers,<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'>Chris<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt;font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>~~~~~~~~~~~~~~~~~~~~~~~~~~~<o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>Christopher Brown<o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>Head of Internet Development<o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>Base Bloc Cambodia<o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>#33, 123, Phnom Penh, Cambodia. <o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>P.O. Box 2086<o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'><a href="http://www.basebloc.com">www.basebloc.com</a><o:p></o:p></span></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>Mobile (+855) 12 315 302</span><o:p></o:p></p>
<p class=MsoAutoSig><span style='font-size:8.0pt;font-family:"Arial","sans-serif";
color:navy'>Office (+855) 23 222 015<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:10.0pt'><o:p> </o:p></span></p>
</div>
</body>
</html>