# convexHull.py
# implements the Graham Scan

import random, math
import matplotlib.pyplot as plt

from point import Point
from segment import Segment
from vector import Vector
from GeomTools import *


NUM_PTS = 50


def convexHull(pts):
  # Find a point with the lowest y value, 
  anchorPt = pts[0]
  for _, pt in enumerate(pts):
    if pt.y < anchorPt.y:
      anchorPt = pt
    elif pt.y == anchorPt.y and pt.x > anchorPt.x:
      anchorPt = pt
  # print("Anchor:", anchorPt)
  
  # Sort all the points based on the angle they make with the anchor pt. 
  ptAngles = []
  for pt in pts:
    ptAngles.append([pt, anchorPt.polarAngle(pt)])
  ptAngles.sort( key=lambda x:x[1])
  sortedPts =  [ pt for [pt,_] in ptAngles]
  
  hull = [anchorPt, sortedPts[0]]
  # test turning if points
  for pt in sortedPts[1:]:
    while Vector.ccw(hull[-2], hull[-1], pt) <= 0:
      del hull[-1] # removal
    hull.append(pt)
  
  return hull



def isInside(poly, p):
  n = len(poly)
  if n < 3:
    return False
  for i in range(n):
    if Vector.ccw(poly[i], poly[(i+1)%n], p) == -1:  # on right
      return False
  # p always on left or collinear
  return True



def isConvex(pts):
  # https://www.geeksforgeeks.org/check-if-given-polygon-is-a-convex-polygon-or-not/
    
  n = len(pts)
  prev = 0
  curr = 0
  for i in range(n):
    # examine three adjacent edges of the polygon
    curr = Vector.ccw(pts[i], pts[(i+1)%n], pts[(i+2)%n] )
    if curr != 0:
      # orientation of adjacent edges must be the same
      if (curr * prev < 0):
        return False
      else:
        prev = curr
  return True




# -------------------------------------------------

if __name__ == "__main__":

  graphing(size=110)

  pts = [ Point(random.randint(1,100), 
                random.randint(1,100)) 
                       for _ in range(NUM_PTS) ]
  # plot the points
  for pt in pts:
     pt.draw()
  
  hull = convexHull(pts)
  print("Convex hull:")
  print(*hull)

  p = Point(random.randint(1,100), random.randint(1,100))
  print("p:", p)
  p.draw(color="red")
  print("is p inside hull? ", isInside(hull, p))

  drawPoly(hull)

  '''
  graphing()
  poly = [Point(3,0), Point(4,2), Point(7,4),
          Point(3,4), Point(1,2) ]  # concave
  p = Point(2, 7);
  print("poly:", *poly)
  print("p:", p)
  print("is p inside? ", isInside(poly, p))
  print("is poly convex?", isConvex(poly))
  drawPoly(poly)
  p.draw(label="p")
  '''

  plt.show()