grahamscan.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8, 2)\n",
      "[(7, 7), (3, 9), (5, 6), (2, 10), (-1, 8), (6, 3), (4, 4), (1, 4)]\n",
      "coordinates of convex hull are: [(8, 2), (7, 7), (2, 10), (-1, 8), (1, 4)]\n"
     ]
    }
   ],
   "source": [
    "# from matplotlib import pyplot as plt # for plotting\n",
    "from math import atan2 # for coputing polar angle\n",
    "\n",
    "\n",
    "def sort_key(point, P):\n",
    "    angle = atan2(point[1] - P[1], point[0] - P[0])\n",
    "    distance_squared = (point[0] - P[0])**2 + (point[1] - P[1])**2\n",
    "    return (angle, distance_squared)\n",
    "\n",
    "def orientation(a, b, c):\n",
    "    val = (b[1] - a[1]) * (c[0] - b[0]) - (b[0] - a[0]) * (c[1] - b[1])\n",
    "    if val == 0:\n",
    "        return \"COLINEAR\"\n",
    "    elif val > 0:\n",
    "        return \"CW\"\n",
    "    else:\n",
    "        return \"CCW\"\n",
    "\n",
    "def grahamscan(inputSet):\n",
    "    '''\n",
    "    Returns the list of points that lie on the convex hull (graham scan algorithm)\n",
    "            Parameters:\n",
    "                    inputSet (list): a list of 2D points\n",
    "\n",
    "            Returns:\n",
    "                    outputSet (list): a list of 2D points\n",
    "    '''\n",
    "    #ADD YOUR CODE HERE\n",
    "\n",
    "    xs,ys = zip(*inputSet)      #unzip initial x and y coord lists\n",
    "    # plt.scatter(xs,ys)\n",
    "\n",
    "    min_y = float('inf')\n",
    "    min_x = float('inf')\n",
    "    min_tuple = None    \n",
    "\n",
    "    for point in inputSet:\n",
    "        if point[1] < min_y:\n",
    "            min_y = point[1]\n",
    "            min_tuple = point\n",
    "        elif point[1] == min_y:\n",
    "           if point[0] < min_x:\n",
    "                min_tuple = point\n",
    "\n",
    "    if min_tuple is not None:\n",
    "        P = min_tuple\n",
    "        inputSet.remove(P)\n",
    "        print(P)\n",
    "                \n",
    "        #sort the inputSet by polar angle with respect to P\n",
    "        sorted_inputSet = sorted(inputSet, key=lambda point: sort_key(point, P))\n",
    "        print(sorted_inputSet)\n",
    "        #print(sorted_inputSet)\n",
    "        outputSet = []\n",
    "        outputSet.append(P)\n",
    "        outputSet.append(sorted_inputSet[0])\n",
    "\n",
    "        #for each point in sorted_inputSet, we need to determine whether poimt is a left or right turn\n",
    "        #if left turn, add to stack. If right turn, pop from stack\n",
    "\n",
    "        for i in range(1, len(sorted_inputSet)):\n",
    "            #remove top of stack if turning clcokwise\n",
    "            while len(outputSet) > 1 and orientation(outputSet[-2], outputSet[-1], sorted_inputSet[i]) != \"CCW\":\n",
    "                outputSet.pop()\n",
    "            outputSet.append(sorted_inputSet[i]) \n",
    "        return outputSet  \n",
    "points = [(1,4),(5,6),(2,10),(8,2),(-1,8),(6,3),(7,7),(4,4),(3,9)]\n",
    "# points = [(0, 0), (0, 4), (-4, 0), (5, 0), (0, -6), (1, 0)]\n",
    "convex_hull = grahamscan(points)\n",
    "print(\"coordinates of convex hull are:\", convex_hull)"
   ]
  }
 ],
 "metadata": {
  "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.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}