[ka-Map-users] Efficient Point Collision

Christopher Brown chris at basebloc.com
Sat Oct 21 02:53:26 EDT 2006

Hi Guys,

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 ( http://flickr.com/map/ ) with discs of
relative sizes which show the number of points within. 

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.

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.

I don't need code, just some inspiration on how to achieve this, all ideas
and suggestions welcome!





Christopher Brown

Head of Internet Development

Base Bloc Cambodia

#33, 123, Phnom Penh, Cambodia. 

P.O. Box 2086


Mobile (+855) 12 315 302

Office (+855) 23 222 015


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.maptools.org/pipermail/ka-map-users/attachments/20061021/8e3e2cba/attachment.html

More information about the ka-Map-users mailing list