Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Rotating Convex Hulls solution in Clear category for Inscribe a Contour by JamesArruda
"""
Procedure:
1. Graham scan algorithm to find the convex hull
2. For each edge in the hull:
a. Rotate that edge to be straight along the x-axis
b. Get the area of the hull's rectangle
3. Return the smallest of those
"""
from math import pi, atan2, sin, cos
def angle(point_a, point_b):
"""Return the angle of point b relative to point a
"""
rise = point_b[1] - point_a[1]
run = point_b[0] - point_a[0]
return atan2(rise, run)
def ccw(a, b, c):
"""Whether or not the sequence of points a->b-> is a counter-clockwise turn
"""
x1, y1 = a
x2, y2 = b
x3, y3 = c
return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) >= 0
def rotate(origin, angle, point):
"""Rotate a point by some angle around an origin
"""
x = point[0] - origin[0]
y = point[1] - origin[1]
new_x = x * cos(angle) - y * sin(angle)
new_y = x * sin(angle) + y * cos(angle)
return (new_x + origin[0], new_y+origin[1])
def make_hull(points):
# sort points by lowest y, then left-most
min_point = min(points, key=lambda x: (x[1], x[0]))
# get angles of rotation from the lowest-left point
angles = [(angle(min_point, pt), pt) for pt in points if pt != min_point]
angles = sorted(angles)
stack = [min_point]
for _, point in angles:
while len(stack) > 1 and ccw(stack[-2], stack[-1], point) <= 0:
stack.pop()
stack.append(point)
hull = list(stack) + [stack[0]]
return hull
def area_from_edge(edge_index, hull):
"""Get the area of a rectangle surrounding a hull along a given edge.
"""
pt_1 = hull[edge_index]
pt_2 = hull[edge_index+1]
ang = angle(pt_1, pt_2)
min_x, max_x, min_y, max_y = float('inf'), 0, float('inf'), 0
for pt in hull:
x, y = rotate(pt_1, -ang, pt)
max_x = max(x, max_x)
min_x = min(x, min_x)
min_y = min(y, min_y)
max_y = max(y, max_y)
area = (max_x - min_x) * (max_y - min_y)
return area
def inscribe(contour):
hull = make_hull(contour)
best_area = min(
[
area_from_edge(edge_index, hull)
for edge_index in range(len(hull)-1)
]
)
return round(best_area, 3)
Dec. 2, 2019
Comments:
