[ka-Map-users] Efficient Point Collision

[Stephen Woodbridge]

These is a very expensive operations:

var distance = Math.sqrt(
	Math.pow(
		(Math.pow((thisNodeLeft - otherNodeLeft),2) +
		 Math.pow((thisNodeTop - otherNodeTop  ),2)
		),1));

Why are you doing the pow(a*a + b*b, 1)? this is useless and expensive.

It is much faster to do a multiple than pow and you should avoid doing 
the sqrt. This can be done by comparing the square of the distances 
instead of the distance and get the same effect.

var a = thisNodeLeft - otherNodeLeft;
var b = thisNodeTop - otherNodeTop;
var distancesq = a*a + b*b;
// if you HAVE to have the distance try to wait until you exit the
// loop with the closest option and then compute the sqrt(distancesq)

This should make thing much faster, but probably not fast enought to do 
500 points.

-Steve W.

Christopher Brown wrote:
> 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!
> 
> Cheers,
> 
> Chris
> 
>  
> 
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~
> 
> Christopher Brown
> 
> Head of Internet Development
> 
> Base Bloc Cambodia
> 
> #33, 123, Phnom Penh, Cambodia.
> 
> P.O. Box 2086
> 
> www.basebloc.com
> 
> Mobile (+855) 12 315 302
> 
> Office (+855) 23 222 015
> 
>  
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> ka-Map-users mailing list
> ka-Map-users at lists.maptools.org
> http://lists.maptools.org/mailman/listinfo/ka-map-users