--@ Version: 1.1.0
--@ Author Luke Wigley

--@ Description
-- Some useful functions for determining intersections with points, lines and quads.


-------------------------------------------
-- POINTS 
-------------------------------------------

on PointInsideQuad (aQuad, aPnt)
  -- returns TRUE if aPnt is on or inside aQuad
  
  repeat with side = 1 to 4
    -- get the line segment
    pnt1 = aQuad[side]
    if side < 4 then pnt2 = aQuad[side+1]
    else pnt2 =aQuad[1]
    -- determine which side of the line the test point is
    WhichSide = aPnt.locV - pnt1.locV - ( (pnt2.locV-pnt1.locV) / (pnt2.locH - pnt1.locH) ) * (aPnt.locH - pnt1.locH)
    if whichSide = 0 then return TRUE -- point is on the edge
    else whichSide = whichSide/abs(whichSide) -- just need to know  with positive or neg
    -- check that the next point in the quad is on the same side as the test point
    if side < 3 then pnt3 = aQuad[side+2]
    else pnt3 = aQuad[2]
    test = pnt3.locV - pnt1.locV - ( (pnt2.locV-pnt1.locV) / (pnt2.locH - pnt1.locH) ) * (pnt3.locH - pnt1.locH)
    -- if the next point in the quad is on a different side, the point is outside the quad
    if test/abs(test) <> whichSide then return 0
  end repeat
  return TRUE
end 


on PointIsOnLine (pnt1, pnt2, pnt3)
  -- return true if pnt3 in on the line segment is defined as pnt1, pnt2
  --
  -- equation of a line connecting two points (x1,y1) and (x2,y2):
  -- 
  --               (y2 - y1)
  --    0 = y - y1 - --------- (x - x1)
  --                 (x2 - x1)
  
  return ( pnt3.locV - pnt1.locV - ( (pnt2.locV-pnt1.locV) / (pnt2.locH - pnt1.locH) ) * (pnt3.locH - pnt1.locH) ) = 0
end


-------------------------------------------
-- LINES & QUADS INTERSECTION
-------------------------------------------


on LineSegmentIntersectsQuad (p1, p2, aQuad)
  -- returns TRUE or FALSE if the specified line segment intersects with the specified Quad
  repeat with side = 1 to 4
    -- get the line segment
    p3 = aQuad[side]
    if side < 4 then p4 = aQuad[side+1]
    else p4 =aQuad[1]
    if LineSegmentsIntersect(p1,p2,p3,p4) then return 1
  end repeat
end

on GetPointsWhereInfLineIntersectsQuad (p1, p2, aQuad)
  -- returns a list of points where the specified line intersects with the specified Quad
  -- (assumes that the line is infinite)
  resultList = []
  repeat with side = 1 to 4
    -- get the line segment
    p3 = aQuad[side]
    if side < 4 then p4 = aQuad[side+1]
    else p4 =aQuad[1]
    res = GetPointofIntersection2(p1,p2,p3,p4)
    if res.ilk = #point then resultList.append( res )
  end repeat
  return resultList
end


on GetPointsWhereLineIntersectsQuad (p1, p2, aQuad)
  -- returns a list of points where the specified line segment intersects with the specified Quad
  resultList = []
  repeat with side = 1 to 4
    -- get the line segment
    p3 = aQuad[side]
    if side < 4 then p4 = aQuad[side+1]
    else p4 =aQuad[1]
    res = GetPointofIntersection(p1,p2,p3,p4)
    if res.ilk = #point then resultList.append( res )
  end repeat
  return resultList
end


on InfLineIntersectsQuad (p1, p2, aQuad)
  -- returns TRUE or FALSE if the specified line intersects with the specified Quad
  -- (assumes that the line is infinite)
  
  repeat with side = 1 to 4
    -- get the line segment
    p3 = aQuad[side]
    if side < 4 then p4 = aQuad[side+1]
    else p4 =aQuad[1]
    if InfLineIntersects(p1,p2,p3,p4) then return 1
  end repeat
end


on LineSegmentsIntersect (p1,p2,p3,p4)
  -- returns true of the line segment (p1,p2) intersections the second line segment (p3, p4)
  denominator = (p4.locV-p3.locV)*(p2.locH-p1.loch) - (p4.locH-p3.locH)*(p2.locV-p1.locV)
  if denominator = 0 then return 0 -- lines a parallel
  num1 = (p4.locH-p3.locH)*(p1.locV-p3.locV) - (p4.locV-p3.locV)*(p1.locH-p3.locH)
  num2 = (p2.locH-p1.locH)*(p1.locV-p3.locV) - (p2.locV-p1.locV)*(p1.locH-p3.locH)
  Ua = num1/float(denominator)
  Ub = num2/float(denominator)
  return (Ua >= 0 AND Ua < 1) AND  (Ub >= 0 AND Ub < 1)
end 

on GetPointofIntersection (p1,p2,p3,p4)
  --  returns point where line segment p1, p2 intersects line segment p3 p4
  denominator = (p4.locV-p3.locV)*(p2.locH-p1.loch) - (p4.locH-p3.locH)*(p2.locV-p1.locV)
  if denominator = 0 then return 0 -- lines are parallel
  num1 = (p4.locH-p3.locH)*(p1.locV-p3.locV) - (p4.locV-p3.locV)*(p1.locH-p3.locH)
  num2 = (p2.locH-p1.locH)*(p1.locV-p3.locV) - (p2.locV-p1.locV)*(p1.locH-p3.locH)
  Ua = num1/float(denominator)
  Ub = num2/float(denominator)
  if (Ua >= 0 AND Ua < 1) AND  (Ub >= 0 AND Ub < 1) then
    x = p1.locH + ua * (p2.locH - p1.locH) 
    y = p1.locV + ua * (p2.locV - p1.locV)
    return point(x,y)
  else return 0
end


on GetPointofIntersection2 (p1,p2,p3,p4)
  -- Returns point where an infinite line through p1 & p2 intersects line segment p3 p4
  -- or 0 if there is no intersection
  denominator = (p4.locV-p3.locV)*(p2.locH-p1.loch) - (p4.locH-p3.locH)*(p2.locV-p1.locV)
  if denominator = 0 then return 0 -- lines a parallel
  num1 = (p4.locH-p3.locH)*(p1.locV-p3.locV) - (p4.locV-p3.locV)*(p1.locH-p3.locH)
  num2 = (p2.locH-p1.locH)*(p1.locV-p3.locV) - (p2.locV-p1.locV)*(p1.locH-p3.locH)
  Ua = num1/float(denominator)
  Ub = num2/float(denominator)
  -- if (Ua >= 0 AND Ua < 1) AND  (Ub >= 0 AND Ub < 1) then
  if  (Ub >= 0 AND Ub < 1) then
    x = p1.locH + ua * (p2.locH - p1.locH) 
    y = p1.locV + ua * (p2.locV - p1.locV)
    return point(x,y)
  else return 0
end


on InfLineIntersects (p1,p2,p3,p4)
  -- returns TRUE if an infinite line through p1 and p2 intersects line segment p3 and p4
  denominator = (p4.locV-p3.locV)*(p2.locH-p1.loch) - (p4.locH-p3.locH)*(p2.locV-p1.locV)
  if denominator = 0 then return 0 -- lines are parallel
  num1 = (p4.locH-p3.locH)*(p1.locV-p3.locV) - (p4.locV-p3.locV)*(p1.locH-p3.locH)
  num2 = (p2.locH-p1.locH)*(p1.locV-p3.locV) - (p2.locV-p1.locV)*(p1.locH-p3.locH)
  Ua = num1/float(denominator)
  Ub = num2/float(denominator)
  return (Ub >= 0 AND Ub < 1)
end   

-------------------------------------------
-- CIRCLE INTERSECTIONS 
-------------------------------------------

on CircleIntersectsCircle (p1, r1, p2, r2)
  dx = p1.locH - p2.locH
  dy = p1.locV - p2.locV
  d2 = dx*dx + dy*dy
  d = sqrt( d2 )
  if ( d> r1 + r2 ) OR ( d<abs(r1-r2) ) then
    return []-- no solution
  else
    r12 = r1*r1
    r22 = r2*r2
    
    A = (r12 - r22 + d2) / (2*d)
    H = sqrt( r12 - a*a )
    x2 = p1.locH + a*(p2.locH - p1.locH)/d
    y2 = p1.locV + a*(p2.locV - p1.locV)/d
    
    ix1 = x2 + H*(p2.locV - p1.locV)/d
    iy1 = y2 - H*(p2.locH - p1.locH)/d
    ix2 = x2 - H*(p2.locV - p1.locV)/d
    iy2 = y2 + H*(p2.locH - p1.locH)/d
    
    return [point(ix1,iy1), point(ix2,iy2)]
  end if
end 

on CircleIntersectsInfLine (p1, p2, p3, r)
  -- returns a list of points where an infinite line along
  -- p1 and p2 (points) intersects with circle around p3 with
  -- radius r
  
  dx = float(p2.locH - p1.locH)
  dy = float(p2.locV - p1.locV)
  
  A = dx * dx + dy * dy
  B = 2 * (dx * (p1.locH - p3.locH) + dy * (p1.locV - p3.locV))
  C = (p1.locH - p3.locH) * (p1.locH - p3.locH) + (p1.locV - p3.locV) * (p1.locV - p3.locV) -  r * r
  
  det = B * B - 4 * A * C
  
  If (A <= 0) or (det < 0) then
    -- No real solutions.
    return []
  else 
    If det = 0 Then
      -- One solution.
      t = -B / (2 * A)
      ix1 = p1.locH + t * dx
      iy1 = p1.locV + t * dy
      return [point(ix1,iy1)]
    else
      -- Two solutions.
      t = (-B + Sqrt(det)) / (2 * A)
      ix1 = p1.locH + t * dx
      iy1 = p1.locV + t * dy
      t = (-B - Sqrt(det)) / (2 * A)
      ix2 = p1.locH + t * dx
      iy2 = p1.locV + t * dy
      return [point(ix1,iy1), point(ix2,iy2)]
    end If 
  end If 
end

on CircleIntersectsLineSegment (p1, p2, p3, r)
  -- returns a list of points where the line defined 
  -- by p1 and p2 intersect a circle around p3 with radius r
  
  dx = float(p2.locH - p1.locH)
  dy = float(p2.locV - p1.locV)
  
  A = dx * dx + dy * dy
  B = 2 * (dx * (p1.locH - p3.locH) + dy * (p1.locV - p3.locV))
  C = (p1.locH - p3.locH) * (p1.locH - p3.locH) + (p1.locV - p3.locV) * (p1.locV - p3.locV) -  r * r
  
  det = B * B - 4 * A * C
  
  rList = []
  
  If (A <= 0) or (det < 0) then
    -- no real solutions.
  else 
    -- one or two possible solutions
    If det = 0 Then
      -- The line meets the circle at one point (tangent  line)
      t = -B / (2 * A)
      if (t >= 0) AND (t<=1) then
        ix1 = p1.locH + t * dx
        iy1 = p1.locV + t * dy
        rList.add(point(ix1,iy1))
      end if
    else
      -- The line meets the circle at one point (secant line).
      t = (-B + Sqrt(det)) / (2 * A)
      if (t >= 0) AND (t<=1) then
        -- line segment intersects
        ix1 = p1.locH + t * dx
        iy1 = p1.locV + t * dy
        rList.add(point(ix1,iy1))
      end if
      t = (-B - Sqrt(det)) / (2 * A)
      if (t >= 0) AND (t<=1) then
        -- line segment intersects
        ix2 = p1.locH + t * dx
        iy2 = p1.locV + t * dy
        rList.add(point(ix2,iy2))
      end if
    end If 
  end If 
  return rList
end

on CircleIntersectsQuad (aQuad, p3, r)
  -- returns a list of points where a quad 
  -- intersect a circle around p3 with radius r
  
  resultList = []
  repeat with side = 1 to 4
    -- get the line segment
    p1 = aQuad[side]
    if side < 4 then p2 = aQuad[side+1]
    else p2 =aQuad[1]
    res = CircleIntersectsLineSegment(p1,p2,p3,r)
    repeat with ahit in res
      resultList.append(aHit)
    end repeat
  end repeat
  return resultList
  
end