Being able to search POI (points of interest) along a route within certain lateral range is a desirable feature for location based services. It makes the search result more relevant. For example, we may prefer a gas station that is 10 miles down on our route to a gas station that is 5 miles deviated from our route. Also, in geofencing applications we want to limit a vehicle, say a truck transporting hazardous materials, to travel only in a corridor area encompassing a predefined route. In this post, I will show you how to generate a corridor polygon for a given route and a radius - the lateral distance on each side of the route.
Consider a route consisting of a series of line segments. Take any two adjacent segments such as AB and BC and form a rectangle around each segment such as D'DEE' and G'GHH' as shown in Fig. 1.
Fig. 1. Two Adjacent Line Segments
If line segments AB and BC are not exactly in the same line, the two rectangles will have an overlapping region BE'F'G' on one side of the route and a gap BEFG on the other side. If we can find the intersecting points F and F', we can form the polygon D'DFHH'F'D' that closes the gap and eliminates the overlapping region. To do so, we first find the the coordinates of the four corners of the rectangle D'DEE' in terms of coordinates of points A and B and the radius r, as shown in Fig. 2.
Fig. 2. Coordinates of D, D', E and E'
Similarly, we can find the four corners of the rectangle G'GHH' in terms of coordinates of B and C and r, as shown in Fig. 3.
Fig. 3. Coordinates of G', G, H, and H'
The order of the points is important when dealing with polygons. We always order our points clockwise. Note that point F is the intersecting point of lines DF and HF, which can be expressed as follows:
Fig. 4. Equations for Lines DF and HF
This is based on the fact that line DF has same slope as that of line AB and line HF has same slope as that of line BC. Now substitute point F in both equations and solve them for its coordinates:
Fig. 5. Coordinates of Point F
Similarly, we can obtain the coordinates of the intersecting point F':
Fig. 6. Coordinates of Point F'
There are some special cases to consider, including when the slope of one of the two segments is infinity, the slopes of both segments are infinity, and the slopes of both segments are equal but not infinity. All of these cases can be solved easily with above formulas in some reduced forms, so I will not cover them here in detail.
For a route with complex shape and many line segments, finding the corridor polygon is not as easy as just tracking the corner points and intersecting points because the corridor polygon may tangle or intersect itself or may even form holes inside it. To deal with these possible situations we need to apply our formulas in conjunction with polygon union operation. The basic idea is that once we find the intersecting points F and F', we treat D'DFF' and F'FHH' as two separate polygons, which will be called segment polygons, and remove their intersecting line FF' to form a single polygon, which will be called union polygon, through polygon union operation. We can devise an algorithm that applies the idea repeatedly to all adjacent segments of a route. Here is a high-level description of the algorithm:
- Find the first and the second segment polygons, a and b;
- Assign a to a variable u, representing the current union polygon;
- Assign b to a variable p, representing the polygon to be unioned with u;
- Find the next pair of adjacent segments' segment polygons, a and b; (Note: if current pair are the 1st and 2nd segments, the next pair will be the 2nd and 3rd, and the next next pair will be the 3rd and 4th, and so on.)
- Replace p's two vertexes with a's two corresponding vertexes;
- Union p with u and assign the result to u;
- Repeat steps 3 to 6 until the second last segment;
- Union b, which is by now the last segment polygon, with u and assign the result to u.
At the end of the process u becomes our final result. If at any point during the process a segment polygon may tangle or form holes with u, the polygon union algorithm will take care of it.
I should point out that the corridor polygon D'DFHH'F'D' is only an approximate encompassing polygon due to the fact that FB > r, meaning some points in the polygon actually have a distance from the route greater than the radius. This problem gets worse when lines AB and BC forms a sharp angle. We could insert an arc with radius r between E and G (Fig. 7), but that changes the nature of a polygon and thus polygon operation, such as union, would not be applicable. Or, we could find point K, where BK = r, and redefine our segment polygon to include this point, instead of point F, as one of the vertexes. This would be a better approximation.
Fig. 7. Close the Gap with Arc EKG
I wrote a small program in C# to implement the proposed corridor polygon generation algorithm. Fig. 8 shows the user interface of the program:
Fig. 8. Corridor Polygon Generator UI
Here are some highlights about the implementation.
The program takes a route KML file as input and produces a corridor polygon KML as output. The reason for this is that we can visualize the result in Google Earth or Google Maps. In a POI search application, we would probably want to write the corridor polygon to a database so that it can be used in a SQL query to get POIs in the corridor.
The program uses General Polygon Clipping (GPC) library by The University of Manchester for polygon union operation. You can get more information about the library here
For a long, complex route the number of points used to describe the shape of the route (called shape points) can be huge. Lots of points are used to describe small turns, ramps and other trivial road features. Depending on the application, this level of detail may not be needed. If this is the case we can reduce the number of shape points dramatically (while still keeping the basic shape of the route) through a polyline reduction algorithm. In this program the Douglas-Peucker polyline reduction algorithm is used. Polyline Reduction Tolerance controls how severe you want the reduction to be. The bigger the number, the more points are removed from the original data set. Please refer to my earlier post regarding the Douglas-Peucker polyline reduction algorithm here
The idea of a "dog bone" shaped polygon is based on the thinking that once you are at the origin or destination of your route, you may want to look at POIs in a wider area. The feature is implemented by first creating two squares centered at the origin and destination, and then unioning them with the corridor polygon.
The program supports 3D KML output. This is particular useful for visualization of a geo-fence.
The following screenshots of Google Earth show the results from the Corridor Polygon Generator program. You can also view them "live" in Google Earth or Google Maps by clicking corresponding links at the bottom of each screenshot.
Fig. 9 shows a corridor polygon of a simple route. The route consists of only 7 points, as shown under the Route Points folder in the left pane as well as in the map. The corridor polygon is actually drawn as a KML path.
Fig. 9. Corridor Polygon of a Simple Route
Fig. 10 shows a corridor polygon with a hole. In this case the corridor polygon and the hole are drawn as two separate paths as shown in the left pane. If there are more holes, each will be drawn separately.
Fig. 10. Corridor Polygon with a Hole
Fig. 11 shows a corridor polygon for a complex route. To exam how well our algorithm works with a route that has a lot of twists and turns, I select a route that contains a section of highway 330 that passes through San Bernardino National Forest. Notice that the big spike is caused by the sharp angle formed by points 46, 47 and 48. If we have more shape points to describe the route more closely, we can expect that the sharp points will get smoothed out. This is exactly the case demonstrated in Fig. 12.
Fig. 11. Corridor Polygon of a Complex Route
Fig. 12. Corridor Polygon of a Complex Route with More Shape Points (less reduction)
Fig. 13. Dog Bone Shaped Corridor Polygon
Fig. 14. 3D Corridor Polygon Useful for Visualization of a Geo-fence
You can download the executable of the program and all the example route files below. The download also includes the GPC library (gpc.dll). You need to install the .exe and .dll to the same folder. The C# wrapper of the GPC library depends on Microsoft Visual C++ run-time libraries (msvcr71.dll). So make sure it exists on your computer.
CorridorPolygon.zip (36.1 kb)