Hull.py

#  File: Hull.py

#  Description:

#  Student Name: Sashi Ayyalasomayajula

#  Student UT EID: sa55465

#  Partner Name:

#  Partner UT EID:

#  Course Name: CS 313E

#  Unique Number: 

#  Date Created:

#  Date Last Modified:

import sys
import math

class Point (object):
  # constructor
  def __init__(self, x = 0, y = 0):
     self.x = x
     self.y = y

  # get the distance to another Point object
  def dist (self, other):
     return math.hypot (self.x - other.x, self.y - other.y)

  # string representation of a Point
  def __str__ (self):
     return '(' + str(self.x) + ', ' + str(self.y) + ')'

  # equality tests of two Points
  def __eq__ (self, other):
     tol = 1.0e-8
     return ((abs(self.x - other.x) < tol) and (abs(self.y - other.y) < tol))

  def __ne__ (self, other):
     tol = 1.0e-8
     return ((abs(self.x - other.x) >= tol) or (abs(self.y - other.y) >= tol))

  def __lt__ (self, other):
     tol = 1.0e-8
     if (abs(self.x - other.x) < tol):
         if (abs(self.y - other.y) < tol):
             return False
         else:
             return (self.y < other.y)

     return (self.x < other.x)

  def __le__ (self, other):
     tol = 1.0e-8
     if (abs(self.x - other.x) < tol):
         if (abs(self.y - other.y) < tol):
             return True
         else:
             return (self.y <= other.y)
     return (self.x <= other.x)

  def __gt__ (self, other):
     tol = 1.0e-8
     if (abs(self.x - other.x) < tol):
         if (abs(self.y - other.y) < tol):
             return False
         else:
             return (self.y > other.y)
     return (self.x > other.x)

  def __ge__ (self, other):
     tol = 1.0e-8
     if (abs(self.x - other.x) < tol):
         if (abs(self.y - other.y) < tol):
             return True
         else:
             return (self.y >= other.y)
     return (self.x >= other.x)

# Input: p, q, r are Point objects
# Output: compute the determinant and return the value
def det (p, q, r):

    det = (q.x * r.y) - (r.x * q.y) + (r.x * p.y) - (p.x * r.y) + (p.x * q.y) - (q.x * p.y)  
    return det

# Input: sorted_points is a sorted list of Point objects
# Output: computes the convex hull of a sorted list of Point objects
#         convex hull is a list of Point objects starting at the
#         extreme left point and going clockwise in order
#         returns the convex hull
def convex_hull (sorted_points):

    upper_hull = []
  
    #append first two points of sorted list to upper hull
    upper_hull.append(sorted_points[0])
    upper_hull.append(sorted_points[1])

    #adds rest of the points to upper_hull, but extracts specific points that are right turns relative to the previous point added
    for i in range(2, len(sorted_points)):
        upper_hull.append(sorted_points[i])

        while(len(upper_hull) >= 3) and (det(upper_hull[-3], upper_hull[-2], upper_hull[-1]) >= 0): #extracts point if is making a right turn
            upper_hull.pop(-2)

    lower_hull = [] 

    #append last two points of sorted list to lower hull
    lower_hull.append(sorted_points[-1]) 
    lower_hull.append(sorted_points[-2])


    # similar functioning loop to upper hull but in reverse order realtive to sorted points list
    for j in range(len(sorted_points)-3, -1, - 1):
        lower_hull.append(sorted_points[j])

        while(len(lower_hull) >= 3) and det(lower_hull[-3], lower_hull[-2], lower_hull[-1]) >= 0:
            lower_hull.pop(-2)

    Cvex_hull = [] #empty list to store final points that make up the polygon

    # gets rid of two duplicate points at the beginnign and end of lower hull
    lower_hull.pop(len(lower_hull)-1) 
    lower_hull.pop(0)

    Cvex_hull = upper_hull # appends upper hull to conver hull
    for point in lower_hull:
        Cvex_hull.append(point) # appends lower hull to conver hull

    return Cvex_hull

# Input: convex_poly is  a list of Point objects that define the
#        vertices of a convex polygon in order
# Output: computes and returns the area of a convex polygon
def area_poly(convex_poly):
    d = 0
    for i in range(len(convex_poly)-1): # goes through points in polygon
        #sets a and b as two consecutive points
        a = convex_poly[i]
        b = convex_poly[i+1] 

        d += (a.x*b.y)
        d -= (a.y*b.x)

    # adds det of two points to d
    d += convex_poly[-1].x*convex_poly[0].y
    d -= convex_poly[-1].y*convex_poly[0].x

    # computes area
    A = 0.5 * math.fabs(d) 
    return A




# Input: no input
# Output: a string denoting all test cases have passed
def test_cases():
  # write your own test cases



  return "all test cases passed"

def main():
    # create an empty list of Point objects
    points_list = []

    # read number of points
    line = sys.stdin.readline()
    line = line.strip()
    num_points = int (line)

    # read data from standard input
    for i in range (num_points):
        line = sys.stdin.readline()
        line = line.strip()
        line = line.split()
        x = int (line[0])
        y = int (line[1])
        points_list.append (Point (x, y))

    # sort the list according to x-coordinates
    sorted_points = sorted(points_list)

    # get the convex hull
    Cvex_hull = []
    Cvex_hull = convex_hull(sorted_points)

    # run your test cases

    # print your results to standard output

    # print the convex hull
    print('Convex Hull')
    for point in Cvex_hull:
        print(tuple([point.x, point.y]))
    print()

    # get the area of the convex hull
    ACvex_hull = area_poly(Cvex_hull)

    # print the area of the convex hull
    print("Area of Convex Hull = " + str(ACvex_hull))

if __name__ == "__main__":
  main()