# closestSweep.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):
  # https://www.geeksforgeeks.org/closest-pair-of-points-using-sweep-line-algorithm/
  n = len(pts)

  # Sort according to x-coordinates
  pts.sort(key=lambda pt: pt.x)

  # Minimum distance b/w pts seen so far
  d = sys.maxsize
  minPair = (None, None)

  # Keeping the pts in increasing order
  ptsSet = set()
  ptsSet.add(pts[0])
  for i in range(1, n):    # x between [x-d, x] and y between [y-d, y+d]
    left = set([p for p in ptsSet 
             if (p.x >= (pts[i].x-d)) and (p.y >= (pts[i].y-d)) ])
    right = set([p for p in ptsSet 
              if (p.x <= (pts[i].x)) and (p.y <= (pts[i].y+d)) ])
    intersectPts = left & right
    if len(intersectPts) == 0:
      continue

    for p in intersectPts:
      dist2 = pts[i].distSq(p)
      # Updating the minimum distance dis
      if d > dist2:
        d = dist2
        minPair = (pts[i], p)

    ptsSet.add(pts[i])

  return d, 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()
  
  d, (pt1, pt2) = closestPair(pts)
  
  pt1.draw(color="red")
  pt2.draw(color="red")
  
  print("Smallest distance:", d)
  print("Points:", pt1, pt2)
  plt.show()