<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: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 Josh,<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'>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.<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'>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?<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>
<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>