assignment_07.sagews

#The program mostly works well, but there a few things that are not working exactly right.

#1) When I tried the polygon [[4.0, 0], [4, 2], [8, 2], [6, 1], [7, 4]] it worked fine, but when I tried [[4, 0], [4, 2], [8, 2], [6, 1], [7, 4]] it said "invalid polyon."  Why did your program not like whole number coordinates?

# - This should work for floats because of the way Python handles floating point arithmetic, although, the int variant fails since we get a vertical line. Is there something else we should be doing for vertical lines? - Cole

#2) When I tried the polygon [[4.0, 0], [4, 2], [8, 2], [6, 1], [7, 4]] with the test point [7, 4], it said "The point is in the interior of an edge of the polygon," which is not correct.  On the other hand, when I tried the same polygon with test point [8, 2], it correctly said "The point is a vertex of the polygon."  What's the difference between the two cases?

# - This is interesting! I was checking for the point in question to be a vertex or in the interior of an edge in the same loop, and the latter was happening first for the last item in the list (because of negative indexing).
#	for i, point in enumerate(arr):
#            if arr[i] == querypoint: return 0, 0
#            if point_on_line(querypoint, arr[i-1], arr[i]): return 2, 0 # this one will trigger first if arr[-1] == querypoint!!!!
# - It’s a pretty simple fix though, just run the loop twice instead - cole

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)
    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


# 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.5.1
assignment_defs = {
    '2.5.1': lambda: html(assignment_html(
        '2.5.1',
        'Make a function that takes a list of points in the plane and an additional point, and determines whether the point is inside, outside or on the polygon with vertices in the list, and plot the polygon and the additional point.',
        funcs=[{
            'name': 'point_in_polygon(querypoint, 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']
    )),
}


# '''
# ---========================---
#    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 arr[i] == querypoint: return 0, 0
        for i, point in enumerate(arr):
            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

# '''
# ---==========================---
#    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))


interactive = {
    '2.5.1': interact_point_in_polygon,
}

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.5.1

Assignment: Make a function that takes a list of points in the plane and an additional point, and determines whether the point is inside, outside or on the polygon with vertices in the list, and plot the polygon and the additional point.

Function:point_in_polygon(querypoint, 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