grp-001-0005code.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# COMP0005 - GROUP COURSEWORK 2023-24\n",
    "# Gesture Recognition via Convex Hull "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the cell below for all python code needed to realise the **Jarvis march algorithm** (including auxiliary points structures and functions needed by this algorithm - if any). The `jarvismarch()` function itself should take as input parameter a list of 2D points (`inputSet`), and reorientation the subset of such points (`outputSet`) that lie on the convex hull."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (16, 10)\n",
    "plt.rcParams['font.size'] = 20 \n",
    "\n",
    "# Utilities\n",
    "\n",
    "class Point2D:\n",
    "    \"\"\"\n",
    "    Represents a 2D point with x and y coordinates.\n",
    "    \"\"\"\n",
    "\n",
    "    x: float\n",
    "    y: float\n",
    "    def __init__(self, x, y):\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "\n",
    "    def __lt__(self, other: 'Point2D') -> bool:\n",
    "        # Defines less than for points -- used for finding the leftmost point\n",
    "        return self.x < other.x or (self.x == other.x and self.y < other.y)\n",
    "\n",
    "    def __eq__(self, other: 'Point2D') -> bool:\n",
    "        # Defines equality for points -- used for testing\n",
    "        return self.x == other.x and self.y == other.y\n",
    "\n",
    "    def __repr__(self) -> str:\n",
    "        return f\"({self.x}, {self.y})\"\n",
    "    \n",
    "def distance_squared(p1: Point2D, p2: Point2D) -> float:\n",
    "    \"\"\"Calculates the squared Euclidean distance between two points.\"\"\"\n",
    "    return (p1.x - p2.x)**2 + (p1.y - p2.y)**2\n",
    "\n",
    "def polar_angle_y(p0: Point2D, p: Point2D) -> float:\n",
    "    \"\"\"Computes the polar angle of p relative to reference point p0, with y-axis as the reference axis.\"\"\"\n",
    "    dx = p.x - p0.x\n",
    "    dy = p.y - p0.y\n",
    "\n",
    "    if dx == 0 and dy == 0:\n",
    "        return 0\n",
    "    \n",
    "    # Special case to handle points directly to the left of p0 \n",
    "    if dx == 0 and dy > 0:\n",
    "        return math.pi / 2 \n",
    "    \n",
    "    return math.atan2(-dx, dy)\n",
    "\n",
    "def leftmost_point(points: list[Point2D]) -> Point2D:\n",
    "    \"\"\"Finds the leftmost point (smallest x, then smallest y).\"\"\"\n",
    "    return min(points)\n",
    "\n",
    "def copy_points(points: list[Point2D]) -> list[Point2D]:\n",
    "    \"\"\"Creates a copy of a list of points.\"\"\"\n",
    "    return [point for point in points]\n",
    "\n",
    "CLOCKWISE = 1\n",
    "ANTI_CLOCKWISE = -1\n",
    "COLINEAR = 0\n",
    "def orientation(p: Point2D, q: Point2D, r: Point2D) -> int:\n",
    "    \"\"\"Determines orientation of three points (clockwise, counter-clockwise, or colinear).\"\"\"\n",
    "    cross_product = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)\n",
    "\n",
    "    if math.isclose(cross_product, 0):\n",
    "        return COLINEAR\n",
    "    return ANTI_CLOCKWISE if cross_product > 0 else CLOCKWISE\n",
    "\n",
    "def plot_points(input_set: list[Point2D], output_set: list[Point2D]):\n",
    "    \"\"\"Plots the input points and the computed convex hull using matplotlib. (For debugging)\"\"\"\n",
    "    xs = [p.x for p in input_set]\n",
    "    ys = [p.y for p in input_set]\n",
    "    plt.scatter(xs, ys, color='blue')  # Set the color of input points to blue\n",
    "    xs = [p.x for p in output_set]\n",
    "    ys = [p.y for p in output_set]\n",
    "    # close the loop\n",
    "    xs.append(output_set[0].x)\n",
    "    ys.append(output_set[0].y)\n",
    "    # Set the color of hull points to red with red lines and dots\n",
    "    plt.plot(xs, ys, color='red', linestyle='-', marker='o')\n",
    "    plt.show()\n",
    "\n",
    "def get_median(times: list[float]) -> float:\n",
    "    \"\"\"Calculates the median value of a list of numbers.\"\"\"\n",
    "    n = len(times)\n",
    "    if n % 2 == 0:\n",
    "        return (times[n // 2 - 1] + times[n // 2]) / 2\n",
    "    return times[n // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jarvis_march(input_set: list[Point2D]) -> list[Point2D]:\n",
    "    \"\"\"\n",
    "    Returns the list of points that lie on the convex hull (jarvis march algorithm)\n",
    "    https://en.wikipedia.org/wiki/Gift_wrapping_algorithm\n",
    "    Args:\n",
    "        input_set: The list of points to compute the convex hull for.\n",
    "\n",
    "    Returns:\n",
    "        A list of points that lie on the convex hull.\n",
    "    \"\"\"\n",
    "    # Start with the leftmost point\n",
    "    point_on_hull = leftmost_point(input_set)\n",
    "    convex_hull = [] \n",
    "\n",
    "    while True:\n",
    "        convex_hull.append(point_on_hull)\n",
    "        # Start with the first point as the endpoint of the segment from point_on_hull\n",
    "        end_point = input_set[0]\n",
    "\n",
    "        for j in range(0, len(input_set)):\n",
    "            # Check against all other points\n",
    "            dir = orientation(convex_hull[-1], end_point, input_set[j])\n",
    "            if (\n",
    "                end_point == point_on_hull or # skip duplicate points\n",
    "                dir == ANTI_CLOCKWISE or\n",
    "                (dir == COLINEAR and \n",
    "                    distance_squared(convex_hull[-1], input_set[j]) > distance_squared(convex_hull[-1], end_point)\n",
    "                )\n",
    "            ):  \n",
    "                # found a point that is more counterclockwise or is on the same line but further away\n",
    "                end_point = input_set[j]\n",
    "\n",
    "        point_on_hull = end_point\n",
    "\n",
    "        # check if we have wrapped around to the first point\n",
    "        if end_point == convex_hull[0]:\n",
    "            break\n",
    "\n",
    "    return convex_hull"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the cell below for all python code needed to realise the **Graham scan** algorithm (including auxiliary data structures and functions needed by this algorithm - if any). The `grahamscan()` 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`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sorting functions\n",
    "\n",
    "GREATER_THAN = 1\n",
    "EQUAL = 0\n",
    "LESS_THAN = -1\n",
    "def compare(p0: Point2D, p1: Point2D, p2: Point2D) -> int:\n",
    "    \"\"\"\n",
    "    Compares two points relative to a reference point for use in polar angle (y) sorting.\n",
    "    Note that polar angle (y) has y as the reference axis and is measured in the clockwise direction.\n",
    "\n",
    "    Args:\n",
    "        p0: The reference point.\n",
    "        p1: The first point to compare.\n",
    "        p2: The second point to compare.\n",
    "\n",
    "    Returns:\n",
    "        GREATER_THAN (1) if p1 has a larger polar angle (y) than p2 relative to p0.\n",
    "        LESS_THAN (-1) if p1 has a smaller polar angle (y) than p2 relative to p0.\n",
    "        EQUAL (0) if p1 and p2 have the same polar (y) angle or if the difference \n",
    "            falls within a tolerance due to floating-point inaccuracies.\n",
    "    \"\"\"\n",
    "    if p1 == p0:\n",
    "        return LESS_THAN\n",
    "    if p2 == p0:\n",
    "        return GREATER_THAN\n",
    "\n",
    "    # first compare by angle\n",
    "    angle1 = polar_angle_y(p0, p1)\n",
    "    angle2 = polar_angle_y(p0, p2)\n",
    "\n",
    "    if not math.isclose(angle1, angle2):\n",
    "        return LESS_THAN if angle1 < angle2 else GREATER_THAN\n",
    "\n",
    "    # if angles are equal, compare by distance_squared_squared\n",
    "    sq_dist1 = distance_squared(p0, p1)\n",
    "    sq_dist2 = distance_squared(p0, p2)\n",
    "\n",
    "    if sq_dist1 < sq_dist2:\n",
    "        return LESS_THAN\n",
    "    if sq_dist1 > sq_dist2:\n",
    "        return GREATER_THAN\n",
    "\n",
    "    return EQUAL\n",
    "\n",
    "def quick_sort(points: list[Point2D], p0: Point2D) -> list[Point2D]:\n",
    "    \"\"\"\n",
    "    Sorts a list of points in-place by their polar angle (y) relative to a reference point p0,\n",
    "    using the QuickSort algorithm.\n",
    "    https://en.wikipedia.org/wiki/Quicksort\n",
    "    \"\"\"\n",
    "    def partition(points: list[Point2D], low: int, high: int) -> int:\n",
    "        pivot = points[high]  \n",
    "        i = low - 1 # index of smaller element\n",
    "\n",
    "        for j in range(low, high):\n",
    "            if compare(p0, points[j], pivot) <= 0: # angle with points[j] is less than or equal to angle with pivot\n",
    "                i += 1\n",
    "                points[i], points[j] = points[j], points[i]\n",
    "\n",
    "        points[i + 1], points[high] = points[high], points[i + 1] # swap the pivot with the element at i + 1\n",
    "        return i + 1\n",
    "\n",
    "    def _quick_sort(points: list[Point2D], low: int, high: int):\n",
    "        if low < high:\n",
    "            pivot_index = partition(points, low, high)\n",
    "            _quick_sort(points, low, pivot_index - 1)\n",
    "            _quick_sort(points, pivot_index + 1, high)\n",
    "        \n",
    "    _quick_sort(points, 0, len(points) - 1)\n",
    "    return points  \n",
    "    \n",
    "def merge_sort(points: list[Point2D], p0: Point2D) -> list[Point2D]:\n",
    "    \"\"\"\n",
    "    Sorts a list of points by their polar angle (y) relative to a reference point p0,\n",
    "    using the MergeSort algorithm.\n",
    "    https://en.wikipedia.org/wiki/Merge_sort\n",
    "    \"\"\"\n",
    "    def merge(left: list[Point2D], right: list[Point2D]) -> list[Point2D]:\n",
    "        result = []\n",
    "        while left and right:\n",
    "            if compare(p0, left[0], right[0]) <= 0: # angle with left[0] is less than or equal to angle with right[0]\n",
    "                result.append(left.pop(0))\n",
    "            else:\n",
    "                result.append(right.pop(0))\n",
    "        result.extend(left or right)\n",
    "        return result\n",
    "   \n",
    "    if len(points) > 1:\n",
    "        mid = len(points) // 2\n",
    "        left = merge_sort(points[:mid], p0)\n",
    "        right = merge_sort(points[mid:], p0)\n",
    "        return merge(left, right)\n",
    "    else:\n",
    "        return points\n",
    "    \n",
    "def heap_sort(points: list[Point2D], p0: Point2D) -> list[Point2D]:\n",
    "    \"\"\"\n",
    "    Sorts a list of points by their polar angle (y) relative to a reference point p0,\n",
    "    using the HeapSort algorithm.\n",
    "    https://en.wikipedia.org/wiki/Heapsort\n",
    "    \"\"\"\n",
    "    def heapify(points: list[Point2D], n: int, i: int):\n",
    "        \"\"\"\n",
    "        Builds a max-heap from an array.\n",
    "\n",
    "        Args:\n",
    "            points: The array to be heapified.\n",
    "            n: The size of the heap.\n",
    "            i: The index of the parent node.\n",
    "        \"\"\"\n",
    "        largest = i  # Initialize the index of the largest element as the root\n",
    "        l = 2 * i + 1  # Index of the left child\n",
    "        r = 2 * i + 2  # Index of the right child\n",
    "\n",
    "        # Compare with the left child (if within bounds)\n",
    "        if l < n and compare(p0, points[l], points[largest]) > 0:\n",
    "            largest = l\n",
    "\n",
    "        # Compare with the right child (if within bounds)\n",
    "        if r < n and compare(p0, points[r], points[largest]) > 0:\n",
    "            largest = r\n",
    "\n",
    "        # If the root was not the largest, swap and recursively heapify\n",
    "        if largest != i:\n",
    "            points[i], points[largest] = points[largest], points[i]\n",
    "            heapify(points, n, largest)\n",
    "\n",
    "    def _heap_sort(points: list[Point2D]):\n",
    "        \"\"\"Performs heap sort on the given array.\"\"\"\n",
    "        n = len(points)\n",
    "\n",
    "        # Build the max-heap\n",
    "        for i in range(n // 2 - 1, -1, -1):\n",
    "            heapify(points, n, i)\n",
    "\n",
    "        # Extract elements one by one by swapping the root with the end and heapifying\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            points[i], points[0] = points[0], points[i]\n",
    "            heapify(points, i, 0)\n",
    "\n",
    "    _heap_sort(points)\n",
    "    return points\n",
    "\n",
    "\n",
    "def sorted_by_polar_angle_y(\n",
    "        p0: Point2D,\n",
    "        input_set: list[Point2D],\n",
    "        sorting_algorithm: callable\n",
    "    ) -> list[Point2D]:\n",
    "    \"\"\"\n",
    "    Sorts a list of points by their polar angle (y) relative to a reference point p0.\n",
    "    Polar angle (y) has y as the reference axis and is measured in the clockwise direction.\n",
    "    \"\"\"\n",
    "    return sorting_algorithm(input_set, p0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def graham_scan(\n",
    "        input_set: list[Point2D],\n",
    "        sorting_algorithm = merge_sort # default sorting algorithm \n",
    "    ) -> list[Point2D]:\n",
    "    \"\"\"\n",
    "    Returns the list of points that lie on the convex hull (graham scan algorithm)\n",
    "    https://en.wikipedia.org/wiki/Graham_scan\n",
    "\n",
    "    Args:\n",
    "        input_set: The list of points to compute the convex hull for.\n",
    "        sorting_algorithm: The sorting algorithm to use for sorting the points by polar angle.\n",
    "\n",
    "    Returns:\n",
    "        A list of points that lie on the convex hull sorted in anti-clockwise order.\n",
    "    \"\"\"\n",
    "    if len(input_set) < 3:\n",
    "        return input_set\n",
    "\n",
    "    # Find the point with the lowest x-coordinate (and the lowest y-coordinate in case of a tie)\n",
    "    p0 = leftmost_point(input_set)\n",
    "\n",
    "    convex_hull = []\n",
    "    input_set = sorted_by_polar_angle_y(p0, input_set, sorting_algorithm)\n",
    "\n",
    "    for i in range(len(input_set)):\n",
    "        # keep removing the last point from the convex hull until the last three points make an anti-clockwise turn\n",
    "        while (\n",
    "            len(convex_hull) > 1 and\n",
    "            orientation(convex_hull[-2], convex_hull[-1], input_set[i]) != CLOCKWISE\n",
    "        ):\n",
    "            convex_hull.pop()\n",
    "\n",
    "        # add the next point to the convex hull\n",
    "        convex_hull.append(input_set[i])\n",
    "    return convex_hull\n",
    "\n",
    "def graham_scan_quick_sort(input_set: list[Point2D]) -> list[Point2D]:\n",
    "    \"\"\"Computes the convex hull using the Graham scan algorithm with QuickSort.\"\"\"\n",
    "    return graham_scan(input_set, quick_sort)\n",
    "\n",
    "def graham_scan_merge_sort(input_set: list[Point2D]) -> list[Point2D]:\n",
    "    \"\"\"Computes the convex hull using the Graham scan algorithm with MergeSort.\"\"\"\n",
    "    return graham_scan(input_set, merge_sort)\n",
    "\n",
    "def graham_scan_heap_sort(input_set: list[Point2D]) -> list[Point2D]:\n",
    "    \"\"\"Computes the convex hull using the Graham scan algorithm with HeapSort.\"\"\"\n",
    "    return graham_scan(input_set, heap_sort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the cell below for all python code needed to realise the **Chen's** algorithm (including auxiliary data structures and functions needed by this algorithm - if any). The `chen()` 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`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition_points(input_set: list[Point2D], partition_size: int) -> list[list[Point2D]]: \n",
    "    \"\"\"Partitions the input set into smaller sets of size partition_size.\"\"\"\n",
    "    return [input_set[i:i + partition_size] for i in range(0, len(input_set), partition_size)]\n",
    "\n",
    "def right_tangent(p: Point2D, hull: list[Point2D]) -> int:\n",
    "    \"\"\"\n",
    "    Returns the index of the right tangent of a point p to a convex hull.\n",
    "    Adapted from: https://gist.github.com/tixxit/252229\n",
    "    \"\"\"\n",
    "    left = 0\n",
    "    right = len(hull)\n",
    "    left_prev_dir = orientation(p, hull[0], hull[-1])\n",
    "    left_next_dir = orientation(p, hull[0], hull[(left + 1) % len(hull)])\n",
    "    while left < right:\n",
    "        mid = (left + right) // 2\n",
    "        mid_prev_dir = orientation(p, hull[mid],  hull[(mid - 1) % len(hull)])\n",
    "        mid_next_dir = orientation(p, hull[mid],  hull[(mid + 1) % len(hull)])\n",
    "        mid_side_dir = orientation(p, hull[left], hull[mid])\n",
    "        if mid_prev_dir != ANTI_CLOCKWISE and mid_next_dir != ANTI_CLOCKWISE:\n",
    "            # tangent touches mid -> found\n",
    "            return mid\n",
    "        elif mid_side_dir == CLOCKWISE and (left_next_dir == ANTI_CLOCKWISE or left_prev_dir == left_next_dir) or \\\n",
    "                mid_side_dir == ANTI_CLOCKWISE and mid_prev_dir == ANTI_CLOCKWISE:\n",
    "            # focus on the left side of loop\n",
    "            right = mid\n",
    "        else:\n",
    "            left = mid + 1\n",
    "            # switch clockwise to anti-clockwise or vice versa\n",
    "            left_prev_dir = -mid_next_dir\n",
    "            if left >= right:\n",
    "                return left - 1\n",
    "            left_next_dir = orientation(p, hull[left], hull[(left + 1) % len(hull)])\n",
    "    return left\n",
    "\n",
    "def visualize_convex_hulls(partitions: list[list[Point2D]], convex_hulls: list[list[Point2D]]):\n",
    "    \"\"\"Visualizes the partitions and the computed convex hulls using matplotlib. (For debugging)\"\"\"\n",
    "    for i in range(len(partitions)):\n",
    "        xs = [p.x for p in partitions[i]]\n",
    "        ys = [p.y for p in partitions[i]]\n",
    "        plt.scatter(xs, ys)\n",
    "        xs = [p.x for p in convex_hulls[i]]\n",
    "        ys = [p.y for p in convex_hulls[i]]\n",
    "        # close the loop\n",
    "        xs.append(convex_hulls[i][0].x)\n",
    "        ys.append(convex_hulls[i][0].y)\n",
    "        plt.plot(xs, ys)\n",
    "    plt.show()\n",
    "\n",
    "def get_hull_leftmost_point(hulls: list[list[Point2D]]) -> tuple[int, int]:\n",
    "    \"\"\"Returns the index of the hull and the index of the leftmost point in the hull -> (hull_index, point_index).\"\"\"\n",
    "    min_x = math.inf\n",
    "    min_x_index = 0\n",
    "    min_x_hull_index = 0\n",
    "    for i in range(len(hulls)):\n",
    "        for j in range(len(hulls[i])):\n",
    "            if hulls[i][j].x < min_x:\n",
    "                min_x = hulls[i][j].x\n",
    "                min_x_index = j\n",
    "                min_x_hull_index = i\n",
    "    return min_x_hull_index, min_x_index\n",
    "\n",
    "def _chan(input_set: list[Point2D], m: int) -> list[Point2D] | None:\n",
    "    \"\"\"\n",
    "    The core implementation of Chan's algorithm.\n",
    "\n",
    "    Args:\n",
    "        input_set: The list of input points.\n",
    "        m: The initial partition size.\n",
    "\n",
    "    Returns:\n",
    "        A list of points representing the convex hull of the input set, or None if m is not large enough.\n",
    "    \"\"\"\n",
    "    # partition the input set into smaller sets and compute the convex hulls\n",
    "    hulls = [graham_scan(partition) for partition in partition_points(input_set, m)]\n",
    "\n",
    "    # merge the convex hulls\n",
    "    convex_hull = []\n",
    "\n",
    "    # start with the leftmost point in the leftmost hull\n",
    "    next_hull_index, next_point_index = get_hull_leftmost_point(hulls)\n",
    "    \n",
    "    for _ in range(m + 1):\n",
    "        convex_hull.append((next_hull_index, next_point_index))\n",
    "        next_point = hulls[next_hull_index][next_point_index] \n",
    "\n",
    "        end_hull_index = next_hull_index\n",
    "        # we start with the previous point in the current hull in case it is most anti-clockwise\n",
    "        end_point_index = (next_point_index + 1) % len(hulls[next_hull_index])\n",
    "\n",
    "        for i in range(0, len(hulls)):\n",
    "            if i == next_hull_index: # skip the current hull (already considered)\n",
    "                continue\n",
    "\n",
    "            j = right_tangent(next_point, hulls[i])\n",
    "                \n",
    "            p = hulls[i][j]\n",
    "            end_point = hulls[end_hull_index][end_point_index]\n",
    "            dir = orientation(next_point, end_point, p)\n",
    "            if (\n",
    "                end_point == next_point or # skip duplicate points\n",
    "                dir == ANTI_CLOCKWISE or\n",
    "                (dir == COLINEAR and \n",
    "                    distance_squared(next_point, p) > distance_squared(next_point, end_point)\n",
    "                )\n",
    "            ):\n",
    "                # Found a more clockwise point\n",
    "                end_hull_index = i\n",
    "                end_point_index = j\n",
    "\n",
    "        # update the next hull and point    \n",
    "        next_hull_index = end_hull_index\n",
    "        next_point_index = end_point_index\n",
    "\n",
    "        # check if we have wrapped around to the first point\n",
    "        if (next_hull_index, next_point_index) == convex_hull[0]:\n",
    "            return [hulls[i][j] for i, j in convex_hull]\n",
    "        \n",
    "    return None\n",
    "\n",
    "def chan(input_set: list[Point2D]) -> list[Point2D] | None:\n",
    "    \"\"\"\n",
    "    Computes the convex hull of an input set of points using Chan's algorithm.\n",
    "    https://en.wikipedia.org/wiki/Chan%27s_algorithm\n",
    "\n",
    "    Args:\n",
    "        input_set: The list of input points.\n",
    "\n",
    "    Returns:\n",
    "        A list of points representing the convex hull of the input set, or None if the hull is not found.\n",
    "    \"\"\"\n",
    "    n = len(input_set)\n",
    "\n",
    "    if n < 3:\n",
    "        return input_set\n",
    "    \n",
    "    m = 3\n",
    "    while m < n:\n",
    "        output_set = _chan(input_set, m)\n",
    "        if output_set is not None:\n",
    "            return output_set\n",
    "\n",
    "        m *= m\n",
    "\n",
    "    return _chan(input_set, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the cell below to implement the **synthetic data generator** needed by your experimental framework (including any auxiliary data structures and functions you might need - be mindful of code readability and reusability)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "DEFAULT_MIN_X, DEFAULT_MAX_X = 0, 32767 - 1\n",
    "DEFAULT_MIN_Y, DEFAULT_MAX_Y = 0, 32767 - 1\n",
    "\n",
    "class TestDataGenerator():\n",
    "    \"\"\"\n",
    "    Generates sets of 2D points for testing convex hull algorithms.\n",
    "    Controls point distribution, range, and reproducibility (via seed).\n",
    "\n",
    "    Includes methods for:\n",
    "    * Colinear points (all on a line)\n",
    "    * Uniformly distributed random points\n",
    "    * Points forming a specific size convex hull with a specific number of total points\n",
    "\n",
    "    Attributes:\n",
    "        seed: The seed for the random number generator.\n",
    "        min_x: The minimum x-coordinate for the points.\n",
    "        max_x: The maximum x-coordinate for the points.\n",
    "        min_y: The minimum y-coordinate for the points.\n",
    "        max_y: The maximum y-coordinate for the points.\n",
    "    \"\"\"\n",
    "    def __init__(\n",
    "            self, \n",
    "            seed: int | None = None, \n",
    "            min_x: int = DEFAULT_MIN_X, max_x: int = DEFAULT_MAX_X, \n",
    "            min_y: int = DEFAULT_MIN_Y, max_y: int = DEFAULT_MAX_Y\n",
    "        ):\n",
    "        self._rng = random.Random(seed)\n",
    "        self.min_x = min_x\n",
    "        self.max_x = max_x\n",
    "        self.min_y = min_y\n",
    "        self.max_y = max_y\n",
    "\n",
    "    def set_seed(self, seed: int) -> None:\n",
    "        \"\"\"Sets the seed for the random number generator.\"\"\"\n",
    "        self._rng.seed(seed)\n",
    "\n",
    "    def generate_colinear_points(self, test_size: int) -> list[Point2D]:\n",
    "        \"\"\"Generates colinear points within the specified range of the data generator.\"\"\"\n",
    "        # not possible to generate more points than the range if we only take integer values\n",
    "        if test_size > (self.max_x - self.min_x + 1) or test_size > (self.max_y - self.min_y + 1):\n",
    "            raise ValueError(\"The number of points should be less than or equal to the range of the points\")\n",
    "        \n",
    "        xs = self._rng.sample(range(self.min_x, self.max_x + 1), test_size)\n",
    "        slope = self._rng.choice([-1, 0, 1])\n",
    "        intercept = self.max_y if slope == -1 else 0\n",
    "        return [Point2D(x, slope * x + intercept) for x in xs]\n",
    "\n",
    "    def generate_random_points_uniform(self, test_size: int) -> list[Point2D]:\n",
    "        \"\"\"Generates uniformly distributed random points within the specified range of the data generator.\"\"\"\n",
    "        if test_size > (self.max_x - self.min_x + 1) * (self.max_y - self.min_y + 1):\n",
    "            raise ValueError(\"The number of points should be less than or equal to the range of the points\")\n",
    "        \n",
    "        return [\n",
    "            Point2D(self._rng.randint(self.min_x, self.max_x), self._rng.randint(self.min_y, self.max_y)) \n",
    "            for _ in range(test_size)\n",
    "        ]\n",
    "    \n",
    "    def generate_points(self, num_convex_hull_vertices: int, num_points: int) -> list[Point2D]:\n",
    "        \"\"\"\n",
    "        Generates points forming a convex hull with a specific number of vertices and total points.\n",
    "        Warning: for large enough num_hull_vertices, the actual number of hull points might be less significantly\n",
    "        less than num_hull_vertices due to the constraints of the range.\n",
    "        \"\"\"\n",
    "\n",
    "        if num_convex_hull_vertices > num_points:\n",
    "            raise ValueError(\"The number of convex hull vertices should be less than or equal to the number of points\")\n",
    "        \n",
    "        if num_convex_hull_vertices == 1:\n",
    "            assert num_points == 1\n",
    "            return [Point2D(self._rng.randint(self.min_x, self.max_x), self._rng.randint(self.min_y, self.max_y))]\n",
    "        \n",
    "        if num_convex_hull_vertices == 2:\n",
    "            return self.generate_colinear_points(num_points)\n",
    "\n",
    "        points: list[Point2D] = []\n",
    "        # adding inscribed triangle\n",
    "        points.append(Point2D(0, 2))\n",
    "        points.append(Point2D(math.sqrt(3), -1))\n",
    "        points.append(Point2D(-math.sqrt(3), -1))\n",
    "\n",
    "        # adding the rest of the outer points\n",
    "        RADIUS_OUTER = 2\n",
    "        for i in range(num_convex_hull_vertices - 3):\n",
    "            angle = self._rng.uniform(0, 2 * math.pi)\n",
    "            x = RADIUS_OUTER * math.cos(angle)\n",
    "            y = RADIUS_OUTER * math.sin(angle)\n",
    "            points.append(Point2D(x, y))\n",
    "        \n",
    "        # adding the inner points\n",
    "        num_inner_points = num_points - num_convex_hull_vertices\n",
    "        RADIUS_INNER = 1\n",
    "        i = 0\n",
    "        while i < num_inner_points:\n",
    "            x = self._rng.uniform(-RADIUS_INNER, RADIUS_INNER)\n",
    "            y = self._rng.uniform(-RADIUS_INNER, RADIUS_INNER)\n",
    "            if x**2 + y**2 < 1: # inside the unit circle\n",
    "                points.append(Point2D(x, y))\n",
    "                i += 1\n",
    "        \n",
    "        # scale and translate the points to fit the range (and convert into integers)\n",
    "        x_min, x_max = -RADIUS_OUTER, RADIUS_OUTER\n",
    "        y_min, y_max = -RADIUS_OUTER, RADIUS_OUTER\n",
    "        \n",
    "        for i in range(len(points)):\n",
    "            points[i].x = round(self.min_x + (points[i].x - x_min) * (self.max_x - self.min_x) / (x_max - x_min))\n",
    "            points[i].y = round(self.min_y + (points[i].y - y_min) * (self.max_y - self.min_y) / (y_max - y_min))\n",
    "\n",
    "        # shuffle the points\n",
    "        self._rng.shuffle(points)\n",
    "        \n",
    "        return points\n",
    "    \n",
    "    def generate_integer_convex_hulls(self, maximum_hull_vertices: int) -> list[Point2D]:\n",
    "        \"\"\"\n",
    "        Generates and saves the gauranteed sized worst case data for convex hull algorithms up to a specific number of vertices.\n",
    "\n",
    "        Note: might take a long time to generate for large enough maximum_hull_vertices. Try smaller values if needed.\n",
    "        \"\"\"\n",
    "        worst_case_data = {}\n",
    "        n = 1\n",
    "        h = 1\n",
    "        # adaptive steps because the higher the h, the more points are needed to generate a convex hull\n",
    "        step = 10 # first derivative step\n",
    "        step_2nd = 10 # second derivative step\n",
    "        while h <= maximum_hull_vertices:\n",
    "            data = self.generate_points(n, n)\n",
    "            convex_hull = graham_scan(data)\n",
    "            h = len(convex_hull)\n",
    "            self._rng.shuffle(convex_hull) # shuffle to avoid bias\n",
    "            worst_case_data[h] = convex_hull\n",
    "            n += step\n",
    "            step += step_2nd\n",
    "            step_2nd += 100\n",
    "\n",
    "        print(f\"Worst case data premade up to h={h} ✅\")\n",
    "        return worst_case_data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the cell below to implement the requested **experimental framework** API."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import timeit\n",
    "\n",
    "class ExperimentalFramework():\n",
    "    \"\"\"\n",
    "    Facilitates the experimental evaluation of convex hull algorithms.\n",
    "\n",
    "    Features:\n",
    "        * Tracks execution times and the number of computed hull vertices.\n",
    "        * Provides plotting functions for analysis.\n",
    "        * Compares algorithm performance.\n",
    "        * Flexible configuration of experiments (independent variable, trials per run).\n",
    "\n",
    "\n",
    "    Attributes:\n",
    "        experiment_name: The name of the experiment.\n",
    "        independent_variable: The independent variable for the experiment.\n",
    "        algorithms: A dictionary of algorithm names and their corresponding functions.\n",
    "        times: A dictionary of algorithm names and their (variable, execution times) tuples.\n",
    "        num_hull_vertices: A dictionary of algorithm names and their (variable, number of hull vertices) tuples.\n",
    "        trials_per_run: The number of trials to run for each configuration.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, experiment_name: str):\n",
    "        self.experiment_name = experiment_name\n",
    "        self.independent_variable = \"Input size\"\n",
    "        self.algorithms: dict[str, callable] = {}\n",
    "        self.times: dict[str, list[tuple[float, list[float]]]] = {}\n",
    "        self.num_hull_vertices: dict[str, list[tuple[float, list[int]]]] = {}\n",
    "        self.trials_per_run = 10\n",
    "\n",
    "    def set_independent_variable(self, variable: str):\n",
    "        self.independent_variable = variable\n",
    "\n",
    "    def set_trials_per_run(self, trials: int):\n",
    "        self.trials_per_run = trials\n",
    "\n",
    "    def add_algorithm(self, name: str, algorithm: callable):\n",
    "        \"\"\"Adds an algorithm to the framework.\"\"\"\n",
    "        self.algorithms[name] = algorithm\n",
    "        self.times[name] = []\n",
    "        self.num_hull_vertices[name] = []\n",
    "\n",
    "    def run_from_input(self, variable: int, input_set: list[Point2D]):\n",
    "        \"\"\"\n",
    "        Runs the registered algorithms on a specific input set and records timing information and the number of hull vertices.\n",
    "\n",
    "        For each algorithm, multiple trials are performed to account for variations in execution time.  \n",
    "\n",
    "        Args:\n",
    "            variable: The current value of the independent variable (e.g., the input size).\n",
    "            input_set: A list of Point2D objects representing the input for the algorithms.\n",
    "        \"\"\"\n",
    "        for name in self.algorithms:\n",
    "            times_taken = []\n",
    "            num_hull_vertices = []\n",
    "            for _ in range(self.trials_per_run):\n",
    "                # points are copied to avoid having a modified input_set in following trials\n",
    "                trial_set = copy_points(input_set)\n",
    "                start_time = timeit.default_timer()\n",
    "                convex_hull = self.algorithms[name](trial_set)\n",
    "                end_time = timeit.default_timer()\n",
    "                times_taken.append(end_time - start_time)\n",
    "                num_hull_vertices.append(len(convex_hull))\n",
    "    \n",
    "            times_taken.sort()\n",
    "            num_hull_vertices.sort()\n",
    "            self.times[name].append((variable, times_taken))\n",
    "            self.num_hull_vertices[name].append((variable, num_hull_vertices))\n",
    "\n",
    "    def run_from_generator(\n",
    "            self,\n",
    "            variable: int, \n",
    "            data_generator: TestDataGenerator, \n",
    "            num_points: int, \n",
    "            num_convex_hull_vertices: int | None = None\n",
    "        ):\n",
    "        \"\"\"\n",
    "        Runs the registered algorithms on multiple randomly generated inputs and records timing information and the number of hull vertices.\n",
    "\n",
    "        Utilizes a TestDataGenerator to create diverse sets of points, either purely random or with a specified number of convex hull vertices. \n",
    "        Algorithm performance is taken over multiple trials to account for variations in execution time.\n",
    "\n",
    "        Args:\n",
    "            variable: The current value of the independent variable.\n",
    "            data_generator: A TestDataGenerator object used to create input sets.\n",
    "            num_points: The total number of points to generate in each input set.\n",
    "            num_convex_hull_vertices: If provided, the generator will create inputs with this number of points on the convex hull; otherwise, purely random point sets are used.\n",
    "        \"\"\"\n",
    "        times_taken_per_algorithm = {name: [] for name in self.algorithms}\n",
    "        hull_vertices_per_algorithm = {name: [] for name in self.algorithms}\n",
    "        \n",
    "        for _ in range(self.trials_per_run):\n",
    "            if num_convex_hull_vertices is None:\n",
    "                input_set = data_generator.generate_random_points_uniform(num_points)\n",
    "            else: \n",
    "                input_set = data_generator.generate_points(num_convex_hull_vertices, num_points)\n",
    "                \n",
    "            for name in self.algorithms:\n",
    "                trial_set = copy_points(input_set)\n",
    "                start_time = timeit.default_timer()\n",
    "                convex_hull = self.algorithms[name](trial_set)\n",
    "                end_time = timeit.default_timer()\n",
    "                times_taken_per_algorithm[name].append(end_time - start_time)\n",
    "                hull_vertices_per_algorithm[name].append(len(convex_hull))\n",
    "\n",
    "        for name in self.algorithms:\n",
    "            times_taken = times_taken_per_algorithm[name]\n",
    "            num_hull_vertices = hull_vertices_per_algorithm[name]\n",
    "            times_taken.sort()\n",
    "            num_hull_vertices.sort()\n",
    "            self.times[name].append((variable, times_taken))\n",
    "            self.num_hull_vertices[name].append((variable, num_hull_vertices))\n",
    "\n",
    "    def _plot_values(self, values: dict[str, list[tuple[float, float]]], ylabel: str):\n",
    "        \"\"\"Plots the values in the given dictionary with each key as a separate graph.\"\"\"\n",
    "        for name in values:\n",
    "            x = [p[0] for p in values[name]]\n",
    "            y = [p[1] for p in values[name]]\n",
    "            plt.plot(x, y, label=name)\n",
    "        plt.xlabel(self.independent_variable)\n",
    "        plt.ylabel(ylabel)\n",
    "        plt.title(self.experiment_name)\n",
    "        plt.legend()\n",
    "\n",
    "    def plot_mean_times(self):\n",
    "        \"\"\"Plots the mean time taken for each algorithm.\"\"\"\n",
    "        plt.figure()\n",
    "        means = {}\n",
    "        for name in self.times:\n",
    "            means[name] = [(p[0], sum(p[1]) / self.trials_per_run) for p in self.times[name]]\n",
    "        self._plot_values(means, f\"Mean time taken (s) (n={self.trials_per_run})\")\n",
    "        plt.show()\n",
    "\n",
    "    def plot_median_times(self):\n",
    "        \"\"\"Plots the median time taken for each algorithm.\"\"\"\n",
    "        plt.figure()\n",
    "        medians = {}\n",
    "        for name in self.times:\n",
    "            medians[name] = [(p[0], get_median(p[1])) for p in self.times[name]]\n",
    "        self._plot_values(medians, f\"Median time taken (s) (n={self.trials_per_run})\")\n",
    "        plt.show()\n",
    "\n",
    "    def plot_min_times(self, max_y: float | None = None):\n",
    "        \"\"\"Plots the minimum time taken for each algorithm.\"\"\"\n",
    "        plt.figure()\n",
    "        mins = {}\n",
    "        for name in self.times:\n",
    "            mins[name] = [(p[0], p[1][0]) for p in self.times[name]]\n",
    "        self._plot_values(mins, f\"Minimum time taken (s) (n={self.trials_per_run})\")\n",
    "        if max_y is not None:\n",
    "            plt.ylim(0, max_y)\n",
    "        plt.show()\n",
    "\n",
    "    def _plot_boxplot(\n",
    "            self, \n",
    "            values: dict[str, list[tuple[float, list[float]]]], \n",
    "            ylabel: str,\n",
    "            number_of_boxes: int = 10\n",
    "        ):\n",
    "        \"\"\"\n",
    "        Plots a boxplot of the values in the given dictionary with each key as a separate graph.\n",
    "        The boxplots are overlaid on top of the median values.\n",
    "        \"\"\"\n",
    "        plt.figure()\n",
    "        medians = {}\n",
    "        for name in values:\n",
    "            medians[name] = [(p[0], get_median(p[1])) for p in values[name]]\n",
    "        self._plot_values(medians, \"\")\n",
    "        for name in values:\n",
    "            num_of_boxes = min(number_of_boxes, len(values[name]))\n",
    "            spacing = len(values[name]) // num_of_boxes\n",
    "            times = values[name][::spacing]\n",
    "            xs = [p[0] for p in times]\n",
    "            ys = [p[1] for p in times]\n",
    "\n",
    "            box_size = (max(xs) - min(xs)) / (3 * num_of_boxes + 1)\n",
    "            plt.boxplot(ys, positions=xs, showfliers=False, widths=box_size)\n",
    "\n",
    "        plt.xlabel(self.independent_variable)\n",
    "        plt.ylabel(ylabel)\n",
    "        plt.title(self.experiment_name)\n",
    "        plt.show()\n",
    "            \n",
    "    def plot_boxplot_time_vs_n(self, number_of_boxes: int = 10):\n",
    "        \"\"\"Plots a boxplot of the time taken for each algorithm, overlaid on top of the median values.\"\"\"\n",
    "        self._plot_boxplot(self.times, f\"Median time taken (s) (n={self.trials_per_run})\", number_of_boxes)\n",
    "\n",
    "    def plot_boxplot_hull_vertices_vs_n(self, number_of_boxes: int = 10):\n",
    "        \"\"\"Plots a boxplot of the number of hull vertices for each algorithm, overlaid on top of the median values.\"\"\"\n",
    "        self._plot_boxplot(self.num_hull_vertices, f\"Median number of hull vertices (n={self.trials_per_run})\", number_of_boxes)\n",
    "\n",
    "    def _plot_min_time_ratios(self, algorithm1: str, algorithm2: str, label: str | None = None):\n",
    "        \"\"\"Plots the ratio of the minimum time taken for one algorithm to another.\"\"\"\n",
    "        # computing the minimums\n",
    "        mins1 = [(p[0], p[1][0]) for p in self.times[algorithm1]]\n",
    "        mins2 = [(p[0], p[1][0]) for p in self.times[algorithm2]]\n",
    "        x = [p[0] for p in mins1]\n",
    "        y = [p[1] / mins2[i][1] for i, p in enumerate(mins1)]\n",
    "        plt.plot(x, y, label=label if label is not None else f\"{algorithm1} / {algorithm2}\")\n",
    "\n",
    "    @staticmethod\n",
    "    def plot_multiple_experiments_min_time_ratios(\n",
    "            experiments: list['ExperimentalFramework'], \n",
    "            algorithm1: str, \n",
    "            algorithm2: str\n",
    "        ):\n",
    "        \"\"\"Plots the ratio of the minimum time taken for one algorithm to another across multiple experiments.\"\"\"\n",
    "        plt.figure()\n",
    "        for experiment in experiments:\n",
    "            experiment._plot_min_time_ratios(algorithm1, algorithm2, experiment.experiment_name)\n",
    "        \n",
    "        # plot the line for the ratio of 1\n",
    "        x = [p[0] for p in experiments[0].times[algorithm1]]\n",
    "        y = [1 for _ in range(len(x))]\n",
    "        plt.plot(x, y, label=\"1\", linestyle=\"--\", color=\"black\")\n",
    "        plt.xlabel(experiments[0].independent_variable)\n",
    "        plt.ylabel(f\"Minimum time ratio (n={experiments[0].trials_per_run})\")\n",
    "        plt.title(f\"{algorithm1} / {algorithm2}\")\n",
    "        plt.legend()\n",
    "        plt.show()\n",
    "\n",
    "    ### CORRECTNESS TESTS ###\n",
    "        \n",
    "    @staticmethod\n",
    "    def test_correctness_line(algorithm: callable):\n",
    "        \"\"\"Tests the correctness of an algorithm on colinear points.\"\"\"\n",
    "        test_size = 100\n",
    "        data_generator = TestDataGenerator(seed=42)\n",
    "        for _ in range(1000):\n",
    "            colinear_points = data_generator.generate_colinear_points(test_size)\n",
    "            convex_hull = algorithm(colinear_points)\n",
    "            assert min(convex_hull) == min(colinear_points) and max(convex_hull) == max(colinear_points)\n",
    "\n",
    "    @staticmethod\n",
    "    def test_correctness_triangle(algorithm: callable):\n",
    "        \"\"\"Tests the correctness of an algorithm on points forming a triangle.\"\"\"\n",
    "        test_size = 100\n",
    "        data_generator = TestDataGenerator(seed=42)\n",
    "        points = data_generator.generate_points(3, test_size)\n",
    "        triangle_points = data_generator.generate_points(3, 3)\n",
    "        convex_hull = algorithm(points)\n",
    "        triangle_points.sort()\n",
    "        convex_hull.sort()\n",
    "        assert convex_hull == triangle_points\n",
    "\n",
    "    @staticmethod\n",
    "    def test_correctness_square(algorithm: callable):\n",
    "        \"\"\"Tests the correctness of an algorithm on points forming a square.\"\"\"\n",
    "        points = [\n",
    "            Point2D(0, 0), Point2D(0, 1),\n",
    "            Point2D(0, 2), Point2D(1, 0),\n",
    "            Point2D(2, 0), Point2D(1, 2),\n",
    "            Point2D(2, 1), Point2D(2, 2)\n",
    "        ]\n",
    "        convex_points = [\n",
    "            Point2D(0, 0), Point2D(0, 2),\n",
    "            Point2D(2, 2), Point2D(2, 0)\n",
    "        ]\n",
    "        convex_hull = algorithm(points)\n",
    "        convex_points.sort()\n",
    "        convex_hull.sort()\n",
    "        assert convex_hull == convex_points\n",
    "    \n",
    "    @staticmethod\n",
    "    def test_correctness_circle(algorithm: callable):\n",
    "        \"\"\"Tests the correctness of an algorithm on points forming a circle.\"\"\"\n",
    "        test_size = 100\n",
    "        data_generator = TestDataGenerator(seed=42)\n",
    "        points = data_generator.generate_points(test_size, test_size)\n",
    "        convex_hull = algorithm(points)\n",
    "        convex_hull.sort()\n",
    "        points.sort()\n",
    "        # assert convex_hull == points\n",
    "        if convex_hull != points:\n",
    "            print(\"failed\")\n",
    "            plot_points([], convex_hull)\n",
    "\n",
    "    @staticmethod\n",
    "    def test_correctness_line_rogue_point(algorithm: callable):\n",
    "        \"\"\"Tests the correctness of an algorithm on colinear points with a rogue point.\"\"\"\n",
    "        test_size = 100\n",
    "        data_generator = TestDataGenerator(seed=42)\n",
    "        for _ in range(100):\n",
    "            colinear_points = data_generator.generate_colinear_points(test_size)\n",
    "            convex_points = [min(colinear_points), max(colinear_points)]\n",
    "            colinear_points.append(Point2D(20000, 100))\n",
    "            convex_points.append(colinear_points[-1])\n",
    "            convex_hull = algorithm(colinear_points)\n",
    "            convex_points.sort()\n",
    "            convex_hull.sort()\n",
    "            assert convex_hull == convex_points"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use the cell below to illustrate the python code you used to **fully evaluate** the three convex hull algortihms under considerations. The code below should illustrate, for example, how you made used of the **TestDataGenerator** class to generate test data of various size and properties; how you instatiated the **ExperimentalFramework** class to  evaluate each algorithm using such data, collect information about their execution time, plots results, etc. Any results you illustrate in the companion PDF report should have been generated using the code below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testing the correctness of the algorithms\n",
    "for algorithm in [jarvis_march, graham_scan_quick_sort, graham_scan_merge_sort, graham_scan_heap_sort, chan]:\n",
    "    print(f\"Testing correctness of {algorithm.__name__}...\")\n",
    "    ExperimentalFramework.test_correctness_triangle(algorithm)\n",
    "    ExperimentalFramework.test_correctness_square(algorithm)\n",
    "    ExperimentalFramework.test_correctness_circle(algorithm)\n",
    "    ExperimentalFramework.test_correctness_line_rogue_point(algorithm)\n",
    "    ExperimentalFramework.test_correctness_line(algorithm)\n",
    "    print(f\"{algorithm.__name__} passed all tests ✅\")\n",
    "\n",
    "print(\"All algorithms passed the correctness tests ✅\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize the data generator\n",
    "data_generator = TestDataGenerator(seed=42)\n",
    "\n",
    "# Initialize worst case data\n",
    "MAX_H = 2_200\n",
    "worst_case_data = data_generator.generate_integer_convex_hulls(MAX_H) # might take ~6-10 minutes to generate depending on the machine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment Graham Scan (Average Case)\n",
    "experiment_graham_average = ExperimentalFramework(\"Graham Scan on Randomly (Uniformly) Generated Points\")\n",
    "experiment_graham_average.set_independent_variable(\"Number of points\")\n",
    "experiment_graham_average.set_trials_per_run(50)\n",
    "\n",
    "experiment_graham_average.add_algorithm(\"Graham Scan (Quick Sort)\", graham_scan_quick_sort)\n",
    "experiment_graham_average.add_algorithm(\"Graham Scan (Merge Sort)\", graham_scan_merge_sort)\n",
    "experiment_graham_average.add_algorithm(\"Graham Scan (Heap Sort)\", graham_scan_heap_sort)\n",
    "\n",
    "start = 2\n",
    "end = 150_000 \n",
    "step = 1_000\n",
    "plot_step = 10_000\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    experiment_graham_average.run_from_generator(n, data_generator, n)\n",
    "\n",
    "    if (n - start) % plot_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        experiment_graham_average.plot_boxplot_time_vs_n(8)\n",
    "\n",
    "experiment_graham_average.plot_boxplot_time_vs_n(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment Graham Scan (Worst Case)\n",
    "experiment_graham_worst = ExperimentalFramework(\"Graham Scan on Worst Case (n=h) Points\")\n",
    "experiment_graham_worst.set_independent_variable(\"Number of points\")\n",
    "experiment_graham_worst.set_trials_per_run(50)\n",
    "\n",
    "experiment_graham_worst.add_algorithm(\"Graham Scan (Quick Sort)\", graham_scan_quick_sort)\n",
    "experiment_graham_worst.add_algorithm(\"Graham Scan (Merge Sort)\", graham_scan_merge_sort)\n",
    "experiment_graham_worst.add_algorithm(\"Graham Scan (Heap Sort)\", graham_scan_heap_sort)\n",
    "\n",
    "plot_step = 10\n",
    "for i, h in enumerate(sorted(worst_case_data)):\n",
    "    # shuffle the points to avoid any bias\n",
    "    data_generator._rng.shuffle(worst_case_data[h])\n",
    "    experiment_graham_worst.run_from_input(h, worst_case_data[h])\n",
    "\n",
    "    if i % plot_step == 0:\n",
    "        print(f\"Finished running for h={h}\")\n",
    "        experiment_graham_worst.plot_boxplot_time_vs_n(8)\n",
    "\n",
    "experiment_graham_worst.plot_boxplot_time_vs_n(8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment Jarvis March (Average Case)\n",
    "experiment_jarvis_average = ExperimentalFramework(\"Jarvis March on Randomly (Uniformly) Generated Points\")\n",
    "experiment_jarvis_average.set_independent_variable(\"Number of points\")\n",
    "experiment_jarvis_average.set_trials_per_run(50)\n",
    "\n",
    "experiment_jarvis_average.add_algorithm(\"Jarvis March\", jarvis_march)\n",
    "\n",
    "start = 2\n",
    "end = 250_000\n",
    "step = 5_000\n",
    "plot_step = 10_000\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    experiment_jarvis_average.run_from_generator(n, data_generator, n)\n",
    "\n",
    "    if (n - start) % plot_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        experiment_jarvis_average.plot_boxplot_time_vs_n(5)\n",
    "\n",
    "experiment_jarvis_average.plot_boxplot_time_vs_n(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment Jarvis March (Worst Case)\n",
    "experiment_jarvis_worst = ExperimentalFramework(\"Jarvis March on Worst Case (n=h) Points\")\n",
    "experiment_jarvis_worst.set_independent_variable(\"Number of points\")\n",
    "experiment_jarvis_worst.set_trials_per_run(10)\n",
    "\n",
    "experiment_jarvis_worst.add_algorithm(\"Jarvis March\", jarvis_march)\n",
    "\n",
    "plot_step = 10\n",
    "for i, h in enumerate(sorted(worst_case_data)):\n",
    "    # shuffle the points to avoid any bias\n",
    "    data_generator._rng.shuffle(worst_case_data[h])\n",
    "    experiment_jarvis_worst.run_from_input(h, worst_case_data[h])\n",
    "    if i % plot_step == 0:\n",
    "        print(f\"Finished running for h={h}\")\n",
    "        experiment_jarvis_worst.plot_min_times()\n",
    "\n",
    "experiment_jarvis_worst.plot_min_times()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment Chan's Algorithm (Average Case)\n",
    "experiment_chan_average = ExperimentalFramework(\"Chan's Algorithm on Randomly (Uniformly) Generated Points\")\n",
    "experiment_chan_average.set_independent_variable(\"Number of points\")\n",
    "experiment_chan_average.set_trials_per_run(50)\n",
    "\n",
    "experiment_chan_average.add_algorithm(\"Chan's Algorithm\", chan)\n",
    "\n",
    "start = 10\n",
    "end = 250_000\n",
    "step = 5_000\n",
    "plot_step = 10_000\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    experiment_chan_average.run_from_generator(n, data_generator, n)\n",
    "\n",
    "    if (n - start) % plot_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        experiment_chan_average.plot_boxplot_time_vs_n(5)\n",
    "\n",
    "experiment_chan_average.plot_boxplot_time_vs_n(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Experiment Chan's Algorithm (Worst Case)\n",
    "experiment_chan_worst = ExperimentalFramework(\"Chan's Algorithm on Worst Case (n=h) Points\")\n",
    "experiment_chan_worst.set_independent_variable(\"Number of points\")\n",
    "experiment_chan_worst.set_trials_per_run(20)\n",
    "\n",
    "experiment_chan_worst.add_algorithm(\"Chan's Algorithm\", chan)\n",
    "\n",
    "plot_step = 10\n",
    "for i, h in enumerate(sorted(worst_case_data)):\n",
    "    experiment_chan_worst.run_from_input(h, worst_case_data[h])\n",
    "\n",
    "    if i % plot_step == 0:\n",
    "        print(f\"Finished running for h={h}\")\n",
    "        experiment_chan_worst.plot_min_times()\n",
    "\n",
    "experiment_chan_worst.plot_min_times()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Comparing All Algorithms Together in Randomly (Uniformly) Generated Points\n",
    "experiment_all_average = ExperimentalFramework(\"Comparing All Algorithms Together on Randomly (Uniformly) Generated Points\")\n",
    "experiment_all_average.set_independent_variable(\"Number of points\")\n",
    "experiment_all_average.set_trials_per_run(50)\n",
    "\n",
    "experiment_all_average.add_algorithm(\"Jarvis March\", jarvis_march)\n",
    "experiment_all_average.add_algorithm(\"Graham Scan\", graham_scan_merge_sort)\n",
    "experiment_all_average.add_algorithm(\"Chan's Algorithm\", chan)\n",
    "\n",
    "start = 2\n",
    "end = 100_000\n",
    "step = 1000\n",
    "plot_step = 10_000\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    experiment_all_average.run_from_generator(n, data_generator, n)\n",
    "\n",
    "    if (n - start) % plot_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        experiment_all_average.plot_boxplot_time_vs_n(6)\n",
    "\n",
    "experiment_all_average.plot_boxplot_time_vs_n(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Analysis of Worst Case Time Complexity of All Algorithms\n",
    "experiment_worst_case = ExperimentalFramework(\"Worst Case (n=h) Time Complexity of All Algorithms\")\n",
    "experiment_worst_case.set_independent_variable(\"Number of points\")\n",
    "experiment_worst_case.set_trials_per_run(20)\n",
    "\n",
    "experiment_worst_case.add_algorithm(\"Jarvis March\", jarvis_march)\n",
    "experiment_worst_case.add_algorithm(\"Graham Scan\", graham_scan_merge_sort)\n",
    "experiment_worst_case.add_algorithm(\"Chan's Algorithm\", chan)\n",
    "\n",
    "start = 2\n",
    "end = 30_000\n",
    "step = 100\n",
    "plot_step = 100\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    input_set = data_generator.generate_points(n, n)\n",
    "    experiment_worst_case.run_from_input(n, input_set)\n",
    "\n",
    "    if (n - start) % plot_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        experiment_worst_case.plot_min_times(0.1)\n",
    "\n",
    "experiment_worst_case.plot_min_times(0.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Analysis to see when Chan's Algorithm is better than Graham Scan\n",
    "# we fix h to multiple different values (e.g. 3, 5, 10, 20, 50, 100) and vary n\n",
    "\n",
    "# Experiment Chan's Algorithm vs Graham Scan\n",
    "chans_algorithm = \"Chan's Algorithm\"\n",
    "graham_scan_algorithm = \"Graham Scan\"\n",
    "hs = [3, 10, 20] #, 10, 20, 50, 100]\n",
    "experiments = {h: ExperimentalFramework(f\"Chan's Algorithm / Graham Scan (h={h})\") for h in hs}\n",
    "for h in hs:\n",
    "    experiments[h].set_independent_variable(\"Number of points\")\n",
    "    experiments[h].set_trials_per_run(20)\n",
    "    experiments[h].add_algorithm(chans_algorithm, chan)\n",
    "    experiments[h].add_algorithm(graham_scan_algorithm, graham_scan_merge_sort)\n",
    "\n",
    "start = 0\n",
    "end = 100_000\n",
    "step = 100\n",
    "plot_step = 10_000\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    for h in hs:\n",
    "        input_set = data_generator.generate_points(h, h+n)\n",
    "        experiments[h].run_from_input(n, input_set)\n",
    "    if (n - start) % plot_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        ExperimentalFramework.plot_multiple_experiments_min_time_ratios(list(experiments.values()), chans_algorithm, graham_scan_algorithm)\n",
    "\n",
    "ExperimentalFramework.plot_multiple_experiments_min_time_ratios(list(experiments.values()), chans_algorithm, graham_scan_algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Standalone plot to see if h converges as n increases for generate_random_points_uniform\n",
    "experiment_h_vs_n = ExperimentalFramework(\"Number of Hull Vertices vs Number of Points\")\n",
    "experiment_h_vs_n.set_independent_variable(\"Number of points\")\n",
    "experiment_h_vs_n.set_trials_per_run(100)\n",
    "\n",
    "# we can use any algorithm here, we just want something to compute h\n",
    "experiment_h_vs_n.add_algorithm(\"Number of Hull Vertices\", jarvis_march) \n",
    "\n",
    "start = 2\n",
    "end = 100_000\n",
    "step = 10\n",
    "print_step = 10_000\n",
    "data_generator.set_seed(42)\n",
    "for n in range(start, end + step, step):\n",
    "    experiment_h_vs_n.run_from_generator(n, data_generator, n)\n",
    "\n",
    "    if (n - start) % print_step == 0:\n",
    "        print(f\"Finished running for n={n}\")\n",
    "        experiment_h_vs_n.plot_boxplot_hull_vertices_vs_n(6)\n",
    "\n",
    "experiment_h_vs_n.plot_boxplot_hull_vertices_vs_n(6)"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}