//////////////////////// Geometry functions /////////////////////////////////


// simple box/extent intersection. b1 and b2 are 4-element arrays
function boxesIntersect (b1, b2)
{
	if (b1[0] > b2[2] || b1[2] < b2[0]) return false
	if (b1[1] > b2[3] || b1[3] < b2[1]) return false
	return true
}

// return true if b1 contains b2
function rectangleContains(b1, b2)
{
  return b1[0] <= b2[0] && b1[1] <= b2[1] && b1[2] >= b2[2] && b1[3] >= b2[3]
}

function getNearestPolylinePoint (p, polyline) // returns {point, nearestDistance, cumulativeDistance, index, linkLength)
{
  var cumDist = 0
  var linkLength = 0
  var index = -1
  
  var bd
  var distanceAlong
  var dSmallest
  var point
  
  var dSmallest = 1e20
  
  linkLength = 0
  for (var i=1; i<polyline.length; i++)
  {
    bd = distancePointLineSquared(p, polyline[i-1], polyline[i])
    if (bd.distanceSquared < dSmallest)
    {
      dSmallest = bd.distanceSquared
      distanceAlong = Math.sqrt(bd.distanceAlongSquared)
      cumDist = linkLength + distanceAlong
      index = i
      point = bd.point
    }
    linkLength += Math.sqrt(bd.baseSquared)
  }
  
  return {point:point, nearestDistance:Math.sqrt(dSmallest), cumulativeDistance:cumDist, index:0, linkLength:linkLength}
}

function pointAlongLine (p1, p2, fract)
{
  var e = p2[0] - p1[0]
  var n = p2[1] - p1[1]
  return [p1[0] + fract*e, p1[1] + fract*n]
}

function distancePointLineSquared(p, p1, p2) // returns {distanceSquared, baseSquared, distanceAlongSquared}
{
  var d
  var distanceAlong
  var pt
  
  var dsq = distancePointPointSquared(p1, p2)
  var d1sq = distancePointPointSquared(p, p1)
  var d2sq = distancePointPointSquared(p, p2)
  
  if (d2sq >= d1sq + dsq)
  {
    d = d1sq
    distanceAlong = 0
    pt = p1
  }
  else if (d1sq >= d2sq + dsq)
  {
    d = d2sq
    distanceAlong = dsq
    pt = p2
  }
  else if (dsq < 1e-6 * (d1sq + d2sq))
  {
    d = 0.5 * (d1sq + d2sq)
    distanceAlong = dsq / 4
    pt = p1
  }
  else
  {
    var area = areaOfTriangleDoubled(p, p1, p2)
    d = area * area / dsq
    distanceAlong = d1sq - d
    var e = p2[0] - p1[0]
    var n = p2[1] - p1[1]
    var fract = Math.sqrt(distanceAlong/dsq)
    pt = [p1[0] + fract*e, p1[1] + fract*n]
  }

  return {distanceSquared:d, baseSquared:dsq, distanceAlongSquared:distanceAlong, point:pt}
  
}

function distancePointPointSquared(p1, p2)
{

  var E_diff = p1[0] - p2[0]
  var N_diff = p1[1] - p2[1]

  return (E_diff * E_diff) + (N_diff * N_diff)
}

function areaOfTriangleDoubled(p1, p2, p3)
{ 
  var E1 = p1[0] - p3[0]
  var N1 = p2[1] - p3[1]
  var E2 = p2[0] - p3[0]
  var N2 = p1[1] - p3[1]

  return (E1 * N1) - (E2 * N2)
}