# Zerlegen des Polygons
#import import_ipynb
# Voronoi diagramm
import scipy.spatial as spatial
from collections import defaultdict
import random
import numpy
from shapely.geometry import Polygon, MultiPolygon
from .packing_algo import ConvexPolygon, Point_xy, plot_polygons_in_single_plot
def rectangle_cutter(rect_width: float, rect_height: float, cut_count: int, intervals=[0, 0.01, 0.05, 1],
weights=[0, 0, 0.5, 1], render=False,
plot_width=700, plot_height=700) -> [ConvexPolygon]:
if len(intervals) != len(weights):
raise ValueError("the number of values from weights and intervals need to be the same")
rectangle_polygon = ConvexPolygon([(0, 0), (0, rect_height), (rect_width, rect_height), (rect_width, 0), (0, 0)])
max_area = rect_width * rect_height
small_area_polygons = []
polygons_to_cut = [rectangle_polygon]
if cut_count < 0:
raise ValueError("the cut cut_count need to be positive to cut the polygon")
while cut_count > 0 and len(polygons_to_cut) > 0:
cutted_polygons = []
for polygon in polygons_to_cut:
related_area = polygon.area / max_area
weight = find_weight(related_area, intervals, weights)
rand = random.random()
if rand <= weight:
cutted_polygons = cutted_polygons + cut_polygon(polygon)
else:
polygon.plot_fill = True
small_area_polygons.append(polygon)
polygons_to_cut = cutted_polygons
cut_count = cut_count - 1
if render:
current_polygons = polygons_to_cut + small_area_polygons
title = "Rectangle to Polygons=P. cut_count: {} P. count: {} P. to cut: {} P. stopped cutting: {}".format(
cut_count, len(current_polygons), len(polygons_to_cut), len(small_area_polygons))
fig = plot_polygons_in_single_plot(current_polygons, title=title, plot_width=plot_width,
plot_height=plot_height)
all_polygons = polygons_to_cut + small_area_polygons
if render:
for polygon in all_polygons:
polygon.plot_fill = False
return all_polygons
def find_weight(x, intervals, weights):
for index in range(0, len(intervals)):
if x <= intervals[index]:
return weights[index]
def cut_polygon(polygon: ConvexPolygon) -> [ConvexPolygon]:
polygon = polygon.shell # polyog
number_vertices = len(polygon)
if number_vertices < 3:
raise ValueError("Polygon has not enough vertices")
first_edge = numpy.random.randint(1, number_vertices)
second_edge = numpy.random.randint(1, number_vertices)
while first_edge == second_edge:
second_edge = numpy.random.randint(1, number_vertices)
if first_edge > second_edge:
first_edge, second_edge = second_edge, first_edge
vertex_1_first_edge = polygon[first_edge - 1]
vertex_2_first_edge = polygon[first_edge]
vertex_1_second_edge = polygon[second_edge - 1]
vertex_2_second_edge = polygon[second_edge]
new_vertex_1 = random_point_between_edge(vertex_1_first_edge, vertex_2_first_edge)
new_vertex_2 = random_point_between_edge(vertex_1_second_edge, vertex_2_second_edge)
polygon_1 = polygon[:first_edge] + [new_vertex_1] + [new_vertex_2] + polygon[second_edge:]
polygon_2 = [new_vertex_1] + polygon[first_edge:second_edge] + [new_vertex_2] + [new_vertex_1]
# s = [1,2,5,6,7] ,s[6:] => []; daher können wir für den spezial Fall second_edge== vertices_number so vorgehen
return [ConvexPolygon(polygon_1), ConvexPolygon(polygon_2)]
def random_point_between_edge(vertex_1: Point_xy, vertex_2: Point_xy) -> Point_xy:
new_vertex = (0, 0)
if vertex_1[0] == vertex_2[0]:
low, high = vertex_1[1], vertex_2[1]
if low > high:
low, high = high, low
rand_number = numpy.random.uniform(low, high)
new_vertex = (vertex_1[0], rand_number)
elif vertex_1[1] == vertex_2[1]:
low, high = vertex_1[0], vertex_2[0]
if low > high:
low, high = high, low
rand_number = numpy.random.uniform(low, high)
new_vertex = (rand_number, vertex_1[1])
else:
# y = m*x+n
# n = y-m*x
slope = (vertex_1[1] - vertex_2[1]) / (vertex_1[0] - vertex_2[
0]) # m = y2-y1/x2-x1 Formel für die Geradensteigung mithilfe aus zwei verschiedenen Punkten der Geraden
n = vertex_1[1] - (slope * vertex_1[0])
low, high = vertex_1[1], vertex_2[1]
if low > high:
low, high = high, low
rand_number = numpy.random.uniform(low, high)
new_vertex_x = (rand_number - n) / slope # x=(y-n)/m
new_vertex = (new_vertex_x, rand_number)
return new_vertex
# https://gist.github.com/pv/8036995
# https://stackoverflow.com/questions/20515554/colorize-voronoi-diagram/20678647#20678647
def voronoi_polygons_wrapper(rect_width, rect_height, point_count):
boundary = numpy.array([[0, 0], [0, rect_height], [rect_width, rect_height], [rect_width, 0], [0, 0]])
boundary_polygon = Polygon(boundary)
x_values = numpy.random.uniform(low=0 + 1, high=rect_width - 1, size=(point_count,))
y_values = numpy.random.uniform(low=0 + 1, high=rect_height - 1, size=(point_count,))
points = list(zip(x_values, y_values))
bigger = max(rect_width, rect_height)
pre_number = pre_decimal_finder(bigger) + 3
border_point = int(str(9) * pre_number)
help_border = [[border_point, border_point], [-border_point, border_point], [border_point, -border_point],
[-border_point, -border_point]]
points = numpy.append(points, help_border, axis=0)
# compute Voronoi tesselation
vor = spatial.Voronoi(points)
polygon_list = []
for region in vor.regions:
if not -1 in region:
polygon = [vor.vertices[i] for i in region]
if len(polygon) > 2:
# Clipping polygon
poly = Polygon(polygon)
clipped_poly = poly.intersection(boundary_polygon)
polygon_list.append(ConvexPolygon(clipped_poly.exterior.coords))
return polygon_list
def pre_decimal_finder(i: float) -> int:
if i < 0:
i = abs(i)
counter = 0
while i != 0:
i = i // 10
counter += 1
return counter