# closestDC.py

import random, math, sys
import matplotlib.pyplot as plt

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

# create a random set of pts
NUM_PTS = 50


def closestPair(pts, n):
  if n <= 3:
    return pairsSearch(pts, n)

  mid = n//2
  midPoint = pts[mid]
  # divide and conquer
  dl, mpl = closestPair(pts, mid)  # left
  dr, mpr = closestPair(pts[mid:], n-mid) # right

  # use the minimum distance (and its pair)
  if dl < dr:
    d = dl
    mp = mpl
  else:
    d = dr
    mp = mpr

  strip = []
  # build a 2d-wide strip of points
  for i in range(n):
    if abs(pts[i].x - midPoint.x) < d:
      strip.append(pts[i])
  return checkStrip(strip, d, mp)


def checkStrip(strip, minDist, minPair):
  size = len(strip)

  # sort so can move upwards through the strip
  strip = sorted(strip, key=lambda pt: pt.y)

  for i in range(size):
    for j in range(i+1, size):
      # only examine minDist upwards
      if (strip[j].y - strip[i].y) >= minDist:
          break
      d = strip[i].distTo(strip[j])
      if d < minDist:
        minDist = d
        minPair = (strip[i], strip[j])

  return minDist, minPair



def pairsSearch(pts, n):
  minDist = sys.maxsize
  minPair = (None, None)
  for i in range(n):
    for j in range(i+1, n):
      d = pts[i].distTo(pts[j])
      if d < minDist:
        minDist = d
        minPair = (pts[i], pts[j])

  return minDist, minPair


# ------------ main -----------------

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()
  
  pts = sorted(pts, key=lambda point: point.x)
    # sort so can find median x pt
  d, (pt1, pt2) = closestPair(pts, len(pts))
  
  pt1.draw(color="red")
  pt2.draw(color="red")
  
  print("Smallest distance:", d)
  print("Points:", pt1, pt2)
  plt.show()