98 lines
3.0 KiB
Python
98 lines
3.0 KiB
Python
def point_inside_polygon(x, y, points):
|
|
n = len(points)
|
|
inside = False
|
|
|
|
# this does a raytracing algorithm that I don't quite understand.
|
|
# See http://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon/2922778#2922778
|
|
# for an attempt at an explanation
|
|
|
|
p1x, p1y = points[0]
|
|
for i in range(n + 1):
|
|
p2x, p2y = points[i % n]
|
|
if y > min(p1y, p2y):
|
|
if y <= max(p1y, p2y):
|
|
if x <= max(p1x, p2x):
|
|
if p1y != p2y:
|
|
xinters = (y - p1y) * (p2x - p1x) / (p2y - p1y) + p1x
|
|
if p1x == p2x or x <= xinters:
|
|
inside = not inside
|
|
p1x, p1y = p2x, p2y
|
|
|
|
return inside
|
|
|
|
def line_segments_intersect(first_line, second_line):
|
|
# returns either None or the point where the line segments intersect
|
|
x_0_0 = first_line[0][0]
|
|
x_0_1 = first_line[1][0]
|
|
y_0_0 = first_line[0][1]
|
|
y_0_1 = first_line[1][1]
|
|
|
|
x_1_0 = second_line[0][0]
|
|
x_1_1 = second_line[1][0]
|
|
y_1_0 = second_line[0][1]
|
|
y_1_1 = second_line[1][1]
|
|
|
|
if max(x_0_0, x_0_1) < min(x_1_0, x_1_1):
|
|
return None
|
|
|
|
rise_0 = y_0_1 - y_0_0
|
|
run_0 = x_0_1 - x_0_0
|
|
if run_0 == 0:
|
|
slope_0 = None
|
|
y_intercept_0 = 0
|
|
else:
|
|
slope_0 = rise_0 / run_0
|
|
y_intercept_0 = y_0_0 - (slope_0 * x_0_0)
|
|
|
|
rise_1 = y_1_1 - y_1_0
|
|
run_1 = x_1_1 - x_1_0
|
|
if run_1 == 0:
|
|
slope_1 = None
|
|
y_intercept_1 = 0
|
|
else:
|
|
slope_1 = rise_1 / run_1
|
|
y_intercept_1 = y_1_0 - (slope_1 * x_1_0)
|
|
|
|
if slope_0 is not None and slope_1 is not None and abs(slope_0 - slope_1) < 1e-3:
|
|
return None
|
|
if slope_0 is None and slope_1 is None:
|
|
return None
|
|
if slope_0 is None:
|
|
x_point = x_0_0
|
|
slope = slope_1
|
|
elif slope_1 is None:
|
|
x_point = x_1_0
|
|
slope = slope_0
|
|
else:
|
|
x_point = (y_intercept_1 - y_intercept_0) / (slope_0 - slope_1)
|
|
slope = slope_0
|
|
|
|
if (x_point < max(min(x_0_0, x_0_1), min(x_1_0, x_1_1))) and (x_point > min(max(x_0_0, x_0_1), max(x_1_0, x_1_1))):
|
|
return None
|
|
|
|
y_point = slope * x_point + y_intercept_1
|
|
return x_point, y_point
|
|
|
|
|
|
def clip_polygon(a, clip_region):
|
|
points = []
|
|
for x, y in a:
|
|
points.append((x, y, point_inside_polygon(x, y, clip_region)))
|
|
|
|
idx = 0
|
|
while idx < len(points):
|
|
x0, y0, inside_0 = points[(idx-1) % len(points)]
|
|
x1, y1, inside_1 = points[idx]
|
|
|
|
first_line = [(x0, y0), (x1, y1)]
|
|
|
|
if inside_0 and not inside_1: # intersected between then and now
|
|
for index, vertex in enumerate(clip_region):
|
|
second_line = [vertex, clip_region[(index + 1) % len(clip_region)]]
|
|
intersection = line_segments_intersect(first_line, second_line)
|
|
if intersection:
|
|
points[idx] = (intersection[0], intersection[1], False)
|
|
break
|
|
idx += 1
|
|
return [(x, y) for x, y, _ in points]
|