 CoCalc Public FilesAssignment #1 trial / Assignment 1 trial / assignment_05.sagews
Authors: Ethan Bloch, Cole Hollant
Views : 107
#All the programs are good.

#Out of curiosity, in Exercise 2.3.1, what you did works perfectly, but I wanted to ask why you used one formula for the signed area of a triangle in one place, namely area2 = (b - a) * (c - a) - (b - a) * (c - a), which more precisely is twice the area, and then you used a different formula for the area of a triangle in another place, namely s = (dist(a,b) + dist(b,c) + dist(a,c))/2 and return = (s*(s-dist(a,b))*(s-dist(b,c))*(s-dist(a,c))) ** 0.5.  It's sufficient to use the formula area2, divide it by 2, and then use that result for both orientation and signed area, and take the absolute value for unsigned area.  What you did works, but is more complicated than necessary.

# - I must say, this is just a lack of thinking on my part! I had used CCW for something else beforehand and didn’t think much about what actually went on in the implementation (the area2 = (b - a) * (c - a) - (b - a) * (c - a) bit). The area through 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 is what I’m used to using for the area of a triangle (some version of it is on page 30 of my little python textbook I sent you a while back!). - 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;',
'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 prefix, rule_list in spacing_opts.items():
classes[variant + 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
for el in arr:
if cmp_helper(el, res):
res = el
return res

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

random_points = lambda n, min_val=0, max_val=10: [(random.randint(min_val, max_val), random.randint(min_val, max_val)) for _ in range(n)]

def ccw(a, b, c):
"""
determines if three points are clockwise, counterclockwise, or colinear
"""
area2 = (b - a) * (c - a) - (b - a) * (c - a)
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.1, a + 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

class inputs:
def __init__(self):
pass

@staticmethod
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='number', min_val=-10, max_val=10):
if not num:
num = random.randint(min_val, max_val)
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 = {
'2.2.1': lambda: html(assignment_html(
'2.2.1',
'Make a function that takes two points in the plane and an additional point, and determines whether the additional point is in the line segment with the first two points as endpoints, and plot the line segment and the additional point.',
funcs=[{
'name': 'check_point_on_segment(query_point, a, b)',
'params': [
'query_point: tuple representing point (x, y)',
'a: tuple representing segment endpoint (x, y)',
'b: tuple representing segment endpoint (x, y)',
],
'returns': ['1 if query_point is on ab, 0 if query_point = a or b, -1 if not on segment']
}],
params=[
'(a) A list of two points in the plane.',
'(b) An additional point in the plane.',
]
)),
'2.3.1': lambda: html(assignment_html(
'2.3.1',
'Make three functions that take three points in the plane and find the signed area, the unsigned area and the orientation of the triangle with those vertices, and plot the triangle showing the orientation.',
funcs=[{
'name': 'triangle_signed_area(a, b, c)',
'params': ['a, b, c: tuples representing vertices (x, y)'],
'returns': ['signed area of triangle']
},{
'name': 'triangle_absolute_area(a, b, c)',
'params': ['a, b, c: tuples representing vertices (x, y)'],
'returns': ['absolute area of triangle']
},{
'name': 'triangle_orientation(a, b, c)',
'params': ['a, b, c: tuples representing vertices (x, y)'],
'returns': ['1 if triangle is oriented ccw, 0 if colinear, -1 if cw']
}],
params=['(a) A list of three points in the plane.']
)),
'2.3.2': lambda: html(assignment_html(
'2.3.2',
'Make a function that takes three points in the plane and an additional point, and determines whether the additional point is in the triangle with the first three points as vertices, and plot the triangle and the additional point.',
funcs=[{
'name': 'point_in_triangle(query_point, a, b, c)',
'params': [
'a, b, c: tuples representing vertices (x, y)'
'query_point: tuples representing test point (x, y)'
],
'returns': [
'-1: query_point not in triangle',
'0: query_point on triangle vertex',
'1: query_point in triangle',
'2: query_point on triangle edge',
]
}],
params=[
'(a) A list of three points in the plane.',
'(b) An additional point in the plane.'
]
)),
}

# '''
# ---========================---

#    End Assignment Defs

#      --------

#    Begin Assignment 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)

point_eq = lambda a, b: a == b and a == b

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

# '''
# ---==========================---

#    End Assignment Methods

#      --------

#    Begin Interactive Methods

# ---==========================---
# '''

def interact_check_point_on_segment(
endpoints=inputs.box(val=random_points(2), label='endpoints'),
query_point=inputs.box(val=random_points(1), label='query point')
):
if len(endpoints) < 2:
return html('<strong>Not enough points</strong>')
res = [
line([endpoints, endpoints], rgbcolor='red'),
point(query_point, rgbcolor='blue', size=30)
]
show(plot_arr(res), figsize=[5,5])
show(['Is endpoint', 'On segment', 'Not on line'][check_point_on_segment(query_point, *endpoints[0:2])])

def interact_triangle_areas(vertices=inputs.box(val=random_points(3), label='list of three vertices')):
show_all([
'List: {}'.format(vertices),
'Signed area: {}'.format(triangle_signed_area(*vertices[0:3])),
'Unsigned area: {}'.format(triangle_unsigned_area(*vertices[0:3])),
'The triangle is {}'.format(triangle_orientation(*vertices[0:3])),
])
draw_polygon(vertices[0:3], arrows=True, plot=True)

def interact_point_in_triangle(
vertices=inputs.box(val=random_points(3), label='Triangle vertices'),
query_point=inputs.box(val=random_points(1), label='query point')
):
show([
'query_point on triangle vertex',
'query_point in triangle',
'query_point on triangle edge',
'query_point not in triangle'
][point_in_triangle(query_point, *vertices[0:3])])
res = draw_polygon(vertices[0:3])
res += [point(query_point, rgbcolor='blue', size=30)]
show(plot_arr(res), figsize=[5,5])

interactive = {
'2.2.1': interact_check_point_on_segment,
'2.3.1': interact_triangle_areas,
'2.3.2': interact_point_in_triangle
}

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

Assignment: Make three functions that take three points in the plane and find the signed area, the unsigned area and the orientation of the triangle with those vertices, and plot the triangle showing the orientation.

Function:triangle_signed_area(a, b, c)

params:
• a, b, c: tuples representing vertices (x, y)
returns:
• signed area of triangle

Function:triangle_absolute_area(a, b, c)

params:
• a, b, c: tuples representing vertices (x, y)
returns:
• absolute area of triangle

Function:triangle_orientation(a, b, c)

params:
• a, b, c: tuples representing vertices (x, y)
returns:
• 1 if triangle is oriented ccw, 0 if colinear, -1 if cw

Interactive input:

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

# Exercise 2.3.2

Assignment: Make a function that takes three points in the plane and an additional point, and determines whether the additional point is in the triangle with the first three points as vertices, and plot the triangle and the additional point.

Function:point_in_triangle(query_point, a, b, c)

params:
• a, b, c: tuples representing vertices (x, y)query_point: tuples representing test point (x, y)
returns:
• -1: query_point not in triangle
• 0: query_point on triangle vertex
• 1: query_point in triangle
• 2: query_point on triangle edge

Interactive input:

• (a) A list of three points in the plane.
• (b) An additional point in the plane.

# Exercise 2.2.1

Assignment: Make a function that takes two points in the plane and an additional point, and determines whether the additional point is in the line segment with the first two points as endpoints, and plot the line segment and the additional point.

Function:check_point_on_segment(query_point, a, b)

params:
• query_point: tuple representing point (x, y)
• a: tuple representing segment endpoint (x, y)
• b: tuple representing segment endpoint (x, y)
returns:
• 1 if query_point is on ab, 0 if query_point = a or b, -1 if not on segment

Interactive input:

• (a) A list of two points in the plane.
• (b) An additional point in the plane.