[ka-Map-users] Efficient Point Collision

Sun Oct 22 12:21:37 EDT 2006

Chris,

I think as long as your algorithm, server or client-side, knows how to turn
the interleave back into lat/lon (so it's a 1:1 mapping), then it doesn't
really matter if you have extra 0's in front or not.  The project I used
this on was based in the Pacific Northwest, not globally, and so I never had
to deal anything too far left of the decimal place.   

My script was server-side, and it returned somewhere between 80 - 100 pts
for every view - if there would be more than 100 I'd loop through some of
the pts again with a couple more digits lopped off the interleave (bigger
grid). 

In python, an early draft of the main clustering function looked something
like this:  http://rafb.net/paste/results/ePwPB010.html  (I think this might
be online for just a couple days).  Later I added stuff so you could add to
different clusters based on what 'type' of point it was, so each cluster had
only similar points within it.

The script was fast enough - and worked great in the map I was using because
it didn't have panning capability.  However, I had hoped to use it in a
Google Maps, and like a ka-map style application, you don't want to have to
re-request new points every time you pan the map.  Basing it on difference
between pixels implies you could come up with an algorithm that works on the
entire layer for each zoom level.  Then you can precalculate, and put the
cluster results in a new table.  As people add new pts to the database, you
could either add a trigger if it's a rare occurrence, or deal with the
additional few points manually and re-calculate nightly or whatever.  

This would work great assuming people aren't  needing to make arbitrary
queries for subsets of points, but in my case they were, so points really
had to be dynamically created, and I never got around to coming up with a
good way to figure out how to tell how many pts to put on a given screen,
and not have to deal with re-requesting new pts for every major pan action.

A couple weeks ago on #openlayers I was discussing this with bitner, and he
had some great ideas on the topic.   He just mentioned another great idea
which is starting a wiki on the topic - as you can see I'm certainly no
expert on it, but maybe someone will be able to come up with a wiki link to
this really interesting subject.

  -Josh

From: Christopher Brown [mailto:chris at basebloc.com] 
Sent: Sunday, October 22, 2006 7:37 AM
To: 'Josh Livni'; ka-map-users at lists.maptools.org
Subject: RE: [ka-Map-users] Efficient Point Collision

Hi Josh,

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.

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?

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/9aea55f3/attachment.html