[ka-Map-users] Efficient Point Collision

Sun Oct 22 12:43:29 EDT 2006

**The question of different methods for point grouping or point collision
keeps coming up on a number of lists.  I have created a page on the OSGeo
wiki to try to track some of the methods that folks have come up with.
Right now it is completely empty aside from a title, but hopefully we can
fill it in with some details that have come from this and previous
discussions.  As you experiment (or if you have something that works great)
please describe some different approaches (even if they didn't really work
well, just throw in a brief description of why that path was bad).  If
you've got something that works great, please fill in the details and
perhaps some snippets of code.  As a community, if y'all pick up on this
question coming through the different lists, hopefully we can build this
into a resource we can point folks to rather than having the same
discussions ten times over.

The page is at:
http://wiki.osgeo.org/index.php/Point_Clustering

David

On 10/22/06, Josh Livni <josh at livniconsulting.com> wrote:
>
>  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
>
>
>
> _______________________________________________
> ka-Map-users mailing list
> ka-Map-users at lists.maptools.org
> http://lists.maptools.org/mailman/listinfo/ka-map-users
>
>
>

-- 
************************************
David William Bitner
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.maptools.org/pipermail/ka-map-users/attachments/20061022/0c9b5049/attachment.html