Google maps api parallel path lines

Question

I am working on a sort of itinerary mapper for packaged vacations, and I'm really happy with what I've done so far; I have the directions api implemented with a custom renderer, so I can take driving directions, and plot my own polyline complete with directional arrows that aren't google's awful ones spaced along the path. I am not exactly a math expert, and I am trying to figure out how I could make a path parallel to another path. For example, the itinerary goes from city 1 to city 2, and then back to city 1.

I want to offset the trip back to city 1's polyline, so that it mirrors the path, but travels parallel to it. Ideally, I would like to when I create the path, check for intersecting points in other paths, and if any are found, offset the path at those points only. This would be a better implementation, because you could for instance parallel the path only where it happens to intersect another one, like when it meets another path only for a short time.

I found this code for API2 from bill chadwick

The link is here: http://wtp2.appspot.com/ParallelLines.htm

Update: Somehow managed to convert this old v2 script to get it working in v3, but I'm experiencing some troubles...

It is more than doubling the original number of points, and following the path, but really throwing them in randomly. Screenshot here:

The class I converted is here:

function BDCCParallelLines(points, color, weight, opacity, opts, gapPx) {   

    console.log('Pllel COnstructor Initialized');
    this.gapPx = gapPx;
    this.points = points;
    this.color = color;
    this.weight = weight;
    this.opacity = opacity;
    this.opts = opts;
    this.line1 = null;
    this.line2 = null;
    this.lstnZoom = null;
}


BDCCParallelLines.prototype = new google.maps.OverlayView();



BDCCParallelLines.prototype.onAdd = function() {
console.log('Pllel Initialized');
this.prj = map.getProjection();

var self = this;
    this.lstnZoom = google.maps.event.addListener(map, "zoom_changed",   function() {
self.recalc();
  });
    this.recalc();//first draw
}


BDCCParallelLines.prototype.onRemove = function() {

    if(this.line2)
        this.line2.setMap(null); 
    if(this.line1)
        this.line1.setMap(null);
    if(this.lstnZoom != null)
        google.maps.event.removeListener(this.lstnZoom);

}

BDCCParallelLines.prototype.copy = function() {
    return new BDCCParallelLines(this.points,this.color,this.weight,this.opacity,this.opts,this.gapPx);
}

BDCCParallelLines.prototype.draw = function(force) {
    return; //do nothing
}




  /**
* @param {google.maps.Map} map
* @param {google.maps.LatLng} latlng
* @param {int} z
* @return {google.maps.Point}
*/
BDCCParallelLines.prototype.latLngToPoint = function(latlng, z){
var normalizedPoint = map.getProjection().fromLatLngToPoint(latlng); // returns x,y normalized to 0~255
var scale = Math.pow(2, z);
var pixelCoordinate = new google.maps.Point(normalizedPoint.x * scale, normalizedPoint.y * scale);
return pixelCoordinate;
};
/**
* @param {google.maps.Map} map
* @param {google.maps.Point} point
* @param {int} z
* @return {google.maps.LatLng}
*/
BDCCParallelLines.prototype.pointToLatlng = function(point, z){
var scale = Math.pow(2, z);
var normalizedPoint = new google.maps.Point(point.x / scale, point.y / scale);
var latlng = map.getProjection().fromPointToLatLng(normalizedPoint);
return latlng;
};


BDCCParallelLines.prototype.recalc = function() {

var distallowance;
console.log('recalc called');
   var zoom = map.getZoom();
   distallowance = 1.6;
   if(zoom > 6){
        distallowance = 1.3;
        if(zoom > 9){
            distallowance = .7;
            if( zoom > 13){
                distallowance = .2;
                if( zoom > 15){
                distallowance = .0001;
                }
                }

            }       
        }
        console.log('Zoom Level: ' + zoom);
        console.log('Allowance = ' + distallowance);


   var pts1 = new Array();//left side of center 

   //shift the pts array away from the centre-line by half the gap + half the line width
   var o = (this.gapPx + this.weight)/2;

   var p2l,p2r;

   for (var i=1; i<this.points.length; i++){

      var p1lm1;
      var p1rm1;
      var p2lm1;
      var p2rm1;
      var thetam1;

      var p1 = this.latLngToPoint(this.points[i-1],  zoom)
      var p2 = this.latLngToPoint(this.points[i],  zoom)
      var theta = Math.atan2(p1.x-p2.x,p1.y-p2.y);  
      theta  = theta + (Math.PI/2);


      var dl = Math.sqrt(((p1.x-p2.x)*(p1.x-p2.x))+((p1.y-p2.y)*(p1.y-p2.y)));  

      if(theta > Math.PI)
          theta -= Math.PI*2; 
      var dx = Math.round(o * Math.sin(theta));
      var dy = Math.round(o * Math.cos(theta));

      var p1l = new google.maps.Point(p1.x+dx,p1.y+dy);
      var p1r = new google.maps.Point(p1.x-dx,p1.y-dy); 
      p2l = new google.maps.Point(p2.x+dx,p2.y+dy);
      p2r = new google.maps.Point(p2.x-dx,p2.y-dy);

      if(i==1){   //first point
        pts1.push(this.pointToLatlng(p1l,zoom));
      }
      else{ // mid this.points

  if(distbetweentwo(this.points[i-1], this.points[i]) > distallowance){

        if(theta == thetam1){
            // adjacent segments in a straight line 
        pts1.push(this.pointToLatlng(p1l,zoom));
        }
        else{
            var pli = this.intersect(p1lm1,p2lm1,p1l,p2l);
            var pri = this.intersect(p1rm1,p2rm1,p1r,p2r);

            var dlxi = (pli.x-p1.x);
            var dlyi = (pli.y-p1.y);
            var drxi = (pri.x-p1.x);
            var dryi = (pri.y-p1.y);
        var di = Math.sqrt((drxi*drxi)+(dryi*dryi));  
            var s = o / di;

            var dTheta = theta - thetam1;
            if(dTheta < (Math.PI*2))
                dTheta += Math.PI*2;
            if(dTheta > (Math.PI*2))
                dTheta -= Math.PI*2;

            if(dTheta < Math.PI){
               //intersect point on outside bend
             pts1.push(this.pointToLatlng(p2lm1,zoom));
             pts1.push(this.pointToLatlng(new google.maps.Point(p1.x+(s*dlxi),p1.y+(s*dlyi)),zoom));
             pts1.push(this.pointToLatlng(p1l,zoom));


            }
        else if (di < dl){

        pts1.push(this.pointToLatlng(pli,zoom));

        }
            else{

              pts1.push(this.pointToLatlng(p2lm1,zoom));
              pts1.push(this.pointToLatlng(p1l,zoom));

        }



        }

    }
    else{
    //console.log(distbetweentwo(this.points[i-1], this.points[i]));
    }
    }




      p1lm1 = p1l;
      p1rm1 = p1r;
      p2lm1 = p2l;
      p2rm1 = p2r;
      thetam1 = theta;

      //end loop
    }

   pts1.push(this.pointToLatlng(p2l,zoom));//final point

  // console.log(pts1);

   if(this.line1)
    this.line1.setMap(null);
        this.line1 = new google.maps.Polyline({
        strokeColor: this.color,
        strokeOpacity: this.opacity,
        strokeWeight: this.weight,
        map: map,
        path: pts1 });


   this.line1.setMap(map);


}

BDCCParallelLines.prototype.intersect = function(p0,p1,p2,p3)
{
// this function computes the intersection of the sent lines p0-p1 and p2-p3
// and returns the intersection point, 

var a1,b1,c1, // constants of linear equations
    a2,b2,c2,
    det_inv,  // the inverse of the determinant of the coefficient matrix
    m1,m2;    // the slopes of each line

var x0 = p0.x;
var y0 = p0.y;
var x1 = p1.x;
var y1 = p1.y;
var x2 = p2.x;
var y2 = p2.y;
var x3 = p3.x;
var y3 = p3.y;

// compute slopes, note the cludge for infinity, however, this will
// be close enough

if ((x1-x0)!=0)
   m1 = (y1-y0)/(x1-x0);
else
   m1 = 1e+10;   // close enough to infinity

if ((x3-x2)!=0)
   m2 = (y3-y2)/(x3-x2);
else
   m2 = 1e+10;   // close enough to infinity

// compute constants

a1 = m1;
a2 = m2;

b1 = -1;
b2 = -1;

c1 = (y0-m1*x0);
c2 = (y2-m2*x2);

// compute the inverse of the determinate

det_inv = 1/(a1*b2 - a2*b1);

// use Kramers rule to compute xi and yi

var xi=((b1*c2 - b2*c1)*det_inv);
var yi=((a2*c1 - a1*c2)*det_inv);

return new google.maps.Point(Math.round(xi),Math.round(yi));

}

This is working to a point... It is working as well as the original implementation. The entire path is recalculated on a zoom basis, and I kind of hacked the function to skip very short paths(weird angles) at higher zoom levels, it more closely follows the path the more you zoom in.

I would rather just have a fixed distance offset that is not recalculated, as it is pretty intensive... There are many programs which accomplish this feat, rhino3d, autocad, illustrator... I feel like it would be great for driving directions for google maps itself, an offsetting of the path so you can distinguish the return trip and the original trip.

If anybody has done anything similar to this in JS even if its not for google maps specifically, I would love to see it. Links I am investigating:

http://processingjs.nihongoresources.com/bezierinfo/

http://www.groupsrv.com/computers/about21532.html

Answer 1

Offsetting paths in general is a pretty tricky buisness. This paper (scientific paper alert) gives a good description of the steps taken for 'professional' offset algorithms.

http://cgcad.thss.tsinghua.edu.cn/~yongjh/papers/CiI2007V58N03P0240.pdf

Answer 2

You don't seem to want anything as fancy as in the demo. From what I gather you just want the same polyline, only shifted some pixels to the right and maybe some to the top so it doesn't overlap.

The code you posted has a latLngToPoint function and pointToLatLng function. I think the directions you get from Google are LatLng, so you can convert those to Points, increase the x and y property, and convert it back to a LatLng and draw your Polyline.

This should get you a line that exactly follows the original line. But, it wont look as fancy as the one in the demo. Since it wont be adding any points to smooth the line.