In our latest release (2.88) of the API, we've added "click" events to GPolyline and GPolygon, much to the enthusiasm of developers in the forum. Since a few developers started speculating on how we implemented click detection in the API, we're giving you 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 judgment call. To detect polyline clicks, we need to determine two things: whether clicks are close enough to a polyline to count as a click, and 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, we compute the distance between the clicked point and the nearest point along that segment. We then take the minimum of these distances as the closest segment; if the distance is then small enough, we declare it a 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 (such as driving directions). There are a few heuristics which drastically improve the simple algorithm:
- Given the bounds of the currently visible map viewport, we discard points which are off screen. This can drastically reduce the number of points to consider.
- As we zoom out from a detailed polyline, we also condense and "smooth" segments of the polyline into a simpler group of segments without noticeably changing its shape. In the example below, we simplify a polyline from 9 points at the highest zoom level to 4 points at a more zoomed-out level.
Using Bounds Trees
If we discern that a clicked point is far away from a segment, we discard it from consideration. We take advantage of this fact by precomputing the bounds of groups of segments; if a clicked point is far from these bounds, we skip computing distances for all of the enclosed polylines. By recursively combining these bounds for larger and larger groups of segments, we build a "bounds tree" that allows us to skip most of the segments when performing hit detection.
This dramatically speeds up polyline hit detection. For example, we can detect clicks for complicated polylines like the query Washington to San Francisco. This polyline has around 2000 points.
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.
We can apply 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.
