assignment_08.sagews

import math
import random
import functools

# '''
# ---====================---
#    Begin Helper Methods
# ---====================---
# '''

def merge(arr, l, m, r, cmp, reverse):
    cmp_helper = cmp
    if reverse: cmp_helper = lambda a, b: not cmp(a, b)
    things = [l, m, r]
    types = list(map(type, things))
    l = int(l)
    m = int(m)
    r = int(r)
    left_midpoint = m - l + 1
    right_midpoint = r - m
    temp_arr_left = [arr[l + i] for i in range(left_midpoint)]
    temp_arr_right = [arr[m + 1 + i] for i in range(right_midpoint)]

    i = 0
    j = 0
    k = l

    while i < left_midpoint and j < right_midpoint:
        if cmp_helper(temp_arr_left[i], temp_arr_right[j]):
            arr[k] = temp_arr_left[i]
            i += 1
        else:
            arr[k] = temp_arr_right[j]
            j += 1
        k += 1

    while i < left_midpoint:
        arr[k] = temp_arr_left[i]
        i += 1
        k += 1
    while j < right_midpoint:
        arr[k] = temp_arr_right[j]
        j += 1
        k += 1

def merge_sort(arr, left_index=None, right_index=None, cmp=lambda a, b: a < b, reverse=False):
    if left_index is None:
        left_index = 0
    if right_index is None:
        right_index = len(arr) - 1
    if left_index < right_index:
        midpoint = math.floor((left_index + right_index - 1)/2)
        merge_sort(arr, left_index, midpoint, cmp, reverse)
        merge_sort(arr, midpoint + 1, right_index, cmp, reverse)
        merge(arr, left_index, midpoint, right_index, cmp, reverse)

def css_classes():
    '''
    pseudo-css-class generator!!
    dictionary mapping { pseudo-classname: inline-style }
    '''
    classes = {
        'border-light': 'border: 1px solid #a0aec0;',
        'text-light': 'color: #e6fffa;',
        'text-dark': 'color: #cbd5e0;',
        'rounded': 'border-radius: 3px;',
        'bg-dark': 'background-color: #1a202c;',
        'w-max': 'width: max-content;',
        'flex': 'display: flex;',
        'block': 'display: block;',
        'justify-between': 'justify-content: space-between;',
        'text-center': 'text-align: center;',
        'font-sans': 'font-family: system-ui, -apple-system, BlinkMacSystemFont, "Segoe UI", Roboto, "Helvetica Neue", Arial, "Noto Sans", sans-serif, "Apple Color Emoji", "Segoe UI Emoji", "Segoe UI Symbol", "Noto Color Emoji";',
        'font-serif': 'font-family: Georgia, Cambria, "Times New Roman", Times, serif;',
        'font-mono': 'font-family: Menlo, Monaco, Consolas, "Liberation Mono", "Courier New", monospace;',
    }
    spacings = range(0, 12)
    scale_factor = 1.6 # note, cocalc uses rootFontSize=10px, I want to pretend it's 16px
    scale_rem = lambda x: str(round(x * scale_factor, 3))
    text_prefixes = 'xs sm base lg xl 2xl 3xl 4xl 5xl 6xl'.split()
    text_rem_sizes = [0.75, 0.875, 1, 1.125, 1.25, 1.5, 1.875, 2.25, 3, 4]
    classes.update({'text-{}'.format(text_prefixes[i]): 'font-size: {}rem;'.format(scale_rem(text_rem_sizes[i])) for i in range(len(text_prefixes))})
    spacing_opts = {
        'l': ['left: '],
        'r': ['right: '],
        't': ['top: '],
        'b': ['bottom: ']
    }
    spacing_opts.update({
        'x': spacing_opts['l'] + spacing_opts['r'],
        'y': spacing_opts['t'] + spacing_opts['b']
    })
    spacing_opts[''] = spacing_opts['x'] + spacing_opts['y']
    for spacing in spacings:
        space = str(round(scale_rem(spacing * 0.25), 2)) + 'rem; '
        for variant in ["margin", "padding"]:
            for prefix, rule_list in spacing_opts.items():
                classes[variant[0] + prefix + '-' + str(spacing)] = "".join([variant + "-" + rule + space for rule in rule_list])
                classes['-' + variant[0] + prefix + '-' + str(spacing * -1)] = "".join([variant + "-" + rule + space for rule in rule_list])
    return classes

def apply_classes(raw_html, classes=None):
    '''
    pseudo-css-class injector!!
    note, doesn't actually support bem cause Im not caring about uniqueness (ie. card__header can be affected by card)

    params:
    - raw_html: string containing html!!
    - classes: object mapping classes to further either standard class names or inline styles (simulates @apply behavior from tw)
    '''
    if classes is not None:
        for k, v in classes.items():
            raw_html = raw_html.replace(k, v)
    rules = css_classes()
    for rule, definition in rules.items():
        raw_html = raw_html.replace(rule, definition)
    return raw_html


def assignment_html(exernum, assignment, funcs=None, params=None):
    '''
    returns html for the assignment definition!

    func=[{
                'name': 'listswitch(lis, i, k)',
                'params': ['lis: some list', 'i: index', 'k: index'],
                'returns': ['lis with indices i and k switched']
            }],

    params:
    - exernum: number of the exercise
    - assignment: problem statement
    - func: optional list of dictionaries describing functions. needs the following key-value pairs
      - name: <string>
      - params: <list<string>>
      - returns: <list<string>>
    - params: optional list of interactive inputs
    '''
    res = '''
        <div style="font-sans text-base margin: 4rem 0;">
        <div style="text-xl mb-2 color: lime;">Exercise {}</div>
        <div style="ml-3 text-sm font-sans">
        <p><b>Assignment:</b> {}</p>
    '''.format(exernum, assignment)
    if funcs:
        for func in funcs:
            res += '<p><b>Function:</b><code style="font-mono block mt-4 ml-4">{}</code></p>'.format(func.get('name', ''))
            if 'params' in func:
                res += '<div style="ml-4"><i>params:</i><ul>'
                for param in func['params']:
                    res += "<li>{}</li>".format(param)
                res += "</ul></div>"
            if 'returns' in func:
                res += '<div style="ml-4"><i>returns:</i><ul>'
                for param in func['returns']:
                    res += "<li>{}</li>".format(param)
                res += "</ul></div>"
    if params:
        res += "<p><b>Interactive input:</b></p><ul>"
        for param in params:
            res += "<li>{}</li>".format(param)
        res += "</ul>"
    res += '</div></div>'
    return apply_classes(res)

def plot_arr(arr):
    '''
    helper for show so that we can pass lists
    '''
    return functools.reduce(lambda a,b : a + b, arr)

def show_all(arr):
    '''
    helper for show so that we can pass lists
    '''
    for el in arr:
        show(el)

def dist(point_a, point_b):
    '''
    helper to give distance between two points of equal dimension
    params:
    - point_a: tuple for point a
    - point_b: tuple for point b
    '''
    return sum([(a - b) ** 2 for a, b in zip(point_a, point_b)]) ** 0.5

def float_eq(a, b, epsilon=0.00001):
    '''
    checks if a ~= b within epsilon
    '''
    return abs(a - b) < epsilon

def all_indices(arr, el):
    '''
    helper to give all indices of an element in an array
    '''
    return [i for i in range(len(arr)) if arr[i] == el]

def random_list(length, min_val=0, max_val=20):
    '''
    makes a random list
    '''
    return [random.randint(min_val, max_val) for _ in range(length)]

def arr_cmp(arr, cmp=lambda a, b: a < b, reverse=False):
    '''
    min/max helper with comparison function
    params:
    - arr: array
    - amp: comparison function
    - reverse: order of results
    returns extreme of arr according to cmp
    '''
    cmp_helper = cmp
    if reverse: cmp_helper = lambda a, b: not cmp(a, b)
    if len(arr) == 0:
        return None # maybe should raise an exception, not sure
    res = arr[0]
    for el in arr:
        if cmp_helper(el, res):
            res = el
    return res

def assignment(definition, func):
    '''
    assignment runner
    '''
    show(definition())
    interact(func)

def ccw(a, b, c):
    """
    determines if three points are clockwise, counterclockwise, or colinear
    """
    area2 = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
    if      (area2 < 0): return -1 # clockwise
    elif    (area2 > 0): return  1 # counterclockwise
    else:                return  0 # colinear

def draw_polygon(points, arrows=False, plot=False):
    # annoying, but arrow takes two points and line takes a list, so we wrap in a list and unpack
    connector = arrow if arrows else line
    inject_points = lambda arr: arr if arrows else [arr]
    res = [
        point(a, rgbcolor="blue", size=30) +
        text(i, (a[0] + 0.1, a[1] + 0.1), horizontal_alignment='left', color='green') +
        connector(*inject_points([points[i-1], points[i]]), rgbcolor="red")
    for i, a in enumerate(points)]
    if plot: show(plot_arr(res), figsize=[5,5])
    else: return res

def check_point_on_segment(query_point, a, b):
    '''
    returns:
    |  0 if query point is a or b
    |  1 if query point is on line segment
    | -1 if query point is not on line segment
    '''
    if any([query_point == p for p in [a, b]]): return 0
    return 1 if float_eq(dist(a, query_point) + dist(query_point, b), dist(a, b)) else -1

random_point = lambda min_val=0, max_val=10: (random.randint(min_val, max_val), random.randint(min_val, max_val))

def random_points(n, min_val=0, max_val=10, noise=False):
    points = [random_point(min_val, max_val) for _ in range(n)]
    if noise: points = list(map(lambda a: [round(a[0]/(max_val/10), 3), round(a[1]/(max_val/10), 3)], points))
    return points

dot = lambda a, b: sum(c*d for c, d in zip(a, b))
vector_length = lambda v: math.sqrt(dot(v, v))
angle = lambda a, b: math.acos(dot(a, b) / (vector_length(a) * vector_length(b)))


# necessary globals for auto-labelling
labels = 'a b c d e f g h i j k l'.split()
current_label = 0

class inputs:
    def __init__(self):
        pass

    @staticmethod
    def radio(val=[0, 1], label='selector'):
        return selector(val, label=label)

    @staticmethod
    def box(val=None, label='input'):
        return input_box(default=str(val), label=label)

    @staticmethod
    def num(num=None, label=None, min_val=-10, max_val=10):
        global current_label
        global labels
        if not num:
            num = random.randint(min_val, max_val)
        if label in labels:
            # reset current_label
            current_label = labels.index(label) + 1
        if not label:
            # allow auto-labelling in alphabetical order
            label = labels[current_label]
            current_label += 1
            if current_label >= len(labels): current_label = 0
        return input_box(default=num, label=label)

    @staticmethod
    def arr(num=None, label='arr', min_val=-10, max_val=10):
        if not num:
            num = random.randint(3, 10)
        return input_box(default=str(random_list(num, min_val, max_val)), label=label)

    @staticmethod
    def switch(val=False, label='show'):
        return (label, val)

# '''
# ---========================---
#    End Helper Methods
#      --------
#    Begin Assignment Defs
# ---========================---
# '''

# 2.1.4, 2.6.1, 2.6.2, 2.6.3
assignment_defs = {
    '2.1.4': lambda: html(assignment_html(
        '2.1.4',
        'Make a function that takes any type of list and makes a new list that is the result of sorting the original list by a list of numbers using Insertion Sort. The original list should not be changed.',
        funcs=[{
            'name': 'insertion_sort(arr)',
            'params': [
                'querypoint: point to check',
                'arr: list of points defining the polygon',
            ],
            'returns': [
                '2, 0: point is in the interior of an edge of the polygon',
                '1, slope: point is inside polygon (slope is what is used by alg)',
                '0, 0: point is a vertex of the polygon',
                '-1, slope: point is outside the polygon'
            ]
        }],
        params=['(a) A list of points in the plane.', '(b) A switch to show the ray used']
    )),
    '2.6.1': lambda: html(assignment_html(
        '2.6.1',
        'Make a function that takes two points in the plane and finds the cosine of the polar angle of the vector starting at the first point and ending at the second point, and plot the points and the vector.',
        funcs=[{
            'name': 'cos_polar_angle(a, b)',
            'params': [
                'a, b: points in the plane',
            ],
            'returns': [
                'cosine of the polar angle of the vector starting at a and ending at b'
            ]
        }],
        params=['(a) A list of two points in the plane.']
    )),
    '2.6.2': lambda: html(assignment_html(
        '2.6.2',
        'Make a function that takes a list of points in the plane and finds the bottom left point and the list of other points, and plot the points.',
        funcs=[{
            'name': 'list_bottom_left(arr)',
            'params': [
                'arr: list of points in plane',
            ],
            'returns': [
                'list of two elements, [bottom left, all but bottom left]'
            ]
        }],
        params=['(a) A list of points in the plane.', '(b) A switch to show result']
    )),
    '2.6.3': lambda: html(assignment_html(
        '2.6.3',
        'Take a list of points in the plane and rank them in order of increasing polar angle with the bottom left point, and secondarily by increasing distance from the bottom left point, and plot the points.',
        funcs=[{
            'name': 'sort_by_polar(arr)',
            'params': [
                'arr: list of points',
            ],
            'returns': [
                'sorted list by polar/dist'
            ]
        }],
        params=['(a) A list of points in the plane.', '(b) A switch to show the result']
    )),
}


# '''
# ---========================---
#    End Assignment Defs
#      --------
#    Begin Assignment Methods
# ---========================---
# '''

def det(a, b):
    '''
    gives determinant of 2d matrix
    params:
    | a, b: arrays with > 2 elems
    returns:
    | determinant
    '''
    return a[0] * b[1] - a[1] * b[0]

def line_intersection(a1, a2, b1, b2):
    '''
    computes intersection of lines [a, b]
    params:
    | a1, a2: endpoints of line
    | b1, b2: endpoints of line
    returns:
    | x,y of intersection
    '''
    # get differences across axes
    xdiff = [a1[0] - a2[0], b1[0] - b2[0]]
    ydiff = [a1[1] - a2[1], b1[1] - b2[1]]
    # get divisor!
    div = det(xdiff, ydiff)
    if div == 0:
        raise Exception('lines do not intersect')
    d = [det(a1, a2) , det(b1, b2)]
    return det(d, xdiff) / div, det(d, ydiff) / div

def get_point_slope(a, b):
    '''
    derives point-slope form from two points on a line
    returns:
    | m: slope
    | c: y-intercept
    '''
    y = a[1] - b[1]
    m = y / (a[0] - b[0])
    c = a[1] - (m * a[0])
    return m, c

def point_on_line(querypoint, a, b):
    '''
    returns if querypoint is on the line ab
    '''
    # solves point-slope eq
    m, c = get_point_slope(a, b)
    if querypoint[1] == ((m * querypoint[0]) + c): return True
    return False

def line_intersects_line_segment(a1, a2, b1, b2):
    '''
    checks if line (a1, a2) intersects line segment (b1, b2)
    returns:
    | -1: does not intersect (b1, b2)
    |  0: contains one or both of (b1, b2)
    |  1: intersects interior of (b1, b2)
    '''
    # just have to check directions
    return -1 * ccw(a1, a2, b1) * ccw(a1, a2, b2)

def line_intersection_line_segment(a1, a2, b1, b2):
    '''
    checks if line (a1, a2) intersects line segment (b1, b2)
    returns:
    | intersection between (a1, a2) and (b1, b2)
    | None if doesn't intersect
    '''
    try:
        # if theres an intersection, check if intersection is on segment
        intersection = line_intersection(a1, a2, b1, b2)
        if check_point_on_segment(intersection, b1, b2) == 1:
            return intersection
    except: pass
    return None

def ray_intersects_line_segment(a1, a2, b1, b2):
    '''
    checks if ray (a1, a2) intersects line segment (b1, b2)
    returns:
    |  1: ray intersects the interior
    |  0: ray contains one or both of b1, b2
    | -1: does not intersect the line segment
    | -2: a1 is on the line segment (b1, b2)
    '''
    try:
        intersection = line_intersection(a1, a2, b1, b2)
        # checks if ray base is on line segment
        if check_point_on_segment(a1, b1, b2) == 0:
            return -2, None
        # checks if intersection is on the ray (maybe should write a 'ensure_tonicity(points, coord)')
        if check_point_on_segment(intersection, b1, b2) == 1:
            if a1[0] < a2[0] and intersection[0] >= a1[0]: return 1, intersection
            if a1[0] > a2[0] and intersection[0] <= a1[0]: return 1, intersection
        # checks if segment endpoints are on ray
        for point in [b1, b2]:
            if point_on_line(point, a1, a2):
                if a1[0] < a2[0] and point[0] >= a1[0]: return 0, point
                if a1[0] > a2[0] and point[0] <= a1[0]: return 0, point
    except: pass
    return -1, None

def point_in_polygon(querypoint, arr):
    '''
    checks if a point is in a polygon
    returns:
    | 2, 0: point is in the interior of an edge of the polygon
    | 1, slope: point is inside polygon (slope is what is used by alg)
    | 0, 0: point is a vertex of the polygon
    | -1, slope: point is outside the polygon
    | -2, 0: invalid polygon
    '''
    try:
        # checks for querypoint is a vertex and querypoint is on edge
        for i, point in enumerate(arr):
            if point == querypoint: return 0, 0
            if point_on_line(querypoint, arr[i-1], arr[i]): return 2, 0
    except:
        # encountered div-by-0 error
        return -2, 0
    ray_endpoint = None
    valid_ray = False
    while not valid_ray:
        # determine a ray-endpoint. randomly chooses and then checks validity
        valid_ray = True
        ray_endpoint = random_point(-10000, 10000)
        if ray_endpoint[0] == querypoint[0]:
            # avoid div-by-0 errs
            ray_endpoint[0] += 1
        for point in arr:
            if point_on_line(point, querypoint, ray_endpoint):
                valid_ray = False
                break
    # get slope
    slope, yint = get_point_slope(querypoint, ray_endpoint)
    num_intersections = 0
    for i, point in enumerate(arr):
        r, _ = ray_intersects_line_segment(querypoint, ray_endpoint, arr[i-1], arr[i])
        if r == 1:
            num_intersections += 1
    if num_intersections % 2 == 1:
        return 1, slope
    return -1, slope

def insertion_sort(arr, a1, a2):
    def compare(j, key_1, key_2):
        if a1[j] == key_1:
            return a2[j] >= key_2
        return a1[j] >= key_1
    for i in range(1, len(arr)):
        # would rather do this with callbacks @shift @replace, but can't think of a good way to preserve curr
        curr = arr[i]
        curr1 = a1[i]
        curr2 = a2[i]
        j = i - 1
        while j >= 0 and compare(j, curr1, curr2):
            arr[j+1] = arr[j]
            a1[j+1] = a1[j]
            a2[j+1] = a2[j]
            j -= 1
        arr[j+1] = curr
        a1[j+1] = curr1
        a2[j+1] = curr2





def sort_points(a, b):
    """
    sorts by y coordinate, in case of ties, sorts by x
    """
    if a[1] > b[1]: return 1
    if a[1] < b[1]: return -1
    if a[0] > b[0]: return 1
    if a[0] < b[0]: return -1
    return 0

def sort_polar(point):
    """
    returns a comparator for sorting by polar angle (from a given point)
    """
    def sort_stuff(a, b):
        diff = lambda p1, p2: [p1[0] - p2[0], p1[1] - p2[1]]
        if diff(a, point)[1] >= 0 and diff(b, point)[1] < 0:
            # if a is above point, and b is below
            return -1
        elif diff(b, point)[1] >= 0 and diff(a, point)[1] < 0:
            # if b is above point, and a is below
            return 1
        elif diff(a, point)[1] == 0 and diff(b, point)[1] == 0:
            # all on same y coord, resort to x coord
            if diff(a, point)[0] >= 0 and diff(b, point)[0] < 0:
                # if a is right of point, and b is left
                return -1
            elif diff(b, point)[0] >= 0 and diff(a, point)[0] < 0:
                # if b is right of point, and a is left
                return 1
            return  0 # they're the same point!
        else:
            return -1 * ccw(point, a, b) # otherwise, return clockwise
    return sort_stuff

def make_convex_hull(points):
    """
    returns list representing convex hull boundary vertices using the graham scan method
    params:
    - points: list of dictionaries representing points (must have keys=['x', 'y'])
    """
    stack = []
    points.sort(key=functools.cmp_to_key(sort_points))
    curr = points[0] # start at bottom most (leftmost as tiebreaker)
    stack.append(curr)
    points.sort(key=functools.cmp_to_key(sort_polar(curr))) # sort by polar angle
    for point in points:
        # remove top of the stack if we must turn clockwise to reach it!
        while (len(stack) > 1) and (ccw(stack[len(stack) - 2], stack[len(stack) - 1], point) < 0):
            stack.pop()
        stack.append(point) # put current point on the stack
    return stack

def cos_polar_angle(a, b):
    '''
    cosine of the polar angle of the vector starting at a and ending at b
    '''
    a = vector(a)
    b = vector(b)
    v = b - a
    u = vector([1, 0])
    return v.dot_product(u) / v.norm()

def list_bottom_left(arr):
    '''
    list of two elements, [bottom left, all but bottom left]
    '''
    merge_sort(arr, cmp=lambda a, b: a[0] < b[0] if a[1] == b[1] else a[1] < b[1])
    return arr[0], arr[1:]

def sort_by_polar(arr, point):
    '''
    sorted list by polar/dist
    '''
    def compare(a, b):
        try:
            angleA = -((a[0] - point[0]) / (a[1] - point[1]))
            angleB = -((b[0] - point[0]) / (b[1] - point[1]))
            if angle(point, a) == angle(point, b):
                return dist(point, a) < dist(point, b)
        except:
            return dist(point, a) < dist(point, b)
        return angleA - angleB < 0
    merge_sort(arr, cmp=compare)
    return arr


# '''
# ---==========================---
#    End Assignment Methods
#      --------
#    Begin Interactive Methods
# ---==========================---
# '''


def interact_point_in_polygon(
    points=inputs.box(val=random_points(5, min_val=0, max_val=1000, noise=True), label='List of Vertices of Polygon'),
    querypoint=inputs.box(val=random_point(), label='Test Vertex'),
    switch=inputs.switch(label='Show chosen ray'),
):
    opts = [
        'The point is a vertex of the polygon',
        'The point is inside polygon (slope is what is used by alg)',
        'The point is in the interior of an edge of the polygon',
        'invalid polygon',
        'The point is outside the polygon',
    ]
    result, slope = point_in_polygon(querypoint, points)
    ray_endpoints = [querypoint, [querypoint[0] + 2, querypoint[1] + (slope * 2)]]
    res = draw_polygon(points)
    res += [point(querypoint, rgbcolor="green", size=30)]
    if switch: res += [arrow(*ray_endpoints, rgbcolor='blue')]
    show_all([
        opts[result]
    ])
    show(plot_arr(res))

def interact_insertion_sort(
    original=inputs.box(val=[[5, 3], [2, 6], [-1, 4], [7, -2], [12, 3], [-3, 0], [5, 12], [1, 7]], label="Unsorted List"),
    aux1=inputs.box(val=[7, 5, 10, 2, 3, 4, 2, 6], label="First Comparison List"),
    aux2=inputs.box(val=[-1, 15, 2, 8, 5, 3, 1, 7], label="Second Comparison List"),
    switch=inputs.switch(label='Show sorted list'),
):
    orig = original[:]
    insertion_sort(original, aux1, aux2)
    res = [
        'Unsorted list: {}'.format(orig),
        'First comparison list: {}'.format(aux1),
        'Second comparison list: {}'.format(aux2),
    ]
    if switch: res += ['Sorted list: {}'.format(original)]
    show_all(res)


def interact_cos_polar_angle(
    points=inputs.box(val=random_points(2), label="List of two points")
):
    theta = cos_polar_angle(*points[0:2])
    show('The cosine of the polar angle: {}'.format(theta))
    show('Numerical approximation of the cosine of the polar angle: {}'.format(float(theta)))
    show('The polar angle in radians: {}'.format(math.acos(float(theta))))
    show('The polar angle in degrees: {}'.format(math.acos(float(theta)) * 360 / (2 * math.pi)))
    res = []
    res.append(point([0, 0], rgbcolor="red", size=30))
    res.append(point(points[0], rgbcolor="blue", size=30))
    res.append(point(points[1], rgbcolor="blue", size=30))
    res.append(line([[0, 0], points[0]], rgbcolor="blue"))
    res.append(line([[0, 0], points[1]], rgbcolor="blue"))
    res.append(arrow(points[0], points[1], rgbcolor="red"))
    show(plot_arr(res), figsize=[5,5])

def interact_list_bottom_left(
    points=inputs.box(val=random_points(10, max_val=1000, noise=True), label="List of points"),
    switch=inputs.switch(label='Show result')
):
    res = ['List: {}'.format(points[:])]
    bottom_left, rest = list_bottom_left(points)
    if switch:
        res += [
            'Bottom left point: {}'.format(bottom_left),
            'Other points: {}'.format(rest)
        ]
    plot_res = [point(p, rgbcolor="blue", size=30) for p in rest]
    plot_res += [text(i, [points[i][0] + 0.3, points[i][1] + 0.3] ) for i in range(len(points))]
    plot_res += [point(bottom_left, rgbcolor="red", size=50)]
    show_all(res)
    show(plot_arr(plot_res), figsize=[5, 5])

def interact_sort_by_polar(
    points=inputs.box(val=random_points(10), label="List of points"),
    switch=inputs.switch(label='Show result')
):
    bottom_left, rest = list_bottom_left(points)
    res = ['Original: {}'.format(points[:])]
    points_sorted = sort_by_polar(points, bottom_left)
    if switch:
        res += ['Sorted: {}'.format(points_sorted)]
    show_all(res)
    plot_res = [point(p, rgbcolor="blue", size=30) for p in points]
    plot_res += [text(i, [points[i][0] + 0.3, points[i][1] + 0.3] ) for i in range(len(points))]
    plot_res += [line([bottom_left, p], rgbcolor="green") for p in rest]
    show(plot_arr(plot_res), figsize=[5, 5])

interactive = {
    '2.1.4': interact_insertion_sort,
    '2.6.1': interact_cos_polar_angle,
    '2.6.2': interact_list_bottom_left,
    '2.6.3': interact_sort_by_polar
}

def run_interactive(run=interactive):
    for exernum, func in run.items():
        assignment(assignment_defs[exernum], func)

# '''
# ---=======================---
#    End Interactive Methods
#      ---------
#    Begin Main
# ---=======================---
# '''

def main():
    run_interactive()

main()

Exercise 2.6.1

Assignment: Make a function that takes two points in the plane and finds the cosine of the polar angle of the vector starting at the first point and ending at the second point, and plot the points and the vector.

Function:cos_polar_angle(a, b)

params:

• a, b: points in the plane

returns:

• cosine of the polar angle of the vector starting at a and ending at b

Interactive input:

• (a) A list of two points in the plane.

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc

Exercise 2.6.3

Assignment: Take a list of points in the plane and rank them in order of increasing polar angle with the bottom left point, and secondarily by increasing distance from the bottom left point, and plot the points.

Function:sort_by_polar(arr)

params:

• arr: list of points

returns:

• sorted list by polar/dist

Interactive input:

• (a) A list of points in the plane.
• (b) A switch to show the result

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc

Exercise 2.6.2

Assignment: Make a function that takes a list of points in the plane and finds the bottom left point and the list of other points, and plot the points.

Function:list_bottom_left(arr)

params:

• arr: list of points in plane

returns:

• list of two elements, [bottom left, all but bottom left]

Interactive input:

• (a) A list of points in the plane.
• (b) A switch to show result

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc

Exercise 2.1.4

Assignment: Make a function that takes any type of list and makes a new list that is the result of sorting the original list by a list of numbers using Insertion Sort. The original list should not be changed.

Function:insertion_sort(arr)

params:

• querypoint: point to check
• arr: list of points defining the polygon

returns:

• 2, 0: point is in the interior of an edge of the polygon
• 1, slope: point is inside polygon (slope is what is used by alg)
• 0, 0: point is a vertex of the polygon
• -1, slope: point is outside the polygon

Interactive input:

• (a) A list of points in the plane.
• (b) A switch to show the ray used

$\displaystyle \mathrm{None}$

Interact: please open in CoCalc