<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:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40"
xmlns:ns0="http://schemas.microsoft.com/office/2004/12/omml">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><o:SmartTagType
namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="Street"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="address"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="City"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="country-region"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="place"/>
<!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--a:link
{mso-style-priority:99;}
span.MSOHYPERLINK
{mso-style-priority:99;}
a:visited
{mso-style-priority:99;}
span.MSOHYPERLINKFOLLOWED
{mso-style-priority:99;}
p.MSOAUTOSIG
{mso-style-priority:99;}
li.MSOAUTOSIG
{mso-style-priority:99;}
div.MSOAUTOSIG
{mso-style-priority:99;}
span.E-MAILSIGNATURECHAR
{mso-style-priority:99;}
/* Font Definitions */
@font-face
{font-family:Wingdings;
panose-1:5 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
@font-face
{font-family:Calibri;}
@font-face
{font-family:"Segoe UI";}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
p.MsoAutoSig, li.MsoAutoSig, div.MsoAutoSig
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
span.E-mailSignatureChar
{font-family:Calibri;}
span.EmailStyle19
{mso-style-type:personal;
font-family:Arial;
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal;
font-family:Calibri;
color:#1F497D;}
span.EmailStyle21
{mso-style-type:personal-reply;
font-family:Arial;
color:navy;}
@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><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Hi Guys,<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Thanks for all the input. I think
interleave is exactly what I was looking for to change 95% success rate at
medium point density to 100% whilst still only looping the ten closest markers,
this will save wasting one of the ten passes on a marker whose Y is way off.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Now just onto the problem of how to crunch
though 500+ markers and have each marker run a loop against all the other
markers already placed to check for collision, this could amount to over
125,000 processes which is obviously way to many. I could check for collision
on the server instead of the client by passing the cellSize along with the Ajax
call, but as I see it this will just move the problem rather than solve it, the
server could probably chew it’s way through that in a testing environment
but with multiple users it could easily choke and this will be a common procedure.
<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>But none the less I think most of the leg
work is going to have to be done by the server, I was thinking along the lines
of making a virtual grid based on the extent passed during the call, then on
the server side run a loop to establish which square on the grid each marker
falls, then only run a collision check on markers which share the same square
this could get the number of processes below a couple thousand which would be acceptable,
the problem with this is markers that are on the very edge of a square on the
grid will still collide in some cases. In this case we could load all markers
that are within x(x being the radius of the largest possible disk size) number
of pixels from the edge of the grid into an additional array and then run a separate
loop to check for the collision of these. Do you think this would be a sensible
way to go or still to heavy? I don’t want to write what will be quite a
complex script just to discover when finished it’s slower than a Skoda
with square wheels.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Steve: Thanks for the input on my distance
calculation that’s why I included it </span></font><font size=2
color=navy face=Wingdings><span style='font-size:10.0pt;font-family:Wingdings;
color:navy'>J</span></font><font size=2 color=navy face=Arial><span
style='font-size:10.0pt;font-family:Arial;color:navy'>, in my current script this
doesn’t run on every marker against every other marker, just the ten
closest (Which is still a huge process on 500+ markers). To be honest I just
asked one of the GIS guys how to find the distance between two points, then
changed the equation into code (I should know better by now) without really
thinking about it. How about this as a more simplified alternative:<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>function getDistance(x1,y1,x2,y2)<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>{<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'> var d =
Math.round(Math.sqrt(((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1))));<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'> if
(isNaN(d)) d = 0;<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'> return d;<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>}<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Or do you think this is still too heavy to
be run a couple of thousand times server side incorporated into the grid idea
above?<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Regards,<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'>Chris<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<div>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>~~~~~~~~~~~~~~~~~~~~~~~~~~~<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Christopher Brown<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Head of Internet Development<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Base Bloc <st1:country-region w:st="on"><st1:place
w:st="on">Cambodia</st1:place></st1:country-region><o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>#33, 123, <st1:place w:st="on"><st1:City
w:st="on">Phnom Penh</st1:City>, <st1:country-region w:st="on">Cambodia</st1:country-region></st1:place>.
<o:p></o:p></span></font></p>
<p class=MsoAutoSig><st1:address w:st="on"><st1:Street w:st="on"><font size=1
color=navy face=Arial><span style='font-size:8.0pt;font-family:Arial;
color:navy'>P.O. Box</span></font></st1:Street><font size=1 color=navy
face=Arial><span style='font-size:8.0pt;font-family:Arial;color:navy'> 2086</span></font></st1:address><font
size=1 color=navy face=Arial><span style='font-size:8.0pt;font-family:Arial;
color:navy'><o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>www.basebloc.com<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Mobile (+855) 12 315 302</span></font><font
color=navy><span style='color:navy'><o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Office (+855) 23 222 015<o:p></o:p></span></font></p>
</div>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<div>
<div class=MsoNormal align=center style='text-align:center'><font size=3
face="Times New Roman"><span style='font-size:12.0pt'>
<hr size=2 width="100%" align=center tabindex=-1>
</span></font></div>
<p class=MsoNormal><b><font size=2 face=Tahoma><span style='font-size:10.0pt;
font-family:Tahoma;font-weight:bold'>From:</span></font></b><font size=2
face=Tahoma><span style='font-size:10.0pt;font-family:Tahoma'> Josh Livni
[mailto:josh@livniconsulting.com] <br>
<b><span style='font-weight:bold'>Sent:</span></b> 21 October 2006 22:34<br>
<b><span style='font-weight:bold'>To:</span></b> 'Christopher Brown';
ka-map-users@lists.maptools.org<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:
12.0pt'><o:p></o:p></span></font></p>
</div>
<p class=MsoNormal><font size=2 face="Times New Roman"><span style='font-size:
11.0pt'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;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></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;color:#1F497D'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;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></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;color:#1F497D'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;color:#1F497D'> -Josh<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;color:#1F497D'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 color="#1f497d" face=Calibri><span
style='font-size:11.0pt;font-family:Calibri;color:#1F497D'><o:p> </o:p></span></font></p>
<div>
<div style='border:none;border-top:solid #91C0FF 1.0pt;padding:3.0pt 0in 0in 0in'>
<p class=MsoNormal><b><font size=1 face="Segoe UI"><span style='font-size:9.0pt;
font-family:"Segoe UI";font-weight:bold'>From:</span></font></b><font size=1
face="Segoe UI"><span style='font-size:9.0pt;font-family:"Segoe UI"'>
ka-map-users-bounces@lists.maptools.org
[mailto:ka-map-users-bounces@lists.maptools.org] <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>
ka-map-users@lists.maptools.org<br>
<b><span style='font-weight:bold'>Subject:</span></b> [ka-Map-users] Efficient
Point Collision<o:p></o:p></span></font></p>
</div>
</div>
<p class=MsoNormal><font size=2 face="Times New Roman"><span style='font-size:
11.0pt'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Hi Guys,<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
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/">http://flickr.com/map/</a>
) with discs of relative sizes which show the number of points within. <o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
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.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
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.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>I don’t need code, just some inspiration on how to
achieve this, all ideas and suggestions welcome!<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Cheers,<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Chris<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>~~~~~~~~~~~~~~~~~~~~~~~~~~~<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Christopher Brown<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Head of Internet Development<o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Base Bloc <st1:country-region w:st="on"><st1:place
w:st="on">Cambodia</st1:place></st1:country-region><o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>#33, 123, <st1:place w:st="on"><st1:City
w:st="on">Phnom Penh</st1:City>, <st1:country-region w:st="on">Cambodia</st1:country-region></st1:place>.
<o:p></o:p></span></font></p>
<p class=MsoAutoSig><st1:address w:st="on"><st1:Street w:st="on"><font size=1
color=navy face=Arial><span style='font-size:8.0pt;font-family:Arial;
color:navy'>P.O. Box</span></font></st1:Street><font size=1 color=navy
face=Arial><span style='font-size:8.0pt;font-family:Arial;color:navy'> 2086</span></font></st1:address><font
size=1 color=navy face=Arial><span style='font-size:8.0pt;font-family:Arial;
color:navy'><o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'><a href="http://www.basebloc.com">www.basebloc.com</a><o:p></o:p></span></font></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Mobile (+855) 12 315 302</span></font><o:p></o:p></p>
<p class=MsoAutoSig><font size=1 color=navy face=Arial><span style='font-size:
8.0pt;font-family:Arial;color:navy'>Office (+855) 23 222 015<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face="Times New Roman"><span style='font-size:
10.0pt'><o:p> </o:p></span></font></p>
</div>
</body>
</html>