[ka-Map-users] Efficient Point Collision

Sun Oct 22 02:42:20 EDT 2006

Hi Guys,

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.

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. 

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.

Steve: Thanks for the input on my distance calculation that's why I included
it :-), 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:

function getDistance(x1,y1,x2,y2)

{

  var d =  Math.round(Math.sqrt(((x2-x1)*(x2-x1)) + ((y2-y1)*(y2-y1))));

            if (isNaN(d)) d = 0;

  return d;

}

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?

Regards,

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

  _____  

From: Josh Livni [mailto:josh at livniconsulting.com] 
Sent: 21 October 2006 22:34
To: 'Christopher Brown'; ka-map-users at lists.maptools.org
Subject: RE: [ka-Map-users] Efficient Point Collision

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.  

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:
http://www.postgis.org/pipermail/postgis-users/2006-March/011430.html 

  -Josh

From: ka-map-users-bounces at lists.maptools.org
[mailto:ka-map-users-bounces at lists.maptools.org] On Behalf Of Christopher
Brown
Sent: Friday, October 20, 2006 11:53 PM
To: ka-map-users at lists.maptools.org
Subject: [ka-Map-users] Efficient Point Collision

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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.maptools.org/pipermail/ka-map-users/attachments/20061022/ffc6457e/attachment-0001.html