#There is one definite problem and one sort of problem. #The definite problem is that, while your program does draw the convex hull for the points you gave it as default, when I put different numbers in the interactive box for the number of points, I got the same points as in the default case, rather than the number of points I entered. That is, the interactive box did not work. #The sort of problem is that you are not allowing the user to choose the points, but only the number of points, which does not allow the user to try whatever points they want. # Should be fixed now!! - 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) 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;', } 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(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]) 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="margin: 4rem 0;"> <h1>Exercise {}</h1> <p><b>Assignment:</b> {}</p> '''.format(exernum, assignment) if funcs: for func in funcs: res += '<p><b>Function:</b><code style="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>' 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 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 ''' definition() interact(func) 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 # ---========================--- # ''' assignment_defs = { '3.1.1': lambda: html(assignment_html( '3.1.1', 'Take a list of points in the plane and construct the convex hull.' )), '3.2.1': lambda: html(assignment_html( '3.2.1', 'Take a list of points in the plane and construct a convex hull triangulation.' )), '3.3.1': lambda: html(assignment_html( '3.3.1', 'Take a list of points in the plane and construct the triangle splitting triangulation.' )), } # ''' # ---========================--- # End Assignment Defs # -------- # Begin Assignment Methods # ---========================--- # ''' dot = lambda a, b: sum(c*d for c, d in zip(a, b)) def vector_length(v): res = dot(v, v) if res < 0: return math.sqrt(res * -1) return math.sqrt(res) def angle(a, b): theta_inv = dot(a, b) / (vector_length(a) * vector_length(b)) try: return math.acos(theta_inv) except: new_inv = max(min(theta_inv, 1), -1) print('OOPS, tried acos with theta^-1=', theta_inv, 'trying with:', new_inv) return math.acos(new_inv) 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 make_points(n, max_x=300, max_y=300): """ makes a list of random points! each random point is a dictionary with an x and a y """ return [[random.random() * max_x, random.random() * max_y] for _ in range(0, n)] 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): res = [True, False, True] 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 res[-1] elif diff(b, point)[1] >= 0 and diff(a, point)[1] < 0: # if b is above point, and a is below return res[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 res[-1] elif diff(b, point)[0] >= 0 and diff(a, point)[0] < 0: # if b is right of point, and a is left return res[1] return 0 # they're the same point! else: return res[-1 * ccw(point, a, b)] # otherwise, return clockwise def sort_stuff_2(a, b): angleA = -((a[0] - point[0]) / (a[1] - point[1])) angleB = -((b[0] - point[0]) / (b[1] - point[1])) return angleA - angleB < 0 return sort_stuff_2 def insertion_sort(arr, cmp): 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] j = i - 1 while j >= 0 and cmp(curr, arr[j]): arr[j+1] = arr[j] j -= 1 arr[j+1] = curr 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 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 = [] curr, _ = list_bottom_left(points) stack.append(curr) points = sort_by_polar(points, curr) 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 # ''' # ---==========================--- # End Assignment Methods # -------- # Begin Interactive Methods # ---==========================--- # ''' def check_point_on_segment(query_point, a, b): if any([query_point == p for p in [a, b]]): return 0 return 1 if dist(a, query_point) + dist(query_point, b) == dist(a, b) else -1 def triangle_orientation(a, b, c): return ccw(a, b, c), ['colinear', 'positively oriented', 'negatively oriented'][ccw(a, b, c)] def triangle_unsigned_area(a, b, c): s = (dist(a,b) + dist(b,c) + dist(a,c))/2 result = (s*(s-dist(a,b))*(s-dist(b,c))*(s-dist(a,c))) ** 0.5 return abs(result) def triangle_signed_area(a, b, c): s = (dist(a,b) + dist(b,c) + dist(a,c))/2 result = (s*(s-dist(a,b))*(s-dist(b,c))*(s-dist(a,c))) ** 0.5 return result * ccw(a, b, c) def point_eq(a, b): return a[0] == b[0] and a[1] == b[1] def point_in_triangle(query_point, a, b, c): # if query is a vertex, return 0 if any([point_eq(query_point, p) for p in [a, b, c]]): return 0 edges = [[a, b], [b, c], [c, a]] # if query is on an edge, return 2 if any([check_point_on_segment(query_point, *edge) == 1 for edge in edges]): return 2 # if query is inside return 1 (thought this was a cute way to do it c: ) if all([ccw(query_point, *edge) == 1 for edge in edges]): return 1 if all([ccw(query_point, *edge) == -1 for edge in edges]): return 1 # point not in triangle return -1 def interact_convex_hull( points=inputs.box(val=random_points(15, max_val=1000), label="List of vertices"), show_vertices=inputs.switch(label='Show vertices'), show_convex_hull=inputs.switch(label='Show convex hull') ): """ draws a convex hull """ if len(points) < 3: show("Must have at least 3 points") else: point_size = 30 point_color = "blue" hull = make_convex_hull(points) pair = lambda point: (point[0], point[1]) plot_items = [] xoff = sum(map(lambda a: a[0], points)) / len(points) / 40 yoff = sum(map(lambda a: a[1], points)) / len(points) / 40 show_all([ 'List of vertex coordinates: {}'.format(points), 'List of convex hull indices: {}'.format([points.index(p) for p in hull[1:]]), ]) if show_vertices: plot_items += [point(pair(a), rgbcolor=point_color, size=point_size) for a in points] plot_items += [text(i, [points[i][0] + xoff, points[i][1] + yoff] ) for i in range(len(points))] if show_convex_hull: for i, _ in enumerate(hull): plot_items.append(line([pair(hull[i-1]), pair(hull[i])], rgbcolor="red")) if len(plot_items) > 0: show(plot_arr(plot_items), figsize=[5,5]) def interact_convex_hull_triangulation( points=inputs.box(val=random_points(15, max_val=1000), label="List of vertices"), show_vertices=inputs.switch(label='Show vertices'), show_convex_hull=inputs.switch(label='Show convex hull'), show_triangulation=inputs.switch(label='Show convex hull triangulation'), ): """ draws a convex hull """ if len(points) < 3: show("Must have at least 3 points") else: point_size = 30 point_color = "blue" hull = make_convex_hull(points) pair = lambda point: (point[0], point[1]) plot_items = [] xoff = sum(map(lambda a: a[0], points)) / len(points) / 40 yoff = sum(map(lambda a: a[1], points)) / len(points) / 40 show_all([ 'List of vertex coordinates: {}'.format(points), 'List of convex hull indices: {}'.format([points.index(p) for p in hull[1:]]), ]) if show_vertices: plot_items += [point(pair(a), rgbcolor=point_color, size=point_size) for a in points] plot_items += [text(i, [points[i][0] + xoff, points[i][1] + yoff] ) for i in range(len(points))] if show_convex_hull: for i, _ in enumerate(hull): plot_items.append(line([pair(hull[i-1]), pair(hull[i])], rgbcolor="red")) if show_triangulation: for i, _ in enumerate(hull): plot_items.append(line([pair(hull[0]), pair(hull[i])], rgbcolor="blue")) if len(plot_items) > 0: show(plot_arr(plot_items), figsize=[5,5]) def interact_convex_hull_triangle_splitting( points=inputs.box(val=random_points(15, max_val=1000), label="List of vertices"), show_vertices=inputs.switch(label='Show vertices'), show_convex_hull=inputs.switch(label='Show convex hull'), show_triangulation=inputs.switch(label='Show convex hull triangulation'), show_splitting=inputs.switch(label='Show triangle splitting'), ): """ draws a convex hull """ if len(points) < 3: show("Must have at least 3 points") else: point_size = 30 point_color = "blue" hull = make_convex_hull(points) pair = lambda point: (point[0], point[1]) plot_items = [] xoff = sum(map(lambda a: a[0], points)) / len(points) / 40 yoff = sum(map(lambda a: a[1], points)) / len(points) / 40 convex_hull_inds = [points.index(p) for p in hull[1:]] convex_hull_triangles = [] for i in range(len(convex_hull_inds[2:])): convex_hull_triangles.append([convex_hull_inds[0], convex_hull_inds[i+1], convex_hull_inds[i+2]]) in_triangulation = points[:] for p in hull: if p in in_triangulation: in_triangulation.remove(p) def index_to_point(x): res = [] for i in x: try: res.append(points[i]) except: res.append(i) return res tri_splitting_triangulation = convex_hull_triangles[:] for i in range(len(in_triangulation)): for tri in tri_splitting_triangulation[:]: ta, tb, tc = index_to_point(tri) result = point_in_triangle(in_triangulation[i], ta, tb, tc) if result == 1: a, b, c = tri if tri in tri_splitting_triangulation: p = points.index(in_triangulation[i]) tri_splitting_triangulation.remove(tri) tri_splitting_triangulation.append([p, a, b]) tri_splitting_triangulation.append([p, b, c]) tri_splitting_triangulation.append([p, c, a]) break show_all([ 'List of vertex coordinates: {}'.format(points), 'List of convex hull indices: {}'.format(convex_hull_inds), 'List of convex hull triangles: {}'.format(convex_hull_triangles), 'List of triangle splitting triangles: {}'.format(tri_splitting_triangulation) ]) if show_vertices: plot_items += [point(pair(a), rgbcolor=point_color, size=point_size) for a in points] plot_items += [text(i, [points[i][0] + xoff, points[i][1] + yoff] ) for i in range(len(points))] if show_convex_hull: for i, _ in enumerate(hull): plot_items.append(line([pair(hull[i-1]), pair(hull[i])], rgbcolor="red")) if show_triangulation: for i, _ in enumerate(hull): plot_items.append(line([pair(hull[0]), pair(hull[i])], rgbcolor="blue")) if show_splitting: for p in tri_splitting_triangulation: tri = index_to_point(p) plot_items.append(line([tri[0], tri[1]], rgbcolor="blue")) plot_items.append(line([tri[1], tri[2]], rgbcolor="blue")) plot_items.append(line([tri[0], tri[2]], rgbcolor="blue")) if len(plot_items) > 0: show(plot_arr(plot_items), figsize=[5,5]) interactive = { '3.1.1': interact_convex_hull, '3.2.1': interact_convex_hull_triangulation, '3.3.1': interact_convex_hull_triangle_splitting } 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() # [(10, 6), (8, 2), (2, 6), (10, 10), (4, 11), (7, 8), (7, 5), (4, 2), (5, 8), (3, 6)] main()
Exercise 3.3.1
Assignment: Take a list of points in the plane and construct the triangle splitting triangulation.
Interact: please open in CoCalc
Exercise 3.1.1
Assignment: Take a list of points in the plane and construct the convex hull.
Interact: please open in CoCalc
Exercise 3.2.1
Assignment: Take a list of points in the plane and construct a convex hull triangulation.
Interact: please open in CoCalc