[ka-Map-users] Efficient Point Collision

Sun Oct 22 12:38:41 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, Christopher Brown <chris at basebloc.com> wrote:
>
>  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/3a7bb7f9/attachment-0001.html