/* ============================== DpPolyline ===========================================
Version 0.82 2007-07-08
History 
2007-07-08 RRH added block out coordinates
 
Copyright 2007, Expertech, Ltd. (www.xltd.com www.bike-routes.org)
This code may be freely used for personal use providing that this copyright notice is included with it.
Expertech, Ltd. makes no warranty for this code, and cannot be held liable for any real or imagined damage resulting from its use.
Users of this code must verify correctness for their application.

A modified port of the REDUCE functionality from GEOCONV (Eino Uikkanen  18.06.2005 00:39)
http://www.kolumbus.fi/eino.uikkanen/geoconvgb/index.htm
Which is turn is a slightly modified version of the Douglas-Peucker algorithm. 
http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm 

Short functional description of the algorithm
1.      Draw a leg (line segment) from the first to the last point of the track log.
2.      Of the points, which are between start and end points of the leg,
        select the point with greatest distance from the leg. Let's
        call the distance MaxDist and the point MaxDistPoint.
3.      If requirements to the reduction are achieved (number of points
        is equal to the required number of points or calculated distance
        error is equal to or less than the required maximum error), stop.
4.      Select the leg, which has the greatest MaxDist.
5.      Replace the leg with two legs: from start point of the leg to the
        MaxDistPoint and from MaxDistPoint to end point of the leg. Find
        MaxDist and MaxDistPoint for both new legs.
6.      Goto step 3.

Usage of this implementation 
init(maxDist, pointCount, [gpxDom])
     Initialize and open the routine. Pass the requirements to the routine.
       maxDist: Max. distance error after reducing, e.g. 100.0, default 0.0
       pointCount: Max. number of points after reducing, e.g. 40
       gpxDom (optional): an HTML DOM object that comtains a gpx trk consisting of one or more trkpt

reduce()
     Do the actual reduction. 
     Returns a reduced version fo the passed in gpxDom with trkpts eliminated based on the paramters and input gpxDom

loadGpx (gpxDom) 
      Add the points of the original track log. Can be called separately from init to avoid having to keep setting the parameters 

*/
function DpPoint(x, y) {
  this.x  = x // double
  this.y = y // double
  this.isSelected = false; //integer         Point is selected to the reduced track
  this.isLegStart = false; // integer    Is Start of leg
  this.isLegEnd = false; // integer    Is End of leg
}

function DpLeg(sp, ep, mdp, md) {
  this.startPoint = sp; // long
  this.endPoint = ep; // long
  this.maxDistPoint = mdp; // long
  this.maxDist = md; // double
}

function BlockOut(ulx, uly, lrx, lry, prx, pry, random) {
  // bounding box to ignore trackpoints that fall within the rectangle. If proxy points provided, then replace with these values  
  this.ulx = ulx; // double
  this.uly = uly; // double
  this.lry = lry; // double
  this.prx = prx; // double
  this.pry = pry; // double
  this.random = random // boolean
}

var DpPolyline = {
  _gpx : null, // array of DpPoint
  _PPOINT : new Array(), // array of DpPoint
  _ALEG : new Array(), // array of DpLeg
  _origPointCount : 0, // integer
  _targetPointCount : 200, // integer
  _targetMaxDist : 0, // float
  _finalPointCount : 0, // integer
  _FinalMaxDist : 0, // float
  _blockMaxDist : 0, // float
  _resultGpxStr : "", 
  _blockOut : new BlockOut(),

  init : function(maxDist, pointCount, gpxDom) {
    this._PPOINT = new Array();
    this._ALEG = new Array();
    this._origPointCount = 0;
    this._finalPointCount = 0;
    this._FinalMaxDist = 0;
    this._blockMaxDist = 0;
    this._resultGpxStr = "";
    this._targetMaxDist = maxDist;
    this._targetPointCount = pointCount;
    this.loadGpx(gpxDom);
  },

  setBlockout : function(ulx, uly, lrx, lry, prx, pry, random) {
    this._blockOut.ulx = ulx;
    this._blockOut.uly = uly;
    this._blockOut.lrx = lrx;
    this._blockOut.lry = lry;
    this._blockOut.prx = prx;
    this._blockOut.pry = pry;
    this._blockOut.random = random;
  },

  getResult : function() {
    return this._resultGpxStr;
  },

  loadGpx : function (gpxDom) {
    var trk = gpxDom.getElementsByTagName('trkpt');
    if (!trk || trk.length == 0 || trk.length <= this._targetPointCount) {
      if (trk || trk.length > 0 ) {
        this._origPointCount = trk.length;
      }
      //alert("nothing to do!");
    } else {
      for (var i = 0; i < trk.length; i++) { 
        lat = trk[i].getAttribute("lat"); 
        lon = trk[i].getAttribute("lon"); 
        var pt = new DpPoint(lon, lat);
        this._adjustCoordinatesForBlockout(pt);
        this._PPOINT[i] = pt;
        if (i == 0) {
          this._PPOINT[0].isLegStart = true;
          this._setPointSelection(0, true);
        }
      }
      var endNdx = this._PPOINT.length-1;
      this._PPOINT[endNdx].isLegEnd = true;
      this._setPointSelection(endNdx, true);
      this._origPointCount = this._PPOINT.length;
      this._gpx = gpxDom;
      this._ALEG = new Array();
    }
  },

  _adjustCoordinatesForBlockout : function (pt) {
    if (new Number(pt.x) > new Number(this._blockOut.ulx) 
     && new Number(pt.x) < new Number(this._blockOut.lrx)
     && new Number(pt.y) < new Number(this._blockOut.uly)
     && new Number(pt.y) > new Number(this._blockOut.lry)) {
      pt.x = this._blockOut.prx = this._blockOut.prx;
      pt.y = this._blockOut.pry = this._blockOut.pry;
    }
  },

  reduce : function () {
    var origPointCount = this._origPointCount;
    var targetPointCount = this._targetPointCount;
    if (origPointCount > 0 && (targetPointCount < origPointCount)) {
        this._Reduce2();
        this._buildResultGpx()
    } else {
      this._finalPointCount = origPointCount;
      this._FinalMaxDist = 0;
    }
  },

  displayStats : function () {
    alert(
    "\norigPointCount :" + this._origPointCount +
    "\ntargetPointCount :" + this._targetPointCount +
    "\ntargetMaxDist :" + this._targetMaxDist +
    "\nfinalPointCount :" + this._finalPointCount +
    "\nFinalMaxDist :" + this._FinalMaxDist +
    "\nblockMaxDist :" + this._blockMaxDist);
  },

    _Reduce2 : function() {
    var origPointCount = this._origPointCount;
    var targetPointCount = this._targetPointCount;
    if (targetPointCount > 0) {
      this._reduceBlock(0, origPointCount-1);
    } else {
      var lastReduced = 0; 
      for (var i=0; i<origPointCount; i++) {
        var isEndBlock = false;
        this._setPointSelection(i, true);
        isEndBlock = true;
        if (!isEndBlock) {
          isEndBlock = this._PPOINT[i].isLegEnd;
        } 
        if (isEndBlock) {
          this._blockMaxDist = 0;
          if (lastReduced < i) {
            this._reduceBlock(lastReduced, i);
          }
          lastReduced = i+1;
        }
      }
    }
  },
  
  _setPointSelection : function (i, isSelected) {
    var pt = this._PPOINT[i];
    if (pt.isSelected != isSelected) {
      pt.isSelected = isSelected;
      if (isSelected) {
        this._finalPointCount++;
      }
    }
  },
  
  _reduceBlock : function (BlockStartPoint, BlockEndPoint) {
    // First create the first leg from the start to the end of the full polyline
    this._addLeg(BlockStartPoint, BlockEndPoint);
  
    // Split the leg with greatest MaxDist into two legs until requirements
    // are satisfied or all points of the original track are selected to the
    // reduced track (= there are no legs to split). After sort the last leg
    // (to which LegCount& currently refers) has the greatest MaxDist# and is
    // thus the one to be deleted and split.
    var targetReductionMet = this._targetReductionMet();
    while (!targetReductionMet && (this._ALEG.length > 0)) { 
      // Save values of the leg to split ...
      var ndx = this._LEGMaxDistNdx();
      var PLEG = this._GETLEG(ndx);
      // split it into two legs, add them to the collection
      this._addLeg(PLEG.startPoint, PLEG.maxDistPoint);
      this._addLeg(PLEG.maxDistPoint, PLEG.endPoint);
      // ... then remove the leg just split
      this._DELLEG (ndx);
      // Select MaxDistPoint to the reduced track (StartPoint and EndPoint are already selected). 
      // MaxDistPoint =  last selected point.
      // MaxDist is the MaxDist of the entire reduced route AFTER selection of MaxDistPoint&, 
      //   not MaxDistPoint&s distance from its leg (= StartPoint, EndPoint).
      if (this._ALEG.length > 0) {
        this._setPointSelection(PLEG.maxDistPoint, true);
      }
      targetReductionMet = this._targetReductionMet();
    }
    if (this._FinalMaxDist< this._blockMaxDist) {
      this._FinalMaxDist = this._blockMaxDist;
    }
  },

  _addLeg : function (startPtNdx, endPtNdx) {
    if (startPtNdx < (endPtNdx - 1)) {
      var legNdx = this._ALEG.length;
      var PLEG = new DpLeg(startPtNdx, endPtNdx, startPtNdx, 0);
      this._PUTLEG(legNdx, PLEG);
      PLEG = this._GETLEG(legNdx);
      // Find the point with the greatest distance
      var startPt = this._PPOINT[startPtNdx];
      var endPt = this._PPOINT[endPtNdx];
      //var debugStr = "";
      for (var i = startPtNdx+1; i<endPtNdx; i++) {
        var midPt = this._PPOINT[i];
        var dist = this._pointsDistFromLeg(startPt.x, startPt.y, endPt.x, endPt.y, midPt.x, midPt.y);
        if (dist > PLEG.maxDist) {
          PLEG.maxDist = dist;
          PLEG.maxDistPoint = i;
          //debugStr += '***'
        }
        //debugStr += "pt:" + i + " dist:" + dist + " x:" + this._PPOINT[i].x + " y:" + this._PPOINT[i].y + "\n";  
      }
      
      // Current value of BlockMaxDist is PLEG.MaxDist
      this._blockMaxDist = PLEG.maxDist;
    }
  },

  __targetReductionMet : function(targetPointCount, finalPointCount, targetMaxDist, blockMaxDist) {
    var OK = true;
    if (targetPointCount > 0) {
      OK = (finalPointCount >= targetPointCount);
    } else if (targetMaxDist > 0) {
      if (blockMaxDist > targetMaxDist) {
        OK = false;
      }
    }
    return OK;
  },
  
  _targetReductionMet : function() {
    return this.__targetReductionMet(
      this._targetPointCount, 
      this._finalPointCount, 
      this._targetMaxDist, 
      this._blockMaxDist);
  },
  
  _sortLegs : function (LowInd, HighInd) {
    var i = LowInd;
    var j = HighInd;
    if (j > i) {
      k = Math.floor((i+j)/2);
      var CompKey = this._LEGMaxDist(k);
      while (j >= i) {
        Sortkeyi = this._LEGMaxDist(i);
        while (SortKeyi < CompKey) {
          Sortkeyi = this._LEGMaxDist(++i);
        }
        SortKeyj = this._LEGMaxDist(j);
        while (SortKeyj > CompKey) {
          Sortkeyj = this._LEGMaxDist(++j);
        }
        if (i <= j) {
          // SWAP
          var iLeg = this._GETLEG(i);
          var jLeg = this._GETLEG(j);
          this._PUTLEG(j, iLeg);
          this._PUTLEG(i, jLeg);
          i++;
          j++;
        }
      }
      this._sortLegs(LowInd, j);
      this._sortLegs(i, HighInd);
    }
  },
  
  _pointsDistFromLeg : function (x1, y1, x2, y2, x, y) {
    // Point coordinates x1, y1, x2, y2, x and y are supposed to be two-dimensional grid coordinates. 
    // If not, this routine must be modified accordingly.
    // Calculate leg dependent parameters (Ad, Bd, Cd and LegLen).
    var A = y1 - y2;
    var B = x2 - x1;
    var C = y2 * x1 - y1 * x2;
    var LegLen = Math.sqrt(Math.pow(A,2) + Math.pow(B,2));
    var Ad, Bd, Cd; 
    if (LegLen != 0) {
      Ad = A/LegLen;
      Bd = B/LegLen;
      Cd = C/LegLen;
    }
  
    // Points distance from the StartPoint (x1,y1) of the Leg
    var dist, dist1, dist2;
    var dist1 = Math.sqrt(Math.pow(x-x1,2) + Math.pow(y-y1,2));
    if (LegLen == 0) {
      // If the leg is a point, distance from either end of the leg
      dist = dist1;
    } else {
      // Points distance from the EndPoint (x2,y2) of the Leg
      dist2 = Math.sqrt(Math.pow(x-x2,2) + Math.pow(y-y2,2));
      // Set dist1 <=  dist2 , so we know, which one is shortest
      if (dist1 > dist2) {
        // SWAP dist1, dist2
        var tmp = dist1;
        dist2 = dist1;
        dist1 = tmp;
      }
      // check with Pythagora's theorem, if points distance from the leg is ...
      if (Math.pow(dist1,2) + Math.pow(LegLen,2) > Math.pow(dist2,2)) {
        // ... points distance from the leg-line or ...
        dist = Math.abs(Ad*x + Bd*y + Cd);
      } else {
    // ... points distance from the closer leg-end
        dist = dist1;
      }
    }
    return dist;
  }, 
  
  _PUTLEG : function (i, XLEG) { //XLEG AS DpLeg
    this._ALEG[i] = XLEG;
  },
  
  _GETLEG : function (i) { //XLEG AS DpLeg
    return this._ALEG[i];
  },
  
  _setLegEnd : function (i) {
    this._PPOINT[i].isLegEnd = true;
    this._setPointSelection(i, true);
  },
    
  _LEGMaxDist: function (i) {
    return this._GETLEG(i).maxDist;
  },

  _DELLEG : function (i) { 
    this._ALEG.splice(i,1);
  },

  _LEGMaxDistNdx: function() {
    if (this._ALEG.length > 0) {
      var ndx = 0;
      var maxDist = 0;
      for (i=0; i<this._ALEG.length; i++) {
        if (this._ALEG[i].maxDist > maxDist) {
          ndx = i;
          maxDist = this._ALEG[i].maxDist;
        }
      }
    }
    return ndx;
  },

  _buildResultGpx : function() {
    var gpx = '<gpx version="1.0">\n  <desc>Reduced file</desc>\n<trk>\n';
    for (var i=0; i<this._PPOINT.length; i++) {
      var pt = this._PPOINT[i];
      if (pt.isSelected) {
        gpx += '<trkpt lat="' + pt.y + '" lon="' + pt.x + '"/>\n';
      }
    }
    gpx += '</trk>\n</gpx>';
    this._resultGpxStr = gpx;
  }
}