Google Maps API Clickable Lines & Polygons
Posted by Ben Appleton, Mapplets Team (this version modified by Mapperz)
In the latest release (v2.88) of the Google Maps API, Lines (Polylines) and Polygons are now clickable events to GPolyline and GPolygon, much to the enthusiasm of developers in the Google Maps API Group Forum. Since a few developers started speculating on how this is being implemented in the API, all the juicy details right here. Warning: Algorithms ahead!
Polyline Hit Detection
As polylines have no intrinsic width, detecting clicks on polylines is something of a judgement call. To detect polyline clicks, this method needs to determine two things
- Whether clicks are close enough to a polyline to count as a click
- Which segment of the polyline is the closest to the click.
Overview of the Algorithm
Click detection begins by measuring the distance (in pixels) between the clicked point and the polyline. For each segment of the polyline, the computed distance between the clicked point and the nearest point along that segment. Then take the minimum of these distances as the closest segment; if the distance is then small enough, it is declared as click on the polyline.
Reducing the Sample Set
Note that the simple algorithm has to look at every segment of the polyline. It can be quite slow for big polylines i.e. driving directions). There are a few heuristics which drastically improve the simple algorithm:
- Given the bounds of the currently visible map viewport, discarded points which are off screen. This can drastically reduce the number of points to consider.
- Zooming out from a detailed polyline, generalising the segments of the polyline into a simpler group of segments without noticeably changing its shape. In the example below, a simplify a polyline from 9 points at the highest zoom level to 4 points at a more zoomed-out level.
Using Bounds Trees
If a clicked point is far away from a segment, it is discarded from consideration. Taking advantage of this fact by pre-computing the bounds of groups of segments; if a clicked point is far from these bounds, it skips distances for all of the enclosed polylines. By recursively combining these bounds for larger and larger groups of segments, "bounds tree" that allows to skip most of the segments when performing hit detection.
This dramatically speeds up polyline hit detection. For example, detecting clicks for complicated polylines like the Camden Cycling Map.
Polygon Hit Detection
Detecting whether a clicked point is within a polygon is more straightforward, and less open to interpretation. We first draw a straight line from the clicked point to the right of the screen. Each time this test line crosses a segment of the polygon, it changes state from being inside to outside or vice-versa. If the test line crosses an odd number of segments then the point is determined to be inside the polygon, whereas if the test line crosses an even number of segments then the point must be outside.
Many of the same improvements for polylines in polygon detection, using the map viewport and zoom level to drastically reduce the number of segments to consider, and using a bounds tree to avoid performing unnecessary intersection tests.
Original Post modified here by Mapperz
Camden Cycle Campaign is one of the very first to use this functionality in full effect. Well done.
"Our primary aim is to get more people to cycle and to improve things for those who already do so."
Labels: 2.88, Clickable, Google Maps API, Lines, Method, Polygons
+ Option + A
