Corridor Polygon Generation

by Gong Liu February 13, 2011 14:13

Problem Statement

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. 

Formulation

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:

  1. Find the first and the second segment polygons, a and b;
  2. Assign a to a variable u, representing the current union polygon;
  3. Assign b to a variable p, representing the polygon to be unioned with u;
  4. 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.)
  5. Replace p's two vertexes with a's two corresponding vertexes;
  6. Union p with u and assign the result to u;
  7. Repeat steps 3 to 6 until the second last segment;
  8. 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

Implementation

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. 

Examples

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

Download

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)

A Linear Clustering Algorithm for Virtual Earth

by Gong Liu May 22, 2009 05:12

Official Tracker for Katie Visco's Run Across America   

A while ago a friend showed me a piece of news about a girl named Katie Visco who is about to become the youngest female ever to run solo across America. I thought her story was very inspirational and contacted her about tracking her run on the internet. She was thrilled about the idea and I ended up hosting and maintaining the following tracker about her run. I update the tracker every day based on the mileage log published on her blog site Pave Your Lane

Technical Notes

Linear Clustering Algorithm  

The above tracker is very similar to my workout tracker. However, one key difference is that her tracker shows every day on the map while my tracker only shows my workout days. In her case, the running days are marked by a little red square  and the resting days by a little yellow square . On some resting days she may stay at the same location and thus the day markers overlap. If you hover the mouse cursor on overlapped markers, only the infobox of the top most marker is shown, no matter how closely you zoom in. In the above tracker I have solved the problem by representing overlapped markers with a bigger yellow square . When you hover the mouse cursor on the bigger marker, you will see a list of days it represents. Clicking on one of the days will show that day's infobox at the same location. The technique behind the solution is called pushpin clustering. Pushpin clustering is a process of representing several nearby pushpins with a single pushpin. The original purpose of this is to reduce overcrowded pushpins that may obscure the map underneath. We use pushpin clustering to gain access to overlapped pushpins or markers. Overcrowding is not much of a concern here. Before Virtual Earth 6.2, developers using the Virtual Earth map control would have to either divide groups of pushpins into shape layers and manually control which layers to show and hide at different zoom levels, or just not show pushpins at zoom levels if there were too many on the screen. With Virtual Earth 6.2, it becomes a lot easier to control which pushpins are clustered and how a cluster is displayed.

There are two overloaded methods related to pushpin clustering in VE 6.2:

VEShapeLayer.SetClusteringConfiguration(type, options)
VEShapeLayer.SetClusteringConfiguration(algorithm, options)

The first method allows you to choose one of the pre-defined clustering algorithms. In VE 6.2, there is only one pre-defined clustering algorithm - the grid clustering algorithm. The grid clustering algorithm divides map screen into grids and pushpins falling in one grid are represented by a single pushpin at the grid center. The second method allows you to define your own clustering algorithm. The second parameter in both methods, options, is a VEClusteringOptions object that specifies how a pushpin cluster is displayed in terms of an icon and a callback function where you put your own code to do something about each cluster, such as rendering an infobox.

In our case, the day markers are along some line features (roads), and we are only interested in making overlapped markers into clusters. So the pre-defined grid algorithm is not applicable. We have to roll out our own algorithm, which I call a linear clustering algorithm because of the unique spatial distribution of our markers.

Simply stated, any two or more consecutive markers that overlap or are close enough form a cluster. The following figures show when markers form a cluster and when they don't according to our linear clustering algorithm.
   

The current marker (black square) in A) does not belong to any cluster because none of its consecutive markers (markers immediately before and after it) is close enough to it. By close enough we mean within a pre-defined square area (or a circle). The side d of the square area is measured in degrees same as latitude/longitude, instead of pixels, and thus the clustering does not change with different zoom levels. By our definition the current marker in B) forms a cluster with its next marker. Backtracking and loop as shown in C) and D) do not form a cluster, because the two markers in the square are not consecutive.

Now let's take a look at some code snips.

    ......
    //load day markers to the third layer
    var layer3 = new VEShapeLayer(); 
    var co = new VEClusteringOptions();
    var customIcon = new VECustomIconSpecification();
    customIcon.CustomHTML = "<div style='margin-top: 10px; margin-left: 10px'><img src='images/yellowsquarelarge.gif' width='8' height='8'></div>";
    co.Icon = customIcon;
    co.Callback = ClusterCallback;
    layer3.SetClusteringConfiguration(LinearClusterAlgorithm, co);
    map.AddShapeLayer(layer3);
    var shapes = new Array();
    for (var i = 0; i < days.length; i++)
    {
        var sh = new VEShape(VEShapeType.Pushpin, days[i].CityCenter);
        sh.SetTitle(days[i].Date.toDateString() + " - Day " + (i + 1));
        if (days[i].RunningDay)
            sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/redsquare.gif' width='5' height='5'></div>");
        else
            sh.SetCustomIcon("<div style='margin-top: 11px; margin-left: 10px'><img src='images/yellowsquare.gif' width='5' height='5'></div>");   
        sh.SetDescription(days[i].GetHTML());
        shapes[i] = sh;
    }
    layer3.AddShape(shapes);  
    ......

The above code snip shows that a shape layer is created for day markers. The SetClusteringConfiguration method indicates that the layer is configured to do clustering. The clustering algorithm is defined by a function called LinearClusterAlgorithm and any cluster is going to be dispayed according to the way specified in a VEClusteringOptions object, which includes a display icon (the bigger yellow square ) and a callback function ClusterCallback. The for loop creates day markers as an array of shapes, which is then added to the layer in a batch.

The function LinearClusterAlgorithm is defined as:

function LinearClusterAlgorithm(sLayer)
{
    var arrCSs = new Array();
    var n = sLayer.GetShapeCount();
    if (n > 0) 
    {
        var shape0 = sLayer.GetShapeByIndex(0);
        var pt0 = shape0.GetPoints()[0];
        var clusterSpec = null;
        for(var i = 1; i < n; i++)
        {
            var shape1 = sLayer.GetShapeByIndex(i);
            var pt1 = shape1.GetPoints()[0];
            if (Overlap(pt0, pt1))
            {
                if (clusterSpec == null)
                {
                    clusterSpec = new VEClusterSpecification();
                    clusterSpec.Shapes = new Array();
                    clusterSpec.Shapes.push(shape0);
                }
                clusterSpec.Shapes.push(shape1);
                clusterSpec.LatLong = pt1;
                if (i == n-1)
                    arrCSs.push(clusterSpec);   
            }
            else
            {
                if (clusterSpec != null)
                {
                    arrCSs.push(clusterSpec);
                    clusterSpec = null;
                }
            }
           
            shape0 = shape1;
            pt0 = pt1;     
        }
    }
    return arrCSs;
}

function Overlap(pt0, pt1)
{
    var dd = 0.0001;
    return (Math.abs(pt0.Latitude - pt1.Latitude) < dd && 
            Math.abs(pt0.Longitude - pt1.Longitude) < dd);
}

Here, sLayer is a VEShapeLayer object that the algorithm is going to apply to. The main part of the algorithm consists of a for loop that compares first two consecutive shape points, points 0 and 1, then points 1 and 2, and so on. If any two consecutive points overlap, they form a cluster and are added to the Shapes property of a VEClusterSpecification object. Otherwise, the VEClusterSpecification object is added to an array, which is returned to caller at the end of the loop. The function Overlap is used to determine if two points overlap. "Overlap" does not necessarily mean the two points have to have the same coordinates, but rather their differences are within a pre-defined range.

The ClusterCallback function is as follow:

function ClusterCallback(CSs)
{
    for (var i=0; i < CSs.length; ++i)
    {
        var clusterSpec = CSs[i];
        var clusterShape = clusterSpec.GetClusterShape();
        var shapes = clusterSpec.Shapes;
        clusterShape.SetTitle(shapes.length + " Days");
        var html = "";
        for (var j = 0; j < shapes.length; j++)
        {
            var shape = shapes[j];
            var icon = (shape.GetDescription().indexOf("alt='run'") > 0)? "redsquare.gif" : "yellowsquare.gif";
            html += "<img border='1' src=\"Images/" + icon + "\"> ";
            html += "<a href=\"Javascript: map.HideInfoBox(); ShowInfo('" + shape.GetID() + "')\">" + shape.GetTitle() + "</a><br>"
        }
        clusterShape.SetDescription(html);
    }
}

It accepts an array of VEClusterSpecification objects as parameter, each of which represents a cluster. Each cluster has at least two shape points. The inner for loop uses the info of these points to construct a html snip that is to be used as the description of the cluster's infobox.

When there are overlapped day markers, the touring feature is affected. This is because the ShowInfoBox method is normally called immediately after the map is panned from one point to the next (in the onendpan event handler). But if two or more points overlap, there is no pan action and the onendpan event will not fire, and thus the corresponding infoboxes will not show. To overcome this, we have to call the handler directly at the time an overlap is detected.

Image Overlay

The above tracker has a title image along the top side. Notice that the image is on top of the map layer but under the map control panel, and that the portion of the map that is under the image is still responsive to mouse drag. To overlay the image, I add an image tag just before the myMap div tag:

<img src="images/title.jpg" id="overlay" style="z-index:50; opacity: 0.7; filter: alpha(opacity=70); position:absolute; left:0px; top:0px" alt="pave your lane" />
<div id="myMap" style="width:800;height:600;position:relative;"></div> 

The style opacity: 0.7 works for Firefox and filter: alpha(opacity=70) works for IE 7.0+. So I use both. They make the image semi-transparent. z-index must be > 0, otherwise the image is put behind the map and thus can't be seen. 

The problem with the image tag itself is that it sits on top of both the map layer and the map control panel and make them not responsive to mouse actions. To solve this problem we have to add the image tag as a child node of the myMap div tag:

var veLayer = document.getElementById('myMap');
var imageOverlay = document.getElementById('overlay');
veLayer.appendChild(imageOverlay);  

Finally we have to make sure that the z-index of the image tag is between 1 and 99. A z-index value greater than 99 will put the title image above the map control panel, making it unusable.

Another possible way to overlay an image is to use a custom layer, a feature newly available in VE 6.2.  I tried this way but was unable to anchor the image to the top left corner - the image moves as the map is panned. If you know how to do this using custom layer, please let me know.

About

A seasoned computer professional. A tofu culture evangelist...
more >>

Tag Cloud

Calendar

<<  April 2017  >>
MoTuWeThFrSaSu
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

View posts in large calendar
Copyright © 2008-2011 Gong Liu. All rights reserved. | credits | contact me
The content on this site represents my own personal opinions, and does not reflect those of my employer in any way.