Working with 10k to 20k points: clustering client-side vs server side, geocoding, etc

[Matt Ball]

Starting a new discussion since it's off the topic of the original
thread (http://groups.google.com/group/google-maps-js-api-v3/
browse_thread/thread/35ed8429647ef163), replying to the quoted message
from that thread.

A bit of searching turned up some references to what (I think) you're
talking about:
- http://postgis.refractions.net/pipermail/postgis-users/2006-March/011430.html
- http://www.marine.csiro.au/csquares/about-csquares.htm (not quite
the same)
I don't quite see how I'd use that to speed up my application - would
it involve server-side pre-clustering in some way? At any rate, I
don't have SQL-level access to the data set, I'm not sure if that's a
deal breaker. I'm pretty abstracted out from the database layer, so I
can't really use my own SQL selects to speed things up.
On top of that new entries are geocoded daily (already implemented and
not too slow) but I think that does imply some limits on the
optimizations I can implement.

I am definitely looking into other alternatives. I recall reading
something about showing markers just as an image (in a custom map tile
overlay? not sure.) and using a bit of Javascript to show an info
window when a region containing a marker is clicked. Not sure if this
is doable with v3 - an example is
http://maps.google.com/maps/mpl?moduleurl=http://www.google.com/mapfiles/mapplets/wikipedia/wikipedia.xml,
though I know that's a mapplet and not a separate map.

I still think the clustering could be done completely on the client
side. I'm never going to have to handle more than ~20k markers. So, I
think I can maintain a big array of all my markers (without actually
rendering them) and do the dynamic clustering/rendering client-side
with reasonable speed. Thoughts on that approach?

Something else I'm considering as a separate optimization is server-
side geocoding. Is the only Google API to do this server-side the HTTP
way (sending a request to http://maps.google.com/maps/geo)?

I'd really rather not port all my code to API v2, only to end up
porting it back to v3 once it's more feature-rich. Given my
requirements and the features absent from v3, would you recommend
switching to v2 for now?
Any further recommendations are much appreciated. In the meantime, I
have a lot of research to do!

On Sep 23, 6:35 pm, Björn Brala <bbr...@gmail.com> wrote:
> As soon as you are talking about 10k or maybe 20k markers you should look
> into different solutions. MarkerManager is clientside, this depend for a bit
> part on the speed of the computer at the well, clients side. You should do
> that. One thing i had a lot of help with is some ibm clustering algorithm,
> it interleaves lat and long, Extremely fast! Cant find the link right now.

[Pete]

Matt-

Couple things. Creating custom tiles to overlay on your map in order
to work with a large market set could do the trick yes, but as of now
custom tile overlays i'm not sure if that is in this version yet.

Sever clustering would speed up your application as all the markers
would be clustered on a server rather than client side. Client side
speed would be determined by the browsers js engine, the clients
computer and connection, where as server clustering is based on your
server (database, language, quereying index's).

It would be quicker on the server side, as you can control more of the
variables, and limit the client side interaction. I've been doing
server side clustering for a bit, and will try to get an example out
this weekend on it, as it seems like its a pretty popular topic. I use
JSON to pass back and forth the marker clusters from php -> javascript
then navigate the JSON for the particular clusters and map
accordingly.

As for your move to 3.0:

It depends on what you're wanting right now. I love 3.0 because it
works amazing on mobile devices. If that is a factor for you then
weigh it in your decision. There are features that are still coming
for 3.0 that 2 still has over it, so it depends exactly what you are
looking to do aside from plotting markers.

Hopefully this helps, let me know if you have any other questions!

Thanks

On Sep 24, 11:31 am, Matt Ball <mattjb...@gmail.com> wrote:
> Starting a new discussion since it's off the topic of the original
> thread (http://groups.google.com/group/google-maps-js-api-v3/
> browse_thread/thread/35ed8429647ef163), replying to the quoted message
> from that thread.
>
> A bit of searching turned up some references to what (I think) you're
> talking about:

> -http://postgis.refractions.net/pipermail/postgis-users/2006-March/011...
> -http://www.marine.csiro.au/csquares/about-csquares.htm(not quite

> the same)
> I don't quite see how I'd use that to speed up my application - would
> it involve server-side pre-clustering in some way? At any rate, I
> don't have SQL-level access to the data set, I'm not sure if that's a
> deal breaker. I'm pretty abstracted out from the database layer, so I
> can't really use my own SQL selects to speed things up.
> On top of that new entries are geocoded daily (already implemented and
> not too slow) but I think that does imply some limits on the
> optimizations I can implement.
>
> I am definitely looking into other alternatives. I recall reading
> something about showing markers just as an image (in a custom map tile
> overlay? not sure.) and using a bit of Javascript to show an info
> window when a region containing a marker is clicked. Not sure if this

> is doable with v3 - an example ishttp://maps.google.com/maps/mpl?moduleurl=http://www.google.com/mapfi...,

> though I know that's a mapplet and not a separate map.
>
> I still think the clustering could be done completely on the client
> side. I'm never going to have to handle more than ~20k markers. So, I
> think I can maintain a big array of all my markers (without actually
> rendering them) and do the dynamic clustering/rendering client-side
> with reasonable speed. Thoughts on that approach?
>
> Something else I'm considering as a separate optimization is server-
> side geocoding. Is the only Google API to do this server-side the HTTP

> way (sending a request tohttp://maps.google.com/maps/geo)?

[bratliff]

On Sep 24, 4:31 pm, Matt Ball <mattjb...@gmail.com> wrote:
> Starting a new discussion since it's off the topic of the original
> thread (http://groups.google.com/group/google-maps-js-api-v3/
> browse_thread/thread/35ed8429647ef163), replying to the quoted message
> from that thread.
>
> A bit of searching turned up some references to what (I think) you're
> talking about:

> -http://postgis.refractions.net/pipermail/postgis-users/2006-March/011...
> -http://www.marine.csiro.au/csquares/about-csquares.htm(not quite

> the same)
> I don't quite see how I'd use that to speed up my application - would
> it involve server-side pre-clustering in some way? At any rate, I
> don't have SQL-level access to the data set, I'm not sure if that's a
> deal breaker. I'm pretty abstracted out from the database layer, so I
> can't really use my own SQL selects to speed things up.
> On top of that new entries are geocoded daily (already implemented and
> not too slow) but I think that does imply some limits on the
> optimizations I can implement.
>
> I am definitely looking into other alternatives. I recall reading
> something about showing markers just as an image (in a custom map tile
> overlay? not sure.) and using a bit of Javascript to show an info
> window when a region containing a marker is clicked. Not sure if this

> is doable with v3 - an example ishttp://maps.google.com/maps/mpl?moduleurl=http://www.google.com/mapfi...,

> though I know that's a mapplet and not a separate map.
>
> I still think the clustering could be done completely on the client
> side. I'm never going to have to handle more than ~20k markers. So, I
> think I can maintain a big array of all my markers (without actually
> rendering them) and do the dynamic clustering/rendering client-side
> with reasonable speed. Thoughts on that approach?
>
> Something else I'm considering as a separate optimization is server-
> side geocoding. Is the only Google API to do this server-side the HTTP

> way (sending a request tohttp://maps.google.com/maps/geo)?

>
> I'd really rather not port all my code to API v2, only to end up
> porting it back to v3 once it's more feature-rich. Given my
> requirements and the features absent from v3, would you recommend
> switching to v2 for now?
> Any further recommendations are much appreciated. In the meantime, I
> have a lot of research to do!

Displaying markers is just half of the battle. The other half is
responding to mouse actions.

A browser based approach will be a lot quicker. A server base
approach will require one round trip per click. Instantaneous
"rollover" feedback is only practical in the client. Using individual
event listeners for every marker is impractical. I use intersecting X
& Y slices. A successful hit requires a point to be contained in
both. It also works well with shapes (polys). Others have used
cookies correlated with tiles.

If the lack of a V2 GTileLayerOverlay equivalent for V3 is an issue,
look at:

www.polyarc.us/sparsetile.js
www.polyarc.us/sparse
www.polyarc.us/experimental

[Matt Ball]

I think client-side clustering could work - I'm able to load 10k
markers into a Javascript array, without rendering them on the map, in
a reasonable amount of time. The trick is to then write some really
fast code to cluster them - not so sure how well it could scale up to
20k (twice as many) markers.

I've been working on writing my own overlay that subclasses
OverlayView, but it's been slow going since I don't really know what
I'm doing.
I started out working from a bit of code and ideas presented in the
tech talk video linked at http://code.google.com/events/io/sessions/PerformanceTipsGeoApiMashups.html
(about 14 minutes in). But that was for API v2. So, I could really use
some good reference on doing this with v3.
Likewise I've been poking around in the google maps book (http://
www.googlemapsbook.com/chapter7/) but it's also not written for v3.
Am I fighting a losing battle trying to do this with v3?

Bratliff, the stuff you linked looks interesting but I haven't had
much luck applying it to my own problem. Would you be able to provide
more details about your work there? Any references or documentation at
all would be much appreciated.

Has anyone come across client-side clustering implementations, or some
sort of marker-displaying overlay, for v3? Everything I've dug up is
still for v2.
I really don't need any sort of fancy interaction with the markers,
just simple info windows.

[Matt Ball]

[Paul Kulchenko]

Matt,

I've experimented with drawing a large number of points/markers just
recently; although my numbers are probably not as large as Berry's
(bratliff). You may take a look at the code I have here:
http://notebook.kulchenko.com/maps/datamark

It's for v2 and it's using GTileLayer and getTileURL to return data:
URL. This doesn't work in IE and on iPhone 3G's Safari, which was one
of the reasons I moved to pure canvas implementation. It's using one
canvas element to draw all the points for a particular tile and then
to convert it to a png file using toDataURL canvas method. It simple
and works surprisingly well, but I get better results with drawing one
canvas element per tile (as has been discussed at length in other
threads). I also dynamically add markers for those elements that are
located on tiles currently displayed. When clicked it simply shows the
nearest Street View data. The data file currently has 20k+ of random
points clustered around several cities. Be patient to wait for it to
load...

I also have a different implementation that is using the same code for
both APIs (v2 and v3); I might be able to share it in few days.

Paul.

On Sep 25, 2:40 pm, Matt Ball <mattjb...@gmail.com> wrote:
> I think client-side clustering could work - I'm able to load 10k
> markers into a Javascript array, without rendering them on the map, in
> a reasonable amount of time. The trick is to then write some really
> fast code to cluster them - not so sure how well it could scale up to
> 20k (twice as many) markers.
>
> I've been working on writing my own overlay that subclasses
> OverlayView, but it's been slow going since I don't really know what
> I'm doing.
> I started out working from a bit of code and ideas presented in the

> tech talk video linked athttp://code.google.com/events/io/sessions/PerformanceTipsGeoApiMashup...

> (about 14 minutes in). But that was for API v2. So, I could really use
> some good reference on doing this with v3.

> Likewise I've been poking around in the google maps book (http://www.googlemapsbook.com/chapter7/) but it's also not written for v3.

[bratliff]

On Sep 24, 4:31 pm, Matt Ball <mattjb...@gmail.com> wrote:

Hi Matt,

The stuff I provided is only useful if you are looking for a
replacement for GTileLayerOverlay:

www.polyarc.us/sparsetile.js
www.polyarc.us/sparse
www.polyarc.us/experimental

I have added a couple of small improvements. One
"sparsetilelayeroverlay" will accommodate multiple tile sources. It
will not attempt to fetch non-existent, out of bounds tiles.

Tiles are fast but you will have to figure out how to interact with
the mouse. Anything requiring server assistance will add delay. It
usually means some kind of auxilliary grid structure. I have seen
"quad trees" mentioned but I believe it is overkill.

I prefer to just slice the area into intersecting horizontal &
vertical strips several pixels (64) wide. Each marker is added the
corresponding horizontal & vertical strip along with its actual
bounds. If a marker is near the edge of a strip, it may have to be
added to the adjacent strip too. If you receive a click, you only
must examine the corresponding X & Y strips. A successful hit
requires the marker to be contained in both the X & Y strips. The
same mechanism works well for polys (shapes).

[Paul Kulchenko]

Matt,

As promised here is the code I came up with for the canvas overlay
that works with both API v2 and v3: http://notebook.kulchenko.com/maps/gridapi.
The description of the differences between API versions that I handled
in my code is here: http://notebook.kulchenko.com/maps/google-maps-using-multiple-api-versions.
It doesn't have all the functions you need yet, but it's a demo that
shows it's possible to use the same canvas overlay for both APIs,
which may provides you with a migration path.

My personal preference is to go with client side handling with a tile-
based implementation to avoid clustering at all. As Berry said
earlier, the challenge is to handle mouse/touch events, but there are
several approaches to use; my biggest hurdle so far has been to align
elements with tiles and get decent performance.

Paul (http://notebook.kulchenko.com/maps/)

[Matt Ball]

At this point things are working pretty well. I'm just working on an
efficient way to look up a marker based on a LatLng. I'm open to ideas
on this one.

Bratliff- This method sounds pretty good. Any chance you have a coded
example I could poke around?
Another method I was thinking of was building a hashtable (well, you
know, an associative array) of my markers, keyed on the LatLng. Any
thoughts on this? I know that building it could be a bit slow, but
once it's built, I think it would be pretty quick.

Paul- that canvas overlay method worked wonderfully! Thank you! Talk
about a lifesaver. I do like that click interaction still works, but
it's not ideal for my map since it's limited to a hardcoded zoom
level. I know it's a tradeoff with performance, so I'm trying to find
an alternate (fast) way to do it at any zoom level.

[bratliff]

On Oct 2, 4:56 pm, Matt Ball <mattjb...@gmail.com> wrote:

> Bratliff- This method sounds pretty good. Any chance you have a coded
> example I could poke around?
> Another method I was thinking of was building a hashtable (well, you
> know, an associative array) of my markers, keyed on the LatLng. Any
> thoughts on this? I know that building it could be a bit slow, but
> once it's built, I think it would be pretty quick.

The code is not very user friendly. Look at:

www.polyarc.us/polybuilder

It was developed for polys (shapes). It may be overkill for markers.

A hash table requires an exact match. It will not work for Lat/Lon
coordinates (floating point numbers) unless rounded to precisely the
same value. It will not work for pixels (fixed point numbers) unless
you can live with pixel level accuracy. You really have to allow for
a margin of error.

[Andrew Mcnulty]

Hi Matt

I'm not technical but have been waiting for a discussion on markers
and then would pass on to our developer. From reading the emails it
seems like you want to cluster or group together markers. Is that
right? If so has the response from this group given you what you need?
We really need it on our site www.getawayearth.com as you will see if
you have a look.

Thanks

Andy

[Matt Ball]

Andrew,
It actually worked out better - both in content presentation and speed
- to not cluster the markers.
I implemented a canvas tile overlay adapted from Paul Kulchenko's
posted example. It's lower-level than dealing with markers but it's
WAY faster.
I did take a look at your site, and I'm not sure why you need
clustering, as it's sufficiently fast and I didn't see many markers on
the map.

Paul - a question for you (or anyone else who's knowledgeable,
really): in order to handle the clicks on the "markers" I simply bound
a click listener to the map, which gets the coords of the click and
finds the nearest marker pretty much by brute force. It would be nice
if a click event didn't fire if the click was not on a region of the
map (really, the overlay) containing a "marker."
Is it possible to bind a listener to the overlay such that it only
fires when one of the circles is clicked? I am specifically not using
any API Marker objects - just using Paul's canvas tile overlay
technique to render things that look like markers.

On Oct 3, 2:54 am, Andrew Mcnulty <ajmcnult...@googlemail.com> wrote:
> Hi Matt
>
> I'm not technical but have been waiting for a discussion on markers  
> and then would pass on to our developer. From reading the emails it  
> seems like you want to cluster or group together markers. Is that  
> right? If so has the response from this group given you what you need?  

> We really need it on our sitewww.getawayearth.comas you will see if  

> you have a look.
>
> Thanks
>
> Andy
>

[Paul Kulchenko]

Matt,

I think it's possible, but probably with a slightly different syntax.
I'm working on the logic that allows to track when you mouseover such
a marker or click on it. The code is not ready yet, but I expect to
have a working example in few days.

I see several options in triggering the click or mouseover events:
1. track position and then do search either using x/y coordinate
stripes or quadtrees; you need to use something better than brute
force as it's going to be painfully slow with a large number of
markers; although this may work in some cases with tiles as those
already limit the number of points to check (you already know what
tile you're over).
2. check the color of the point under the mouse pointer (same for the
click); with an additional layer you can even encode a particular
marker id as a specific color (as long as transparency is properly set
to make the color invisible). I got the prototype working, but I don't
like some aspects of this method, so I'll probably end up implementing
#1.
3. use something like SVG that provides an element to bind to, but
with multiple points combined together (if they touch each other) to
reduce the number of DOM elements to track.

There is also a question of where the event should be attached to: the
container object (the one that holds canvas elements, not the map),
canvas/image elements themselves or pseudo markers (elements that
don't have any DOM representation, but are Marker objects with methods
that act as mouseover/click callbacks).

Matt, are you using the later code with canvas elements, or the
earlier example I provided with data: URLs and toDataURL conversion?
The latter (data: URLs) worked well, but didn't satisfy all my
requirements, so I probably will not do any improvement to it even
though the logic I'm working on should be applicable there too. Just
wanted to let you know.

Paul.

> > We really need it on our sitewww.getawayearth.comasyou will see if  

[bratliff]

Hi Paul & Matt,

Paul, have you figured out a clean way to track the mouse without
interfering with Google's event handlers ? I realize "mousemove" is
meaningless to iPhone users but I guess Internet Explorer support is
also.

The best I have been able to do is the following:

www.polyarc.us/polycluster/event.html

It is a lot of code to do what was trivial with the old API.

I have played with "getImageData" / "putImageData" in CANVAS. Both
seem extremely slow. I think it is the back & forth conversion from 8
bit bytes to 32 bit dwords. For "rollovers" I doubt it will seem fast
enough. For what it is worth, you could use the two low order bits of
each color plus alpha (RGBA) for a total of eight bits to identify a
marker. 256 unique ids per tile ought to be sufficient.

I use X & Y slices for polys (shapes) but it could be done for points
also. Basically, you choose a strip width like 64 bits. For each
marker, you add its unique id to the corresponding X & Y slices. If
it is fewer than half the target width bits from the edge, you also
add it to the neighboring parallel strip.

Each strip is an associative array which can be iterated sequentially
with a "for in" loop or accessed directly by unique marker id. I keep
a counter of the number of elements in each strip in order to iterate
through the one with the fewest elements.

A click determines which X & Y strips might contain a marker. Choose
the one with the smallest number of elements. Iterate through it.

If you choose X:

for (i in X[clickedX])
if (Y[clickedY][i]) check marker i

If you choose Y:

for (i in Y[clickedY])
if (X[clickedX][i]) check marker i

For markers, it may be overkill but for polys (shapes) it works well.

[Matt Ball]

On Oct 5, 9:39 pm, Paul Kulchenko <paulclin...@gmail.com> wrote:
> Matt, are you using the later code with canvas elements, or the
> earlier example I provided with data: URLs and toDataURL conversion?
> The latter (data: URLs) worked well, but didn't satisfy all my
> requirements, so I probably will not do any improvement to it even
> though the logic I'm working on should be applicable there too. Just
> wanted to let you know.

I'm using the example at http://notebook.kulchenko.com/maps/datamark,
so I guess that would be the earlier example using toDataURL - though
it does use a canvas!
The basic thing I had to modify was to make it never create markers,
because I want to be able to get info windows on mouse click at any
zoom level. Instead what my version does is given the latlng of a
mouse click, it find the nearest "marker" by looping over my array of
all points and finds the closest one (using the Haversine formula). It
only opens an info window if the nearest is within 5km. With 9500
points each search takes about 90ms, so it should scale to 20k data
points acceptably.
The only real problem with this is that it searches for a nearby
"marker" even if the click was nowhere near one - say, in the middle
of the ocean. This is because the search is initiated by a click on
the map, not on the tile layer. Since I don't understand terribly well
how the tile layer works, or what constitutes a click on the overlay
rather than on the map, I didn't try too hard to get it working with
the click listener bound to the overlay.

Speaking of which, I know this discussion is in the API v3 thread but,
in light of Paul's example that I adapted (for v2), I did end up
porting my code to API v2. The reason I used the "datamark" v2 as my
foundation was because I didn't see anything marker-like within the
map at http://notebook.kulchenko.com/maps/gridapi.

I do think that bratliff's x/y strip method is overkill for markers,
given how quick (90ms per search) my brute-force method works. I'm
always open to suggestion though, and I may play around with
improvements when I have some time in the next couple of days.

Paul, re: the latest stuff you said you're working on - does it ever
create API Marker objects (the way your "datamark" example does)? I am
definitely still interested in making improvements on what I have
working right now. In addition to performance, I will mostly likely
want to draw different-looking markers (color, shape, etc) on the same
map, which will require more tweaking based on my adaptation from the
datamark stuff.

Thanks again!

[Paul Kulchenko]

Berry,

> Paul, have you figured out a clean way to track the mouse without interfering with Google's event handlers ?

I can't even figure out a clean way to track the mouse without any
additional conditions ;). just kidding.

The logic I have seems to work well in Firefox and it doesn't seem to
interfere with anything, but I don't have much in terms of gmap's
event handlers, so I may be just not seeing the interference. Do you
have an example that shows the interference? I can check it against my
logic.

The biggest challenge so far is IE (what a surprise). I'm using IE7
and seem to be unable to track movement (mousemove) on the container
div I have that holds all canvas elements (VML in IE case). The good
thing is that mousemove events seem to be only triggering when the
mouse is over a marker or polygon, but the bad thing is that
additional calculations are needed to map client/page coordinates to
tiles and in-tile offsets.

> I use X & Y slices for polys (shapes) but it could be done for points
> also. Basically, you choose a strip width like 64 bits. For each

I use similar logic, but my slices are more narrow and they overlap.
as I have overlapping markers, each slice hit may point to an array of
markers/points. I think I'm close to making it work in FF and with
some tweaks in IE.

Paul (http://notebook.kulchenko.com/maps/)

[Paul Kulchenko]

Matt,

> only opens an info window if the nearest is within 5km. With 9500
> points each search takes about 90ms, so it should scale to 20k data
> points acceptably.

This is fast. Would you share your algorithm? I'm tracking movement
over specific tiles, so your brute force approach should work even
better when limited to one particular tile (or neighboring tiles when
close to the border).

> porting my code to API v2. The reason I used the "datamark" v2 as my
> foundation was because I didn't see anything marker-like within the
> map athttp://notebook.kulchenko.com/maps/gridapi.

right; it was just a proof of concept to show that it's possible to
use the same class to work with both APIs. It seems that the Marker
object can be handled in a similar way.

> Paul, re: the latest stuff you said you're working on - does it ever
> create API Marker objects (the way your "datamark" example does)? I am
> definitely still interested in making improvements on what I have
> working right now. In addition to performance, I will mostly likely
> want to draw different-looking markers (color, shape, etc) on the same
> map, which will require more tweaking based on my adaptation from the
> datamark stuff.

I currently don't create API marker objects at all and plan to provide
a lightweight object that callbacks can be attached to. The challenge
is to find a good way to avoid creating too many objects and still be
able to handle multiple overlapping markers in the same location. As I
briefly touched on earlier in this thread, I will probably provide a
callback that will receive an array of markers in the click location.
If you only care about one marker, you can just get the first one.

I also plan to draw markers of various types and colors; I already
have a heatmap-like presentation, but it doesn't currently handle any
interaction.

I'm still testing the idea of creating Markers on the fly (not for the
object on the script, but rather for the objects under the pointer),
but regular object only work for circular and rectangular markers. For
anything more complex SVG/VML needs to be used. The benefit is that
you get all DOM events for "free" without any additional work. the
challenge is that with hundreds or even thousands points I have in a
very small area I end up with dynamically creating large number of
objects, which is not workable.

Paul (http://notebook.kulchenko.com/maps/)

On Oct 7, 10:22 am, Matt Ball <mattjb...@gmail.com> wrote:
> On Oct 5, 9:39 pm, Paul Kulchenko <paulclin...@gmail.com> wrote:
>
> > Matt, are you using the later code with canvas elements, or the
> > earlier example I provided with data: URLs and toDataURL conversion?
> > The latter (data: URLs) worked well, but didn't satisfy all my
> > requirements, so I probably will not do any improvement to it even
> > though the logic I'm working on should be applicable there too. Just
> > wanted to let you know.
>

> I'm using the example athttp://notebook.kulchenko.com/maps/datamark,

> so I guess that would be the earlier example using toDataURL - though
> it does use a canvas!
> The basic thing I had to modify was to make it never create markers,
> because I want to be able to get info windows on mouse click at any
> zoom level. Instead what my version does is given the latlng of a
> mouse click, it find the nearest "marker" by looping over my array of
> all points and finds the closest one (using the Haversine formula). It
> only opens an info window if the nearest is within 5km. With 9500
> points each search takes about 90ms, so it should scale to 20k data
> points acceptably.
> The only real problem with this is that it searches for a nearby
> "marker" even if the click was nowhere near one - say, in the middle
> of the ocean. This is because the search is initiated by a click on
> the map, not on the tile layer. Since I don't understand terribly well
> how the tile layer works, or what constitutes a click on the overlay
> rather than on the map, I didn't try too hard to get it working with
> the click listener bound to the overlay.
>
> Speaking of which, I know this discussion is in the API v3 thread but,
> in light of Paul's example that I adapted (for v2), I did end up
> porting my code to API v2. The reason I used the "datamark" v2 as my
> foundation was because I didn't see anything marker-like within the

> map athttp://notebook.kulchenko.com/maps/gridapi.

[Paul Kulchenko]

Berry,

> I use X & Y slices for polys (shapes) but it could be done for points also. Basically, you choose a strip width like 64 bits.

Also, handling events for polys seems to be more complex than tracking
points, as for points you only need to check the distance; for polys
you need to know what side you're on: inside or outside. Is your check
fast enough for complex polygons?

Paul (http://notebook.kulchenko.com/maps/)

[Matt Ball]

My search algorithm is dead simple - it's basically a "min" function.
I have a globally-accessible array of jQuery XML elements (since each
point originates from an XML file) that are already decorated with a
google.maps.LatLng object. As I iterate over the array, I keep track
of the nearest point and the actual distance (so I don't have to
recalculate the distance). Distance between points[i].latLng and the
clicked latLng is computed using a tuned version of the Haversine
formula I originally found at http://www.movable-type.co.uk/scripts/latlong.html#ellipsoid.
Basically, I removed function calls out of the distHaversine function,
and this was where I picked up a lot of speed. The function itself
ended up as

function distHaversine(x, y)
{
// (x)*(Math.PI/180) converts x from deg to rad
var lat1 = x.lat();
var lng1 = x.lng();
var lat2 = y.lat();
var lng2 = y.lng();

var R = 6371; // earth's mean radius in km
var dLat = (lat2-lat1)*(Math.PI/180);
var dLon = (lng2-lng1)*(Math.PI/180);
lat1 = (lat1)*(Math.PI/180); lat2 = (lat2)*(Math.PI/180);

var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
Math.cos(lat1) * Math.cos(lat2) *
Math.sin(dLon/2) * Math.sin(dLon/2);
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
var d = R * c;
return d;
}

where x and y are google.maps.LatLngs.

After I've iterated over the array of points, I check that the
distance is less than 5 before returning the nearest point found.

[bratliff]

On Oct 8, 6:30 pm, Paul Kulchenko <paulclin...@gmail.com> wrote:
> Berry,
>
> > I use X & Y slices for polys (shapes) but it could be done for points also. Basically, you choose a strip width like 64 bits.
>
> Also, handling events for polys seems to be more complex than tracking
> points, as for points you only need to check the distance; for polys
> you need to know what side you're on: inside or outside. Is your check
> fast enough for complex polygons?

I believe it is. I have an old demo:

www.polyarc.us/polybuilder

It does some things discrete event listeners cannot do. It can
provide "click" / "rollover" events for a naked map on which polys
have not been rendered. It can provide multiple heirarchical (state /
county / township / city / zipcode) hit results. It scales well for
many polys. I simplified the explanation for use with markers.

[Paul Kulchenko]

Matt,

You probably run on some super hardware. What browser do you use? My
calculation is much simpler as I already have mapping to points for
each tile, so I just iterate over points in that tile calculating
euclidean difference:

var d = Math.sqrt((points[i].x - x) * (points[i].x - x)
+ (points[i].y - y) * (points[i].y - y));

Still, even with this simple formula it takes about 50ms to iterate
over 3500 points and 100ms for 8500 points. Numbers are for FF 3.5.3.

I managed to get it working in FF and IE and also in v2 and v3 APIs.
I'll put together a demo shortly.

Paul (http://notebook.kulchenko.com/maps/)

On Oct 9, 7:30 am, Matt Ball <mattjb...@gmail.com> wrote:
> My search algorithm is dead simple -  it's basically a "min" function.
> I have a globally-accessible array of jQuery XML elements (since each
> point originates from an XML file) that are already decorated with a
> google.maps.LatLng object. As I iterate over the array, I keep track
> of the nearest point and the actual distance (so I don't have to
> recalculate the distance). Distance between points[i].latLng and the
> clicked latLng is computed using a tuned version of the Haversine

> formula I originally found athttp://www.movable-type.co.uk/scripts/latlong.html#ellipsoid.

> ...
>
> read more »

[Matt Ball]

I use FF 3.5.3 as well, running on a fairly recent Dell refurb (Vista
x64, 6 GB RAM, Core 2 Quad 2.5 GHz).

> ...
>
> read more »

[Matt Ball]

Paul,
I've actually managed to make this thing take even less time by
writing some ugly (but fast) Javascript.
One big improvement was switching the for loop to a decreasing while
loop. That (and a few other small things) got the search down to ~72
ms per click.

> ...
>
> read more »

[Paul Kulchenko]

Matt,

It took me a bit longer, but I put together a demo that shows how to
change mouse cursor when hovering over a marker on canvas:

http://notebook.kulchenko.com/maps/gridmark

All the logic is in the mousemove handler; onclick event can be
handled in a similar way. You can also tweak the logic to give you the
list of all the markers you're hovering over. I plan to better
abstract the interface and to provide real events for the object I'm
creating, but haven't had a chance yet.

I do a brute force search but only for markers in the same tile I'm
hovering over. There are also few tricks for properly changing the
shape when the center of a marker is on another tile, but the circle
is partially on the tile the mouse is over.

The logic I have should work even better for you as I do fewer
calculations in my handler.

Paul (http://notebook.kulchenko.com/maps/)

On Oct 14, 1:50 pm, Matt Ball <mattjb...@gmail.com> wrote:
> Paul,
> I've actually managed to make this thing take even less time by
> writing some ugly (but fast) Javascript.
> One big improvement was switching the for loop to a decreasing while
> loop. That (and a few other small things) got the search down to ~72
> ms per click.
>
> On Oct 12, 11:29 am, Matt Ball <mattjb...@gmail.com> wrote:
>
> > I use FF 3.5.3 as well, running on a fairly recent Dell refurb (Vista
> > x64, 6 GB RAM, Core 2 Quad 2.5 GHz).
>

> > > > > > > On Oct 6, 1:39 am, PaulKulchenko<paulclin...@gmail.com> wrote:
>
> > > > > > > > Matt,
>
> > > > > > > > I think it's possible, but probably with a slightly different syntax.
> > > > > > > > I'm working on the logic that allows to track when you mouseover such
> > > > > > > > a marker or click on it. The code is not ready yet, but I expect to
> > > > > > > > have a working example in few days.
>
> > > > > > > > I see several options in triggering the click or mouseover events:
> > > > > > > > 1. track position and then do search either using x/y coordinate
> > > > > > > > stripes or quadtrees; you need to use something better than brute
> > > > > > > > force as it's going to be painfully slow with a large number of
> > > > > > > > markers; although this may work in some cases with tiles as
>

> ...
>
> read more »

[Matt Ball]

Paul,
That looks awesome. Have you tried it out with tens of thousands of
points? Just wondering since your example has what looks like maybe a
couple hundred.
I've shifted my focus in this project to some data layer stuff, so
I'll probably come back later and tune up my map based on your latest
and greatest. Have you found that v3 handles many points especially
faster or slower than v2?
Thanks again for the great code and help!

Matt

> ...
>
> read more »

[Paul Kulchenko]

Matt,

I did try with a large number of points (20k+), but it didn't make any
difference as it only checks those points that belong to the tile the
mouse is over. I also tested with 3500 points on one tile and it took
about 50-70ms on my hardware (which is why I was surprised that yours
was faster with more points and more complex logic). I haven't noticed
and significant delays; both FF and IE seem to work fine.

If you just care about mouse cursor, you can break out of the loop
after you found that it's within specific distance from one of the
points (you don't need to know it's the nearest one). It's also
possible just to check for a square (instead of euclidean distance),
which should make it even faster.

I haven't noticed much difference between v2 and v3, but this is
probably because I'm bypassing the API and doing all the calculations
myself. I looked at the logic in fromLLtoPixel mapping that API is
implementing and it's very similar to what I'm using (with few
optimization techniques like pre-calculating per-zoom multipliers)
that I haven't done yet.

Paul (http://notebook.kulchenko.com/maps/)

> ...
>
> read more »

[bratliff]

On Oct 21, 9:30 pm, Paul Kulchenko <paulclin...@gmail.com> wrote:

Hi Paul,

> If you just care about mouse cursor, you can break out of the loop
> after you found that it's within specific distance from one of the
> points (you don't need to know it's the nearest one). It's also
> possible just to check for a square (instead of euclidean distance),
> which should make it even faster.

You could compare squared distances rather than actual distances.

if (sqrt(x*x+y*y) < (target))

could be replaced by:

if ((x*x+y*y) < (target*target))

> I haven't noticed much difference between v2 and v3, but this is
> probably because I'm bypassing the API and doing all the calculations
> myself. I looked at the logic in fromLLtoPixel mapping that API is
> implementing and it's very similar to what I'm using (with few
> optimization techniques like pre-calculating per-zoom multipliers)
> that I haven't done yet.

Why use zoom multipliers ?

Shifting integer pixels is much faster than floating point
multiplication and/or floating point division. Also, the use of "~ ~"
to perform integer truncation is not required with shifting.

[Paul Kulchenko]

Berry,

> could be replaced by:
>
> if ((x*x+y*y) < (target*target))

good idea.

> Why use zoom multipliers ?
>
> Shifting integer pixels is much faster than floating point
> multiplication and/or floating point division. Also, the use of "~ ~"
> to perform integer truncation is not required with shifting.

Agree, but I changed the logic because of this:

http://groups.google.com/group/google-maps-api/browse_thread/thread/cf1b9e76cbd84b38/49e8a032f8f1d05c#49e8a032f8f1d05c

Basically, the shifting logic produces incorrect results (x
coordinates are off by one pixel) for some values.

Paul.

[bratliff]

On Oct 28, 2:31 am, Paul Kulchenko <paulclin...@gmail.com> wrote:
> Berry,
>
> > could be replaced by:
>
> > if ((x*x+y*y) < (target*target))
>
> good idea.
>
> > Why use zoom multipliers ?
>
> > Shifting integer pixels is much faster than floating point
> > multiplication and/or floating point division. Also, the use of "~ ~"
> > to perform integer truncation is not required with shifting.
>
> Agree, but I changed the logic because of this:
>

> http://groups.google.com/group/google-maps-api/browse_thread/thread/c...

>
> Basically, the shifting logic produces incorrect results (x
> coordinates are off by one pixel) for some values.

It is working for me. I have made a couple innocuous changes. I have
factored out the degree to radian conversion constant to avoid
repeated divisions. I have also used rounding rather than truncation
to exactly match Google's center coordinates. Rounding can be
performed using shifting. Just add (1<<Z>>1) to each pixel offset
prior to shifting the entire amount by Z. The double shift is used to
avoid trying to do a negative shift if Z=0. Previously, I have set Z=
(21-z).

Do you have a VERY simple example in which shifting fails ?

[bratliff]

Hi Paul,

Do you have a very simple example ? I will be happy to look at it.

I have looked at Google's conversion code. I believe it could be
streamlined without "zoom multipliers", just simple shifting of
integers with optional rounding. I prefer quick turncation. Who
cares about a half pixel displacement if it is applied uniformly ?

Berry

[Ben Appleton]

The problem is that makes projections lossy, which would cause us to
fired extra 'changed' events in some cases. Without measuring it I'm
not sure that scaling is significantly more expensive than shifting.

> Berry
>
> >
>

[bratliff]

On Oct 29, 11:17 pm, Ben Appleton <apple...@google.com> wrote:
> The problem is that makes projections lossy, which would cause us to
> fired extra 'changed' events in some cases. Without measuring it I'm
> not sure that scaling is significantly more expensive than shifting.

I perform the projection calculation once for zoom level 21 using
floating point trig. I never repeat the the projection calculation
again for the same point. Other zoom levels are obtained by shifting
the pixel value for zoom level 21 right by (Z=21-z). Except for
truncation, it is lossless. Rounding can be achieved by adding
(1<<Z>>1) to the pixel value prior to shifting the entire amount right
by (Z=21-z). A zoom speed comparison can be made against PolyCluster
on identical polys. I should have used zoom level 23 which is the
limit for a 32 bit signed integer with 256x256 pixel tiles.

[Paul Kulchenko]

Hi Berry,

I added an example that shows the discrepancy:

http://notebook.kulchenko.com/maps/gridoff1

When you load it you'll see:

-111.90884 and 33.52392 => 198329=198330; 420541=420541

The first pair is what's calculated: 198329x420541 vs. what's returned
by the API: 198330x420541.

Paul (http://notebook.kulchenko.com/maps/)

[Ben Appleton]

Right: we also project polys only once, at zoom level 0 for what it's worth.  My point is that I would not want to make projections lossy without a significant measurable benefit.  It's easy to add rounding later, but it's impossible to undo rounding once it has been performed.

 

[bratliff]

On Oct 30, 6:02 am, Ben Appleton <apple...@google.com> wrote:

> Right: we also project polys only once, at zoom level 0 for what it's worth.
> My point is that I would not want to make projections lossy without a
> significant measurable benefit. It's easy to add rounding later, but it's
> impossible to undo rounding once it has been performed.

OK - you must be storing a floating point result. I am storing an
integer result. Integers can be shifted without loss. Floats cannot
be shifted without loss. Integers can be rounded by adding a scaled
half pixel prior to the shift. For me, truncation is good enough.

[bratliff]

On Oct 30, 2:20 am, Paul Kulchenko <paulclin...@gmail.com> wrote:
> Hi Berry,
>
> I added an example that shows the discrepancy:
>
> http://notebook.kulchenko.com/maps/gridoff1
>
> When you load it you'll see:
>
> -111.90884 and 33.52392 => 198329=198330; 420541=420541
>
> The first pair is what's calculated: 198329x420541 vs. what's returned
> by the API: 198330x420541.
>
> Paul (http://notebook.kulchenko.com/maps/)

Hi Paul,

Try:

var Z=21-z;
var halfPixel=1<<Z>>1;
var abs=
{
x:(LngToX(center.lng())+halfPixel)>>Z,
y:(LatToY(center.lat())+halfPixel)>>Z
};

Berry