extendedgrahamscan.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00000-684fe23f-9bcc-4684-bcde-ed6aef241641",
    "deepnote_cell_type": "markdown"
   },
   "source": [
    "# Extended Graham scan algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00001-47ffd83f-cf5c-4125-95ae-c12e4573bc62",
    "deepnote_cell_type": "markdown"
   },
   "source": [
    "Use the cell below for all python code needed to realise the extended Graham scan algorithm (including any auxiliary data structures and functions you might need). The `extendedgrahamscan()` function itself should take as input parameter a list of 2D points (`inputSet`), and return the subset of such points that lie on the convex hull (`outputSet`).\n",
    "\n",
    "These are the auxiliary functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00002-6a4dc5b2-7ba4-4627-995c-cf4e8ae9ccd8",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": false,
    "execution_millis": 4,
    "execution_start": 1615216799294,
    "source_hash": "3ea69907",
    "tags": []
   },
   "outputs": [],
   "source": [
    "from math import atan2\n",
    "\n",
    "def calc_polar_angle(p1: tuple ,p2: tuple) -> float:\n",
    "    \"\"\"Function that gets the polar angle from two points by using arctan on the y-distance and x-distance\n",
    "    \n",
    "    Args:\n",
    "        p1 (tuple) : a di-tuple (x,y) representing the first coordinate,\n",
    "        p2 (tuple) : a di-tuple (x,y) representing the second coordinate.\n",
    "\n",
    "    Returns:\n",
    "        (float) : the polar angle between p1 and p2 in radians.\n",
    "    \"\"\"\n",
    "    return atan2(p2[1] - p1[1], p2[0] - p1[0])\n",
    "\n",
    "def distance(p1: tuple, p2: tuple) -> float:\n",
    "    \"\"\"Function that calculates the distance between two given points    \n",
    "    \n",
    "    Args:\n",
    "        p1 (tuple) : a di-tuple (x,y) representing the first coordinate,\n",
    "        p2 (tuple) : a di-tuple (x,y) representing the second coordinate.\n",
    "\n",
    "    Returns:\n",
    "        (float) : the distance between p1 and p2.\n",
    "    \"\"\"\n",
    "\n",
    "    return (p2[1] - p1[1]) **2 + (p2[0] - p1[0]) **2\n",
    "\n",
    "def determinant(p1: tuple, p2: tuple, p3: tuple) -> float:\n",
    "    \"\"\"Function that gets the determinant for p1, p2 and p3, to determine whether it is a clockwise or\n",
    "       anticlockwise turn. \n",
    "\n",
    "        Args:\n",
    "        p1 (tuple) : a di-tuple (x,y) representing the first coordinate,\n",
    "        p2 (tuple) : a di-tuple (x,y) representing the second coordinate,\n",
    "        p3 (tuple) : a di-tuple (x,y) representing the third coordinate,\n",
    "\n",
    "    Returns:\n",
    "        (float) : the determinant between p1, p2 and p3.\n",
    "\n",
    "    Note:\n",
    "        det > 0 -> clockwise turn\n",
    "        det < 0 -> anticlockwise turn\n",
    "        det == 0 -> points are collinear\n",
    "    \"\"\"\n",
    "\n",
    "    return (p2[0]-p1[0]) * (p3[1]-p1[1])  - (p2[1]-p1[1]) * (p3[0]-p1[0])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00003-982ac969-e30b-4243-9cda-0fa818d0ca78",
    "deepnote_cell_type": "markdown",
    "tags": []
   },
   "source": [
    "The heuristic that is used filter as many points that are within the convex hull, to reduce the size is by using the shape class below:\n",
    "- We find four extreme points (top-most,bottom-most,right-most and left-most) from the input set to form a quadrilateral. \n",
    "- The quadrilateral will adjust itself to choose four more extreme points, topleft, topright, bottomleft, and bottomright points, transforming it into an octagon. This is to filter out points that are definitely within the convex hull, and if a more extreme point is found, the respective extreme point is updated with it.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00003-e24db61b-1888-4565-a102-b0e6d6c902a1",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": false,
    "execution_millis": 4,
    "execution_start": 1615216799312,
    "source_hash": "4f211b3",
    "tags": []
   },
   "outputs": [],
   "source": [
    "class Shape:\n",
    "    \"\"\"Instance that is used to setup a preliminary convex hull to filter out non essential points to prevent excessive \n",
    "    backtracking by the grahamscan.\"\"\"\n",
    "\n",
    "    def __init__(self, inputSet):\n",
    "        self.inputSet = inputSet\n",
    "        self.load_extreme_points() #gets top, left, right, and bottom most points.\n",
    "        self.bottomleft, self.bottomright, self.topleft, self.topright = None, None, None, None # will get replaced when it iterates through the list.\n",
    "\n",
    "    def load_extreme_points(self):\n",
    "        \"\"\"Method that gets the most bottom, left, right, and top points, and places them into their respect attributes\"\"\"\n",
    "        self.bottom, self.left, self.right, self.top = self.inputSet[0], self.inputSet[0], self.inputSet[0], self.inputSet[0]\n",
    "        for point in self.inputSet:\n",
    "            if point[1] < self.bottom[1] or (point[1] == self.bottom[1] and point[0] < self.bottom[0]):\n",
    "                self.bottom = point\n",
    "            \n",
    "            if point[1] > self.top[1] or (point[1] == self.top[1] and point[0] < self.top[0]):\n",
    "                self.top = point\n",
    "            \n",
    "            if point[0] < self.left[0] or (point[0] == self.left[0] and point[1] < self.left[1]):\n",
    "                self.left = point\n",
    "            \n",
    "            if point[0] > self.right[0] or (point[0] == self.right[0] and point[1] < self.right[1]):\n",
    "                self.right = point\n",
    "\n",
    "\n",
    "    def clockwise_turn(self, p1: tuple, p2: tuple, corner: tuple, target: tuple) -> (bool, tuple):\n",
    "        \"\"\"Method that determines whether the target coordinate creates a clockwise turn.\n",
    "        \n",
    "        Args:\n",
    "            p1 (tuple): a di-tuple representing a coordinate of (top, bottom, left, right)\n",
    "            p2 (tuple):  a di-tuple representing a coordinate of (top, bottom, left, right)\n",
    "            corner (tuple):  a di-tuple representing a coordinate that connect p1 and p2 (topleft/topright/botttomleft/bottomright)\n",
    "            target (tuple): a di-tuple representing the coordinate to check whether it creates an clockwise turn, with the others args.\n",
    "        \n",
    "        Returns:\n",
    "            (bool) Returns True if a clockwise turn is made with any of the lines.\n",
    "            (tuple) if target creates an anticlockwise turn with all lines, then it should be returned to update the extreme point.\n",
    "        \"\"\"\n",
    "        if determinant(p1, p2, target) <= 0: # if it is on the anticlockwise / left hand side or colinear \n",
    "            if corner is None or (determinant(p1, corner, target) <= 0 or determinant(corner, p2, target) <= 0): \n",
    "                # if it is on the anticlockwise / land hand side of either, then it is outside the octagon.\n",
    "                # if its None, then set this point as the corner as its a suitable candidate (being anticlockwise of p1 -> p2).\n",
    "                return False, target\n",
    "        return True, corner\n",
    "    \n",
    "    def is_inside(self, point: tuple) -> bool:\n",
    "        \"\"\"Method that determines whether a point lies inside the shape, and updates a corner attribute if it doesn't.\n",
    "\n",
    "        Returns:\n",
    "            (bool): Returns True if the point does lie inside the shape.\n",
    "        \"\"\"\n",
    "        inside_topleft, self.topleft = self.clockwise_turn(self.top, self.left, self.topleft, point)\n",
    "        inside_topright, self.topright = self.clockwise_turn(self.right, self.top, self.topright, point)\n",
    "        inside_bottomright, self.bottomright = self.clockwise_turn(self.bottom, self.right, self.bottomright, point)\n",
    "        inside_bottomleft, self.bottomleft = self.clockwise_turn(self.left, self.bottom, self.bottomleft, point)\n",
    "\n",
    "        return inside_topleft and inside_topright and inside_bottomright and inside_bottomleft\n",
    "\n",
    "    def get_outside_points(self) -> list:\n",
    "        \"\"\"Method that generates a list of points that are outside the shape.\n",
    "\n",
    "        Returns:\n",
    "            (list): List of di-tuples that represent the x,y coordinates of points that lay outside the shape.\n",
    "        \"\"\"\n",
    "        outside_points = []\n",
    "        for point in self.inputSet:\n",
    "            if not self.is_inside(point):\n",
    "                outside_points.append(point)\n",
    "        return outside_points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00005-1b031dd1-29d1-4c85-a762-88e84eca1f10",
    "deepnote_cell_type": "markdown",
    "tags": []
   },
   "source": [
    "Regular Graham Scan code, which is exactly the same as the one from grahamscan.ipnyb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00002-44106f00-a53f-4f98-a6ae-1c5eb38c0ef4",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": false,
    "execution_millis": 0,
    "execution_start": 1615216799331,
    "source_hash": "83541448"
   },
   "outputs": [],
   "source": [
    "def merge(angles: dict, points: list, aux: list, ref: tuple, low: int, mid: int, high: int):\n",
    "    \"\"\"The merge step of the merge sort.\n",
    "\n",
    "    Args:\n",
    "        angles (dict): dictionary that has the polar angle of each point in points,\n",
    "        points (list): a list of di-tuples representing (x,y) coordinates,\n",
    "        aux (list): the auxiliary list,\n",
    "        ref (tuple): the reference tuple that is used to calculate distance in the case where there are,\n",
    "                     multiple points with the same polar angle,\n",
    "        low (int): the index at the start of the partition,\n",
    "        mid (int): the index at the middle of the partition,\n",
    "        high (int): the index at the end of the partition.\n",
    "    \"\"\"\n",
    "    # copy over into the auxiliary list.\n",
    "    for i in range(low, high+1):\n",
    "        aux[i] = points[i]\n",
    "\n",
    "    first_partition_counter = low\n",
    "    second_partition_counter = mid+1\n",
    "\n",
    "    for counter in range(low, high+1):\n",
    "        if first_partition_counter > mid: # if larger then there are no more elements in the first_partition\n",
    "            points[counter] = aux[second_partition_counter]\n",
    "            second_partition_counter = second_partition_counter + 1\n",
    "            \n",
    "        elif second_partition_counter > high: # if smaller then there are no more elements in the second_partition\n",
    "            points[counter] = aux[first_partition_counter]\n",
    "            first_partition_counter = first_partition_counter + 1\n",
    "\n",
    "        elif angles[aux[second_partition_counter]] < angles[aux[first_partition_counter]]: # compare the polar angles\n",
    "            points[counter] = aux[second_partition_counter]\n",
    "            second_partition_counter = second_partition_counter + 1\n",
    "        \n",
    "        elif angles[aux[second_partition_counter]] == angles[aux[first_partition_counter]]: # if angles are equal compare distance.\n",
    "            if distance(aux[second_partition_counter], ref) < distance(aux[first_partition_counter], ref):\n",
    "                points[counter] = aux[second_partition_counter]\n",
    "                second_partition_counter = second_partition_counter + 1\n",
    "\n",
    "        else:\n",
    "            points[counter] = aux[first_partition_counter]\n",
    "            first_partition_counter = first_partition_counter + 1\n",
    "\n",
    "def mergesort(angles: dict, points: list, aux: list, ref: tuple, low: int, high: int):\n",
    "    \"\"\"Recursive merge sort that sorts points based on their polar angle with the reference point.\n",
    "\n",
    "    Args:\n",
    "        angles (dict): dictionary that has the polar angle of each point in points,\n",
    "        points (list): a list of di-tuples representing (x,y) coordinates,\n",
    "        aux (list): the auxiliary list,\n",
    "        ref (tuple): the reference tuple that is used to calculate distance in the case where there are,\n",
    "                     multiple points with the same polar angle,\n",
    "        low (int): the index at the start of the partition,\n",
    "        high (int): the index at the end of the partition.\n",
    "    \"\"\"\n",
    "    if (high <= low): # base case\n",
    "        return\n",
    "    \n",
    "    mid = low + ((high - low)//2)\n",
    "\n",
    "    # splitting the list.\n",
    "    mergesort(angles, points, aux, ref, low, mid)\n",
    "    mergesort(angles, points, aux, ref, mid+1, high)\n",
    "\n",
    "    if angles[points[mid]] < angles[points[mid+1]]: # if already in the correct order then skip merge\n",
    "        return\n",
    "    merge(angles, points, aux, ref, low, mid, high) # merge the two partitions.\n",
    "\n",
    "\n",
    "def extendedgrahamscan(inputSet: list) -> list:\n",
    "    \"\"\"Function that scans through the list and returns a list of points that are on the convex hull\n",
    "\n",
    "    Args:\n",
    "        inputSet (list): a list of di-tuples representing (x,y) coordinates\n",
    "\n",
    "    Returns:\n",
    "        (list): a list of di-tuples representing (x,y) coordinates on the convex hull.\n",
    "    \"\"\"\n",
    "    \n",
    "    shape = Shape(inputSet)\n",
    "\n",
    "    # using a dictionary to avoid multiple recalculations.\n",
    "    angles = dict([(tuple(point), calc_polar_angle(point, shape.bottom)) for point in shape.get_outside_points()])\n",
    "\n",
    "    inputSet = list(angles.keys()) # gets the points filtered points\n",
    "    mergesort(angles,inputSet, [None]*len(inputSet), shape.bottom, 0, len(inputSet)-1) # sort based on angle made with reference point\n",
    "    stack = []\n",
    "    for point in inputSet:\n",
    "        while len(stack) > 1 and determinant(stack[-2], stack[-1],point) < 0:\n",
    "            #removes points on the stack that make an anticlockwise turn\n",
    "            del stack[-1]\n",
    "        stack.append(point) #adds points that could potentially be on the convex hull.\n",
    "    \n",
    "\n",
    "    return stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00003-50a42f43-c1a4-4f8a-930f-c5d397b807fe",
    "deepnote_cell_type": "markdown"
   },
   "source": [
    "Use the cell below for all python code needed to generate test data points (both random and those representing worst-case scenario)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00004-f8018ffa-a666-40ef-95a4-497356cbd362",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": false,
    "execution_millis": 1,
    "execution_start": 1615216799390,
    "source_hash": "f61ced8d"
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "#code for random data generation\n",
    "def generatePoint() -> tuple:\n",
    "    \"\"\"Function that generates a random valid point\"\"\"\n",
    "    return (random.randint(0, 32767), random.randint(0, 32767))\n",
    "\n",
    "def generatePoints(limit: int) -> list:\n",
    "    \"\"\"Function that generates a random list of point\"\"\"\n",
    "    return [generatePoint() for point in range(limit)]\n",
    "\n",
    "#code for worst case data generation\n",
    "\n",
    "def worstCase(limit: int) -> list:\n",
    "    \"\"\"Function that generates the worst case set of points for the Extended Graham Scan,\n",
    "    which occurs when the order of the order of points is increasingly more extreme, \n",
    "    and thus nullifying the ability to filter out any points.\n",
    "\n",
    "    Args:\n",
    "        limit (int): the number of points required.\n",
    "    \n",
    "    Returns:\n",
    "        (list): a list of di-tuples representing points, that trigger the worst case for heuristic.\n",
    "    \"\"\"\n",
    "    inputSet = [(16383, 32767), (0, 16383), (32767, 16383), (0,0)]\n",
    "\n",
    "    shape = Shape(inputSet)\n",
    "    for _ in range(limit-4):\n",
    "        point = generatePoint()\n",
    "        while shape.is_inside(point): # keep generating points until it is outside the shape\n",
    "            point = generatePoint()\n",
    "        inputSet.append(point)\n",
    "    shape = Shape(inputSet)\n",
    "    return inputSet\n",
    "    \n",
    "def join(points: list, left: list, right: list, low: int, mid: int, high: int):\n",
    "    \"\"\"Functions that merges two partitions together for the worst_merge_sort procedure,\n",
    "    in a way that triggers the worst case for merge sort.\n",
    "\n",
    "    Args:\n",
    "        points (list): the original list of points, which the left and right lists are to merge into,\n",
    "        left (list): the list of points in the left partition,\n",
    "        right (list): the list of points in the right partition,\n",
    "        low (int): the index at which the left partition begins at.\n",
    "        mid (int): the index at which the left partition ends, and the right one begins.\n",
    "        high (int): the index at which the right partition ends.\n",
    "    \"\"\"\n",
    "    for i in range(mid-low+1):\n",
    "        points[i] = left[i]\n",
    "    \n",
    "    for j in range(high-mid):\n",
    "        points[i + j + 1] = right[j]\n",
    "\n",
    "\n",
    "def worst_merge_sort(points: list, low: int, high: int):\n",
    "    \"\"\"Recursive procedure that changes the order of the sorted list of points to trigger the \n",
    "    worst case for merge sort, which is a list that triggers the maximum number of comparisons.\n",
    "\n",
    "    Args:\n",
    "        points (list): a sorted list,\n",
    "        low (int): the start index of the partition,\n",
    "        high (int): the end index of the partition.\n",
    "    \"\"\"\n",
    "    if low < high:\n",
    "        mid = low + ((high - low) // 2)\n",
    "\n",
    "        left = [points[i*2] for i in range(mid-low+1)] # takes even indices\n",
    "        right = [points[i * 2 + 1] for i in range(high-mid)] # takes odd indices\n",
    "\n",
    "        # partition again.\n",
    "        worst_merge_sort(left, low, mid)\n",
    "        worst_merge_sort(right, mid+1, high)\n",
    "\n",
    "        join(points, left, right, low, mid , high)\n",
    "\n",
    "def regular_worst_case(limit: int) -> list:\n",
    "    \"\"\"Function that generates the worst case scenario for the graham scan\n",
    "\n",
    "    Args:\n",
    "        limit (int): the number of points that are to be in the list.\n",
    "    \n",
    "    Returns: \n",
    "        (list) the list of points that is structured to trigger the worst case for graham.\n",
    "    \"\"\"\n",
    "    inputSet = generatePoints(limit) # generate a random set of points.\n",
    "    ref = Shape(inputSet).bottom # get the reference point.\n",
    "\n",
    "    # create angles dictionary.\n",
    "    angles = dict([(point, calc_polar_angle(point, ref)) for point in inputSet])\n",
    "\n",
    "    mergesort(angles, inputSet, inputSet.copy(), ref, 0, len(inputSet)-1) # sort inputSet\n",
    "    worst_merge_sort(inputSet, 0, len(inputSet)-1) # transform it into worst case\n",
    "\n",
    "    return inputSet # return worst case"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00005-8d9ecdd9-fffd-4556-8d82-11d2558413a4",
    "deepnote_cell_type": "markdown"
   },
   "source": [
    "Use the cell below for all python code needed to test the `extendedgrahamscan()` function on the data generated above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00006-9549926a-a66f-4c5b-9ef6-1627abfd645d",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": false,
    "execution_millis": 2745,
    "execution_start": 1615216799391,
    "source_hash": "4d14ebe"
   },
   "outputs": [],
   "source": [
    "import timeit\n",
    "\n",
    "#test code\n",
    "\n",
    "def get_avg_unfiltered_points(limit: int, data_generator) -> int:\n",
    "    \"\"\"Function that gets the number of points the shape is unable to filter out\n",
    "\n",
    "    Args:\n",
    "        limit (int): the number of points in the original list.\n",
    "        data_generator: a function that when given the limit, will generate a list with a size equal to the limit.\n",
    "    \n",
    "    Returns:\n",
    "        (int): the average number of points that the shape was unable to filter out given the limit and the data generator.\n",
    "    \"\"\"\n",
    "    return sum([len(Shape(data_generator(limit)).get_outside_points()) for _ in range(50)]) / 50\n",
    "\n",
    "def run_tests(limits: list, data_generator, title=\"\", tests=100):\n",
    "    \"\"\"Procedure that tests the code, and presents the findings in a prettified manner.\n",
    "\n",
    "    Args:\n",
    "        limits (list): a list of limits to test the grahamscan on,\n",
    "        data_generator (function): a function, that when given a limit from limits, generates a list of points,\n",
    "        title (str): title is used as a label,\n",
    "        tests (int): number of times to run a limit. Defaults to 100.\n",
    "    \"\"\"\n",
    "    \n",
    "    print(\"=\"*10, f\" STARTING: {title} cases \", \"=\"*10, \"\\n\")\n",
    "    for limit in limits:\n",
    "        header =  f'{title} Case @ {limit}: ' \n",
    "        whitespace_required = (len(header)-2)*' '\n",
    "\n",
    "        # take avg. data generation time to subtract from total time, to get time taken for grahamscan.\n",
    "        data_generation_time = timeit.timeit('data_generator(limit)', number = tests, globals={'data_generator':data_generator, 'limit':limit})\n",
    "\n",
    "        # get the avg. time taken to grahamscan a random list (a new list is generated each iteration), includes time for data generation.\n",
    "        total_time = timeit.timeit('extendedgrahamscan(data_generator(limit))', number = tests,  \n",
    "        globals={'extendedgrahamscan':extendedgrahamscan,'data_generator':data_generator, 'limit':limit})\n",
    "\n",
    "        # subtract total_time by the time it takes to generate data, and then take avg.\n",
    "        extendedgrahamscan_time = (total_time - data_generation_time) / tests\n",
    "\n",
    "        print(header,  f\"{extendedgrahamscan_time} seconds\")\n",
    "\n",
    "        unfiltered_points = get_avg_unfiltered_points(limit, data_generator)\n",
    "        filtraton_rate = round(((limit - unfiltered_points) * 100) / limit, 2)\n",
    "        print(f\"{whitespace_required}| reduced size by approx. {filtraton_rate}%\")\n",
    "    print()\n",
    "    print(\"=\"*10, f\" FINISHED: {title} cases \", \"=\"*10)\n",
    "\n",
    "limits = (100, 500, 1000, 5000, 10000, 15000, 20000)\n",
    "run_tests(limits, generatePoints, \"Normal\")\n",
    "run_tests(limits, worstCase, \"Worst\")\n",
    "run_tests(limits, regular_worst_case, \"Regular Graham Worst Case\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "cell_id": "00007-0595bb7f-edcc-4dab-8076-2571958a71c8",
    "deepnote_cell_type": "markdown"
   },
   "source": [
    "*Optional*: Feel free to use the code below on small datasets (e.g., N = 10) to visually inspect whether the algorithm has been implemented correctly. The fragment below assumes both `inputSet` and `outputSet` to be lists of 2D points, with each point being a list of 2 elements (e.g., `[[x1,y1], [x2,y2], ..., [x_k,y_k]]`)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00008-79e0e909-0e62-4475-b042-2918161056c6",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": true,
    "execution_millis": 1031,
    "source_hash": "27c504ad"
   },
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# inputSet and outputSet should have been defined above. \n",
    "# uncomment the next two lines only if you wish to test the plotting code before coding your algorithm\n",
    "\n",
    "#inputSet = [[1,1], [2,2] , [3, 3], [4,4], [1,4], [3,1], [1, 5], [2, 4], [3, 5]]\n",
    "#outputSet = [[1,1], [3,1] , [4, 4], [3,5], [1,5]]\n",
    "\n",
    "\n",
    "inputSet = generatePoints(1000)\n",
    "outputSet = extendedgrahamscan(inputSet)\n",
    "plt.figure()\n",
    "\n",
    "#first do a scatter plot of the inputSet\n",
    "input_xs, input_ys = zip(*inputSet)\n",
    "plt.scatter(input_xs, input_ys)\n",
    "\n",
    "#then do a polygon plot of the computed covex hull\n",
    "outputSet.append(outputSet[0]) #first create a 'closed loop' by adding the first point at the end of the list\n",
    "output_xs, output_ys = zip(*outputSet)\n",
    "plt.plot(output_xs, output_ys) \n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "cell_id": "00009-55cba226-1513-4476-b823-f663bfbbd9c2",
    "deepnote_cell_type": "code",
    "deepnote_to_be_reexecuted": true,
    "execution_millis": 4,
    "source_hash": "b623e53d"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "deepnote": {},
  "deepnote_execution_queue": [],
  "deepnote_notebook_id": "bd5b347f-0689-4042-8156-bb654aa7a51e",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}