import sys, path
import copy
import numpy
import math
import random
from collections import defaultdict
import itertools
# from typing import NewType
# for JupyterLab
#import import_ipynb
# tree datastructure
from . import avl_tree
# shapely/polygon packages
from shapely.geometry import MultiPolygon, Polygon, LineString, LinearRing, Point
from shapely.geometry.base import BaseGeometry, geos_geom_from_py
from shapely import affinity
# plotting packages
import mpld3
import bokeh
from bokeh.plotting import figure, Figure
from bokeh.io import output_notebook, show
from bokeh.layouts import gridplot, row, layout, column, Column
from bokeh.models import Div
from bokeh.models import Legend
from bokeh.models import BoxAnnotation
from bokeh.models.widgets import Tabs, Panel
from bokeh.models import ColumnDataSource, Label, LabelSet, Range1d
from bokeh.palettes import Dark2_5 as palette
from bokeh.plotting import output_file
# for analysing the data
import pandas as pd
# Type aliases for the type hints
Point_xy = (float, float)
class ConvexPolygon(object):
def __init__(self, shell: [Point_xy]) -> None:
self.__shell, self.__area = self.convex_hull_and_area(shell)
self.__x_values = [vertex[0] for vertex in self.shell]
self.__y_values = [vertex[1] for vertex in self.shell]
self.__min_x = min(self.__x_values)
self.__max_x = max(self.__x_values)
self.__min_y = min(self.__y_values)
self.__max_y = max(self.__y_values)
self.__height = self.__max_y - self.__min_y
self.__width = self.__max_x - self.__min_x
self.__spine = self.set_spine()
self.__vertices_left_visible, self.__vertices_right_visible = self.splitter()
self.__slope = self.set_slope()
self.plot_fill = False
@property
def area(self):
return self.__area
@property
def shell(self):
return self.__shell
@property
def min_x(self):
return self.__min_x
@property
def max_x(self):
return self.__max_x
@property
def min_y(self):
return self.__min_y
@property
def max_y(self):
return self.__max_y
@property
def x_values(self):
return self.__x_values
@property
def y_values(self):
return self.__y_values
@property
def height(self):
return self.__height
@property
def width(self):
return self.__width
@property
def spine(self):
return self.__spine
@property
def vertices_left_visible(self):
return self.__vertices_left_visible
@property
def vertices_right_visible(self):
return self.__vertices_right_visible
@property
def slope(self):
return self.__slope
# @property
# def plot_fill(self):
# return self.__plot_fill
def convex_hull_and_area(self, shell: [Point_xy]) -> [Point_xy]:
# the Polygon points will be ordered clockweise and the start and end point are connected
if shell == None:
raise ValueError("a convex polygon can't intialized with None")
elif shell == [] or len(shell) < 3:
raise ValueError("a convex polygon needs at least 3 points")
shapely_polygon = Polygon(shell)
convex_polygon = shapely_polygon.convex_hull
if type(convex_polygon) is not Polygon:
raise ValueError(
"couldn't create the convex Polygon, to less points after using the convex hull on the input points")
shell = list(convex_polygon.exterior.coords)
area = convex_polygon.area
return (shell, area)
def translation(self, x: float, y: float) -> None:
self.__shell = [(point[0] + x, point[1] + y) for point in self.__shell]
self.__spine = (
(self.__spine[0][0] + x, self.__spine[0][1] + y), (self.__spine[1][0] + x, self.__spine[1][1] + y))
self.__vertices_left_visible = [(point[0] + x, point[1] + y) for point in self.__vertices_left_visible]
self.__vertices_right_visible = [(point[0] + x, point[1] + y) for point in self.__vertices_right_visible]
self.__min_x = self.__min_x + x
self.__max_x = self.__max_x + x
self.__min_y = self.__min_y + y
self.__max_y = self.__max_y + y
self.__x_values = [vertex + x for vertex in self.__x_values]
self.__y_values = [vertex + y for vertex in self.__y_values]
def set_spine(self) -> (Point_xy,
Point_xy): # für den spine spielt es keine Rolle in welche Rolle das Polygon aufgebaut ist ob im Uhrzeigersinn oder dagegen
y_sorted_p_p = sorted(self.__shell, key=lambda k: k[
1]) # Parser schreibt oder davon ausgeht das konvexe Polygone übergeben werden
if y_sorted_p_p[0][1] == y_sorted_p_p[1][
1]: # falls der niedrige Puntk eine wagerechte ist nehme die linke Ecke
if y_sorted_p_p[0][0] < y_sorted_p_p[1][0]:
spine_bottom = y_sorted_p_p[0]
else:
spine_bottom = y_sorted_p_p[1]
else:
spine_bottom = y_sorted_p_p[0]
if y_sorted_p_p[-2][1] == y_sorted_p_p[-1][
1]: # falls der höchste Punkt eine wagerechte ist nehme die rechte Ecke
if y_sorted_p_p[-2][0] < y_sorted_p_p[-1][0]:
spine_top = y_sorted_p_p[-1]
else:
spine_top = y_sorted_p_p[-2]
else:
spine_top = y_sorted_p_p[-1]
return (spine_bottom, spine_top)
def set_slope(self) -> float:
spine = self.__spine
if spine[0][0] == spine[1][0]: # Sonderfall für eine senkrechte
slope = math.inf
else:
slope = (spine[1][1] - spine[0][1]) / (spine[1][0] - spine[0][
0]) # m = y2-y1/x2-x1 Formel für die Geradensteigung mithilfe aus zwei verschiedenen Punkten der Geraden
return slope
def plot_polygon(self, title="", plot_width=400, plot_height=300, color="#1F77B4", render=True) -> Figure:
"""Plotting a Polygon with bokeh"""
legend_items = []
height = (int(self.__height * 10)) / 10
if self.__slope == math.inf:
slope = math.inf
else:
slope = truncate(self.__slope, 1)
x_data = self.__x_values
y_data = self.__y_values
TOOLTIPS = [("index", "$index"), ("(x,y)", "($x{0.0}, $y{0.0})"), ]
if title == "":
title = 'height: {} slope: {}'.format(height, slope)
else:
title = '{} height: {} slope: {}'.format(title, height, slope)
fig = figure(title=title, x_axis_label='x', y_axis_label='y', width=plot_width, height=plot_height,
tooltips=TOOLTIPS, )
if self.plot_fill:
poly_fig = fig.patch(x_data, y_data, line_width=1, color=color, alpha=0.9, line_alpha=1, muted_alpha=0.05)
else:
poly_fig = fig.patch(x_data, y_data, line_width=1, alpha=0.1, color=color, line_alpha=1, muted_alpha=0.05)
fig_points = fig.circle(x_data, y_data, color=color, line_width=1, muted_alpha=0.02, size=4)
legend_items.append(("shell-lines", [poly_fig]))
legend_items.append(("vertices", [fig_points]))
spine_x_values = [x[0] for x in self.__spine]
spine_y_values = [x[1] for x in self.__spine]
fig_spine = fig.line(spine_x_values, spine_y_values, line_color="red", line_width=1, muted_alpha=0.2,
muted_color="red")
legend_items.append(("spine", [fig_spine]))
legend = Legend(items=legend_items)
legend.click_policy = "mute"
fig.add_layout(legend, 'right')
if render:
show(fig)
return fig
def splitter(self) -> ([Point_xy], [Point_xy]):
left = []
right = []
spine_bottom = self.__spine[0]
spine_top = self.__spine[1]
help_array = self.__shell[:]
if help_array[0] == help_array[-1]: # falls letztes element doppelt
help_array = help_array[0:-1]
spine_bottom_found = False
spine_top_found = False
spine_bottom_not_horizontal = False
while spine_bottom_found == False: # Phase 1 der Funktion sie sucht den bottom spine, dabei werden die Ecken die nicht der Spine Bottom sind ans Ende der Liste geschoben
if help_array[0] == spine_bottom:
if spine_bottom[1] != help_array[-1][
1]: # checkt ob Spine bottom ein horizontalen Nachbar hat falls ja wird ein Flag gesetzt damit Spine bottomt später nicht in die Rechte mitgenommen wird
spine_bottom_not_horizontal = True
spine_bottom_found = True
left.append(help_array.pop(0))
else:
help_array.append(help_array.pop(0))
while spine_top_found == False: # iterieren die Liste erneut durch bis wir spine top finden, falls spine top gefunden wurde wird auch geschaut ob spine top ein horizontalen linken
if help_array[0] == spine_top: # Nachbar hat falls ja wird spine top nicht in die Linke Liste miteingefügt
spine_top_found = True
if spine_top[1] != left[-1][1]:
left.append(spine_top)
else:
left.append(help_array.pop(0))
right = help_array.copy()
if spine_bottom_not_horizontal:
right.append(spine_bottom)
return (left, right)
class HighClass(object):
def __init__(self, i: int, alpha: float, h_max_polygon: float, w_max_polygon: float) -> None:
self.i = i
self.alpha = alpha
self.h_max_polygon = h_max_polygon
self.w_max_polygon = w_max_polygon
self.min_border = alpha ** (i + 1) * h_max_polygon
self.max_border = alpha ** (i) * h_max_polygon
self.polygons = []
self.spine_ordered_polygons = []
def set_polygons(self, polygons: [ConvexPolygon]) -> None:
self.polygons = polygons
spine_ordered_polygons = sorted(self.polygons, key=lambda polygon: polygon.slope)
self.spine_ordered_polygons = spine_ordered_polygons
def plot_hc(self, ordered=False, render=True, plot_width=300, plot_height=300) -> Column:
plots = []
if ordered:
polygon_list = self.spine_ordered_polygons
else:
polygon_list = self.polygons
for counter, polygon in enumerate(polygon_list):
title = "Polygon {}".format(counter)
plots.append(polygon.plot_polygon(title=title, render=False))
grid = gridplot(plots, ncols=4, plot_width=plot_width, plot_height=plot_height, toolbar_location="left")
grid_title = Div(text="<b>Hc_{} height: {}-{} alpha: {}<b>".format(self.i, truncate(
self.min_border, 1), truncate(self.max_border, 1), self.alpha))
grid_layout = column(grid_title, grid)
if render:
show(grid_layout)
return grid_layout
class Container(object):
def __init__(self, hc: HighClass) -> None:
self.hc = hc # am ende nur zuweiseung ohne copy
self.y_boundary = self.hc.max_border
self.x_boundary = 0
self.Tree = avl_tree.AVLTree()
self.root = None
self.sigma, self.plot_steps = self.packing_container(self.hc.spine_ordered_polygons)
def distance(self, edge_points: (Point_xy, Point_xy), point: Point_xy) -> float:
# y = m*x+n
# (y-n)/m=x
# n = y-m*x
edge_p1 = edge_points[0]
edge_p2 = edge_points[1]
if edge_p1[0] == edge_p2[0]: # Sonderfall für eine senkrechte
distance = math.sqrt((edge_p1[0] - point[
0]) ** 2) # da der edge_points eine senkrechte ist -> der eintreffpunkt hat den gleichen y wert wie der punkt, in der Abstand formel fällt dieser wert weg
elif edge_p1[1] == point[1]:
distance = math.sqrt((edge_p1[0] - point[0]) ** 2 + (edge_p1[1] - point[1]) ** 2)
else:
slope = (edge_p2[1] - edge_p1[1]) / (edge_p2[0] - edge_p1[
0]) # m = y2-y1/x2-x1 Formel für die Geradensteigung mithilfe aus zwei verschiedenen Punkten der Geraden
n = edge_p1[1] - (slope * edge_p1[0])
intersection_point_x = (point[1] - n) / slope # x=(y-n)/m
intersection_point = (intersection_point_x, point[1])
distance = math.sqrt((intersection_point[0] - point[0]) ** 2 + (intersection_point[1] - point[1]) ** 2)
return distance
def find_successor(self, vertex: Point_xy, vertices_visible_left: [Point_xy]) -> (Point_xy, Point_xy):
for counter, top_edge_vertex in enumerate(vertices_visible_left):
if top_edge_vertex[1] >= vertex[1]:
bottom_edge_vertex = vertices_visible_left[counter - 1]
return (bottom_edge_vertex, top_edge_vertex)
def packing_container(self, hc_spine_ordered_polygons: [ConvexPolygon]) -> ([ConvexPolygon], [Figure]):
hc_polygons = copy.deepcopy(hc_spine_ordered_polygons) # n
sigma_plot_helper = [] # holds the Polygons before their translation to next polygon in sigma
step_counter = 0
sigma = []
plot_steps = []
for polygon in hc_polygons:
sigma_plot_helper.append(polygon)
if sigma == []:
transform_x = -polygon.min_x
transform_y = -polygon.min_y
polygon.translation(transform_x, transform_y)
polygon_vertices = len(polygon.vertices_right_visible)
# filling the tree with all vertices visible form right of the first polygon
for count in range(0, polygon_vertices - 1):
vertice = polygon.vertices_right_visible[count]
vertice_neighbour = polygon.vertices_right_visible[count + 1]
self.root = self.Tree.insert_node(self.root, vertice[1], vertice, vertice_neighbour)
sigma.append(polygon)
self.x_boundary += polygon.width
plot_steps.append(
self.plot_container(sigma_plot_helper, render=False, title="Step {}".format(step_counter)))
step_counter += 1
else:
transform_x = (self.x_boundary + abs(polygon.min_x)) + 10
transform_y = -polygon.min_y
polygon.translation(transform_x, transform_y)
min_horizontal_distance = math.inf
distance_rl_plot_helper = []
# distanzen von rechts nach links
for vertex in polygon.vertices_left_visible:
vertex_y = vertex[1]
successor_vertex = self.Tree.find_edges(self.root, vertex_y, self.root)
corresponding_edge_points = (successor_vertex.vertice, successor_vertex.vertice_neighbour)
distance = self.distance(corresponding_edge_points, vertex)
if distance <= min_horizontal_distance:
min_horizontal_distance = distance
distance_rl_plot_helper.append((vertex, distance))
key = polygon.spine[1][1]
tree_array = self.Tree.preOrder_array((self.root), [],
key) # alle Ecken bis zum höchsten Punkt von dem neuen Polygon
distance_lr_plot_helper = []
# distanzen von links nach rechts
for vertex in tree_array:
successor = self.find_successor(vertex, polygon.vertices_left_visible)
distance = self.distance(successor, vertex)
if distance <= min_horizontal_distance:
min_horizontal_distance = distance
self.root = self.Tree.delete_node(self.root, vertex[1]) # deleting vertices from B
distance_lr_plot_helper.append((vertex, distance))
plot_steps.append(
self.plot_container(sigma_plot_helper, distance_rl_plot_helper, distance_lr_plot_helper,
min_horizontal_distance, render=False, title="Step {}".format(step_counter)))
step_counter += 1
polygon.translation(-(min_horizontal_distance), 0)
for counter, vertex in enumerate(polygon.vertices_right_visible[0:-1]):
self.root = self.Tree.insert_node(self.root, vertex[1], vertex,
(polygon.vertices_right_visible[counter + 1]))
x_boundary = max([vertex[0] for vertex in polygon.vertices_right_visible] + [self.x_boundary])
self.x_boundary = x_boundary
sigma.append(polygon)
plot_steps.append(self.plot_container(sigma, render=False, title="Finished Container"))
return (sigma, plot_steps)
def plot_container(self, sigma=None, r_l_distances=None, l_r_distances=None, min_distance=None, render=True,
title="", box_boundarys_x_values_colors_tuple=None) -> Figure:
# sigma als argument statt self.sigma dient dazu auch zwischen schritte plotten zu lassen
legend_items = []
legend_polygons = []
legend_spine = []
legend_lr = []
legend_rl = []
legend_vertices = []
if sigma == None:
sigma = self.sigma
TOOLTIPS = [("index", "$index"), ("(x,y)", "($x{0.0}, $y{0.0})"), ]
fig = figure(title=title, x_axis_label='x', y_axis_label='y', tooltips=TOOLTIPS, toolbar_location="left")
for counter, polygon in enumerate(sigma):
x_values = polygon.x_values
y_values = polygon.y_values
poly_fig = fig.patch(x_values, y_values, line_width=1, alpha=0.1, muted_alpha=0.05, line_alpha=1)
circle_fig = fig.circle(x_values, y_values, line_width=1, muted_alpha=0.01)
legend_label = "Polygon{}".format(counter)
legend_polygons.append((legend_label, [poly_fig]))
legend_vertices.append(circle_fig)
x_spine = [x[0] for x in polygon.spine]
y_spine = [y[1] for y in polygon.spine]
spine_fig = fig.line(x_spine, y_spine, line_color="red", line_width=1, alpha=0.01, muted_color="red",
muted_alpha=1)
legend_spine.append(spine_fig)
if box_boundarys_x_values_colors_tuple != None:
box_boundarys_x_values = box_boundarys_x_values_colors_tuple[0]
background_c_list = box_boundarys_x_values_colors_tuple[1]
for counter, boundary in enumerate(box_boundarys_x_values[0:-1]):
next_boundary = box_boundarys_x_values[counter + 1]
color_box = BoxAnnotation(bottom=0, top=self.y_boundary, left=box_boundarys_x_values[counter],
right=next_boundary, fill_color=background_c_list[counter], fill_alpha=0.1)
fig.add_layout(color_box)
fig.line([next_boundary, next_boundary], [0, self.y_boundary], line_dash="dotted")
fig.title.text = 'Hc-Container{} height: {} -> Mini Containers'.format(self.hc.i,
truncate(self.y_boundary, 1))
if title == "":
fig.title.text = 'Hc-Container{} height: {} '.format(self.hc.i, truncate(self.y_boundary, 1))
if r_l_distances != None:
for vertex_distance_tuple in r_l_distances:
vertex_r = vertex_distance_tuple[0]
distance = vertex_distance_tuple[1]
x = vertex_r[0]
corresponding_point_x = x - distance
y = vertex_r[1]
text_point_x, text_point_y = (x - distance / 2, y)
distance_int = int(distance)
color = "blue"
if distance_int == int(min_distance):
line_dash = "solid"
else:
line_dash = "dotted"
fig_rl = fig.line([vertex_r[0], corresponding_point_x], [y, y], line_color=color, line_width=1,
muted_alpha=0.2, line_dash=line_dash)
source = ColumnDataSource(data=dict(x=[vertex_r[0] - (distance / 2)], y=[y], names=[distance_int]))
labels = LabelSet(x='x', y='y', text='names', level='glyph', x_offset=0, y_offset=0, source=source,
render_mode='canvas')
fig.add_layout(labels)
legend_rl.append(fig_rl)
if l_r_distances != None:
for vertex_distance_tuple in l_r_distances:
vertex_l = vertex_distance_tuple[0]
distance = vertex_distance_tuple[1]
x = vertex_l[0]
corresponding_point_x = x + distance
y = vertex_l[1]
text_point_x, text_point_y = (x + distance / 2, y)
distance_int = int(distance)
color = "green"
if distance_int == int(min_distance):
line_dash = 'solid'
else:
line_dash = "dotted"
fig_lr = fig.line([vertex_l[0], corresponding_point_x], [y, y], line_color=color, line_width=1,
muted_alpha=0.2, line_dash=line_dash)
source = ColumnDataSource(data=dict(x=[vertex_l[0] + (distance / 2)], y=[y], names=[distance_int]))
labels = LabelSet(x='x', y='y', text='names', level='glyph', x_offset=0, y_offset=0, source=source,
render_mode='canvas')
fig.add_layout(labels)
legend_lr.append(fig_lr)
# building the custom legend
fig_boundary = fig.line([0, self.x_boundary, self.x_boundary, 0, 0],
[0, 0, self.y_boundary, self.y_boundary, 0], line_color="black", alpha=0.7,
line_width=1, muted_alpha=0.2, )
legend_items.append(("spine", legend_spine))
if l_r_distances != None:
legend_items.append(("distance-lr", legend_lr))
if r_l_distances != None:
legend_items.append(("distance-rl", legend_rl))
legend_items.append(("boundary", [fig_boundary]))
legend_items.append(("vertices", legend_vertices))
legend_items = legend_items + legend_polygons
legend = Legend(items=legend_items)
legend.click_policy = "mute"
fig.add_layout(legend, 'right')
if render:
show(fig)
return fig
def plot_container_steps(self, render=True, colums=2, plot_width=600, plot_height=600) -> Column:
grid = gridplot(self.plot_steps, ncols=colums, plot_width=plot_width, plot_height=plot_height,
toolbar_location="left")
min_border = (int(self.hc.min_border * 10)) / 10
max_border = (int(self.hc.max_border * 10)) / 10
# text="<b>Hc_{} height: {}-{} alpha: {}<b>
title = Div(
text="<b>Highclass Container {}, Polygon height: {}-{} <b>".format(self.hc.i, min_border,
max_border))
grid_layout = column(title, grid)
if render:
show(grid_layout)
return grid_layout
class Mini_Container(object):
def __init__(self, max_width: float, max_height: float, max_polygon_width: float, hc_i: int, c=2.214) -> None:
self.max_polygon_width = max_polygon_width
self.current_right_boundary = 0
self.height = 0
self.hc_i = hc_i
self.hc_height = max_height
self.max_width = max_width
self.c = c
self.polygons = []
self.y_offset = 0
self.plot_steps = []
def plot_container(self, render=True, title="", background_c=None) -> Figure:
y_offset = self.y_offset
legend_polygons = []
legend_spine = []
legend_lr = []
legend_rl = []
legend_vertices = []
TOOLTIPS = [("index", "$index"), ("(x,y)", "($x{0.0}, $y{0.0})"), ]
fig = figure(title=title, x_axis_label='x', y_axis_label='y', tooltips=TOOLTIPS, toolbar_location="left")
if background_c != None:
color_box = BoxAnnotation(left=0, right=self.max_width, bottom=y_offset,
top=y_offset + self.height, fill_color=background_c,
fill_alpha=0.1)
fig.add_layout(color_box)
for counter, polygon in enumerate(self.polygons):
x_values = polygon.x_values
y_values = polygon.y_values
poly_fig = fig.patch(x_values, y_values, line_width=1, alpha=0.1, line_alpha=1, muted_alpha=0.05)
circle_fig = fig.circle(x_values, y_values, line_width=1, muted_alpha=0.01)
legend_label = "Polygon{}".format(counter)
legend_polygons.append((legend_label, [poly_fig]))
legend_vertices.append(circle_fig)
x_spine = [x[0] for x in polygon.spine]
y_spine = [y[1] for y in polygon.spine]
spine_fig = fig.line(x_spine, y_spine, line_color="red", line_width=1, alpha=0.1, muted_alpha=1,
muted_color="red")
legend_spine.append(spine_fig)
# building the custom legend
fig_boundary = fig.line([0, self.max_width, self.max_width, 0, 0],
[0 + y_offset, 0 + y_offset, self.height + y_offset, self.height + y_offset,
0 + y_offset]
, line_color="black", alpha=0.7, line_width=1, muted_alpha=0.2, )
fig_polygon_boundary = fig.line([self.current_right_boundary, self.current_right_boundary],
[0 + y_offset, self.height + y_offset]
, line_color="black", line_dash="dotted", alpha=0.7, line_width=1,
muted_alpha=0.2, )
items = legend_polygons + [("spine", legend_spine)]
items.append(("container-boundary", [fig_boundary]))
items.append(("last polygon-boundary", [fig_polygon_boundary]))
items.append(("vertices", legend_vertices))
legend = Legend(items=items)
legend.click_policy = "mute"
fig.add_layout(legend, 'right')
if render:
show(fig)
return fig
class End_Container(object):
def __init__(self, mini_container_array: [Mini_Container], angle=0) -> None:
self.mini_containers = copy.deepcopy(mini_container_array)
self.initial_mini_containers = mini_container_array
self.polygons, self.max_width, self.max_height, self.container_not_clipped_area = self.pack_container()
self.x_values_border = [0, 0, self.max_width, self.max_width, 0]
self.y_values_border = [0, self.max_height, self.max_height, 0, 0]
self.container_area = self.max_width * self.max_height
self.angle = angle
self.plot_steps_all = None
def pack_container(self) -> ([ConvexPolygon], float, float):
y_offset = 0
end_c_polygons = []
container_polygon_boundary_width = 0
container_not_clipped_area = 0
for mini_container in self.mini_containers:
container_not_clipped_area += mini_container.max_width * mini_container.hc_height
for polygon in mini_container.polygons:
polygon.translation(0, y_offset)
mini_container.y_offset = y_offset
y_offset += mini_container.height
end_c_polygons = end_c_polygons + mini_container.polygons
if container_polygon_boundary_width < mini_container.current_right_boundary:
container_polygon_boundary_width = mini_container.current_right_boundary
return (end_c_polygons, container_polygon_boundary_width, y_offset, container_not_clipped_area)
def plot_polygons(self, title="", plot_width=500, plot_height=500, render=True) -> Figure:
if title == "":
title = 'End-Container area: {} not-clipped-area: {} angle:{}'.format(truncate(self.container_area, 1),
truncate(
self.container_not_clipped_area,
1), self.angle)
fig = plot_polygons_in_single_plot(self.polygons, title=title, plot_width=plot_width, plot_height=plot_height,
render=render, border=(self.x_values_border, self.y_values_border))
return fig
def plot_steps(self, render=True):
if render:
show(self.plot_steps_all)
return self.plot_steps_all
def plot_container(self, title="", plot_width=600, plot_height=600, solo_box_border=False, render=True,
reverse_legend=True) -> Figure:
legend_mini_containers = []
legend_spine = []
legend_lr = []
legend_rl = []
legend_items = []
legend_vertices = []
TOOLTIPS = [("index", "$index"), ("(x,y)", "($x{0.0}, $y{0.0})"), ]
if title == "":
title = 'End-Container area: {} not-clipped-area: {} angle:{}'.format(
truncate(self.container_area, 1), truncate(self.container_not_clipped_area, 1), self.angle)
fig = figure(title=title, x_axis_label='x', y_axis_label='y', width=plot_width, height=plot_height,
toolbar_location="left", tooltips=TOOLTIPS)
y_offset = 0
colors = itertools.cycle(palette)
for counter, mini_container in enumerate(self.mini_containers):
color = next(colors)
legend_polygons = []
for polygon in mini_container.polygons:
source = ColumnDataSource(data=dict(x=polygon.x_values, y=polygon.y_values))
fig_polygon = fig.patch(x="x", y="y", line_width=1, color=color, line_color=color, muted_color=color,
alpha=0.1, muted_alpha=0.05, line_alpha=1, source=source)
fig_circle = fig.circle(x="x", y="y", line_width=1, color=color, fill_color=color, muted_color=color,
muted_alpha=0.01, size=4,
source=source)
spine_x_values = [x[0] for x in polygon.spine]
spine_y_values = [x[1] for x in polygon.spine]
fig_spine = fig.line(spine_x_values, spine_y_values, line_color="red", line_width=1, alpha=0.01,
muted_color="red",
muted_alpha=1)
legend_spine.append(fig_spine)
legend_polygons = legend_polygons + [fig_polygon]
legend_vertices.append(fig_circle)
if solo_box_border:
mini_box_border = mini_container.current_right_boundary
fig.title.text = 'End-Container mini-containers with solo boundarys'
else:
mini_box_border = self.max_width
color_box = BoxAnnotation(left=0, right=mini_box_border, bottom=mini_container.y_offset,
top=mini_container.y_offset + mini_container.height, fill_color=color,
fill_alpha=0.1)
fig.add_layout(color_box)
fig_border = fig.line([0, mini_box_border, mini_box_border, 0, 0],
[0 + y_offset, 0 + y_offset, mini_container.height + y_offset,
mini_container.height + y_offset,
0 + y_offset], line_color=color, muted_alpha=0.2)
y_offset += mini_container.height
legend_label = "MC{} height:{} (hc{})".format(counter, int(mini_container.height), mini_container.hc_i)
legend_polygons.append(fig_border)
legend_mini_containers.append((legend_label, legend_polygons))
spine_legend = [("spine", legend_spine)]
vertices_legend = [("vertices", legend_vertices)]
legend_items = legend_items + legend_mini_containers + spine_legend + vertices_legend
if reverse_legend:
legend_items.reverse()
legend = Legend(items=legend_items)
fig.add_layout(legend, 'right')
fig.legend.click_policy = "mute"
if render:
show(fig)
return fig
class ConvexContainer(object):
def __init__(self, polygons: [ConvexPolygon], steps=90, build_plots=True) -> None:
self.angle_0_end_container = pack_polygons(polygons)
self.angle_0_end_container_polygons = self.angle_0_end_container.polygons
self.rotate_center = (self.angle_0_end_container.max_width / 2, self.angle_0_end_container.max_height / 2)
self.rotated_end_container_list = [] # Liste aller Endcontainer
self.rotated_container_plots = []
self.back_rotated_polygons_plots = []
self.smallest_end_container, self.polygons, self.angle, self.area = self.find_convex_container(steps,
build_plots)
self.width = self.smallest_end_container.max_width
self.height = self.smallest_end_container.max_height
self.boundarys_x_values, self.boundarys_y_values = self.set_boundarys()
self.plot_steps_all = self.build_plot_steps()
def build_plot_steps(self):
convex_c_panels = []
smallest_c = self.plot_container(render=False, plot_width=800, plot_height=700)
smallest_c_tab = Panel(child=smallest_c, title="Smallest-Convex-Container")
convex_c_panels.append(smallest_c_tab)
rotated_c = self.plot_rotated_containers(render=False, plot_width=800, plot_height=700)
rotated_c_tab = Panel(child=rotated_c, title="Rotated-End-Containers")
convex_c_panels.append(rotated_c_tab)
back_rotated_c = self.plot_back_rotated_polygons(render=False, plot_width=800, plot_height=700)
back_rotated_c_tab = Panel(child=back_rotated_c, title="Convex-Containers (back rotated)")
convex_c_panels.append(back_rotated_c_tab)
tabs = Tabs(tabs=convex_c_panels)
t_header = Panel(child=tabs, title="Convex-Container") #
tab_header = self.smallest_end_container.plot_steps(render=False)
tab_header.tabs.append(t_header)
return tab_header
def plot_steps(self, render=True):
if render:
show(self.plot_steps_all)
return self.plot_steps_all
def find_convex_container(self, steps: int, build_plots=True) -> (End_Container, [ConvexPolygon], int, float):
list_of_area = []
polygons = []
for angle in range(0, 360, steps):
polygons = rotate_polygons(self.angle_0_end_container_polygons, -angle, origin=self.rotate_center)
rotated_end_container = pack_polygons(polygons, -angle)
# rotated_end_container.angle=angle
self.rotated_end_container_list.append(rotated_end_container)
list_of_area.append(rotated_end_container)
if build_plots: # das Flag ist aus Performance gründen da sonst wird jeder End Container zurück rotiert
title = 'End-Container area: {} not-clipped-area: {} angle: {}'.format(
truncate(rotated_end_container.container_area, 1),
truncate(rotated_end_container.container_not_clipped_area, 1), rotated_end_container.angle)
self.rotated_container_plots.append(rotated_end_container.plot_container(render=False, title=title))
back_rotated_polygons = rotate_polygons(rotated_end_container.polygons, angle,
origin=self.rotate_center) # kreiert neue Polygone
box_x_v = rotated_end_container.x_values_border
box_y_v = rotated_end_container.y_values_border
boundarys = list(zip(box_x_v, box_y_v))
rotated_x_values, rotated_y_values = rotate_points_and_split(boundarys, angle,
origin=self.rotate_center)
title2 = 'Convex-Container area: {} not-clipped-area: {} angle: {}'.format(
truncate(rotated_end_container.container_area, 1),
truncate(rotated_end_container.container_not_clipped_area, 1), -rotated_end_container.angle)
back_rotated_polygon_plot = plot_polygons_in_single_plot(back_rotated_polygons, render=False,
border=(rotated_x_values, rotated_y_values),
title=title2)
self.back_rotated_polygons_plots.append(back_rotated_polygon_plot)
sorted_container = sorted(list_of_area, key=lambda k: k.container_area)
smallest_container = sorted_container[0]
angle = smallest_container.angle
smallest_container_polygons = sorted_container[0].polygons
smallest_back_rotated_polygons = rotate_polygons(smallest_container_polygons, angle, origin=self.rotate_center)
smallest_area = smallest_container.container_area
return (smallest_container, smallest_back_rotated_polygons, abs(angle), smallest_area)
def set_boundarys(self) -> ([Point_xy], [Point_xy]):
container = self.smallest_end_container
boundarys_x_values = [0, 0, self.width, self.width, 0]
boundarys_y_values = [0, self.height, self.height, 0, 0]
boundarys = list(zip(boundarys_x_values, boundarys_y_values))
rotated_x_values, rotated_y_values = rotate_points_and_split(boundarys, container.angle,
origin=self.rotate_center)
return (rotated_x_values, rotated_y_values)
def plot_rotated_containers(self, render=True, colums=9, plot_width=600, plot_height=600) -> Column:
grid = gridplot(self.rotated_container_plots, ncols=colums, plot_width=plot_width, plot_height=plot_height,
toolbar_location="left")
if render:
show(grid)
return grid
def plot_back_rotated_polygons(self, render=True, colums=9, plot_width=700, plot_height=600) -> Column:
grid = gridplot(self.back_rotated_polygons_plots, ncols=colums, plot_width=plot_width, plot_height=plot_height,
toolbar_location="left")
if render:
show(grid)
return grid
def plot_container(self, title="", plot_width=600, plot_height=600, render=True, reverse_legend=True) -> Figure:
if title == "":
title = 'Convex Container area: {} not-clipped-area: {} angle: {}'.format(
truncate(self.smallest_end_container.container_area, 1),
truncate(self.smallest_end_container.container_not_clipped_area, 1), self.angle)
fig = plot_polygons_in_single_plot(self.polygons, title=title, plot_width=plot_width, plot_height=plot_height,
render=render, border=(self.boundarys_x_values, self.boundarys_y_values))
return fig
def rotate_points_and_split(point_list: [Point_xy], angle, origin=(0, 0)) -> ([float], [float]):
poly_wrapper = Polygon(point_list)
poly_wrapper_rotated = affinity.rotate(poly_wrapper, angle, origin=origin)
return poly_wrapper_rotated.exterior.xy
def rotate_and_create_new_convex_polygon(polygon: ConvexPolygon, angle: int, origin=(0, 0)) -> ConvexPolygon:
poly_wrapper = Polygon(polygon.shell)
poly_wrapper_rotated = affinity.rotate(poly_wrapper, angle, origin=origin)
rotated_convex_polygon = ConvexPolygon(poly_wrapper_rotated.exterior.coords)
return rotated_convex_polygon
def rotate_polygons(polygons: [ConvexPolygon], angle: int, origin=(0, 0)) -> [ConvexPolygon]:
rotated_polygons = []
for polygon in polygons:
rotated_polygon = rotate_and_create_new_convex_polygon(polygon, angle, origin)
rotated_polygons.append(rotated_polygon)
return rotated_polygons
def build_mini_containers_and_plots(container_array: [Container], c=2.214) -> ([Mini_Container], [[Figure]]):
mini_container_array = []
mini_container_plots_list = []
colors = itertools.cycle(palette)
background_color_list = [next(colors)]
for container in container_array:
container_sigma = copy.deepcopy(container.sigma)
container_and_mini_container_plots = []
box_width = c * container.hc.w_max_polygon
box_width_helper = 0
box_counter = 1 # hilft dabei wie oft der Container in Mini-Container geteilt wird
box_boundarys_x_values = []
# für den plot die grenzen der miniboxen herauszufinden
while box_width_helper < container.x_boundary:
box_boundarys_x_values.append(box_width_helper)
box_width_helper += box_width
background_color_list.append(next(colors))
box_boundarys_x_values_colors_tuple = (box_boundarys_x_values, background_color_list)
container_and_mini_container_plots.append(container.plot_container(container_sigma, render=False,
box_boundarys_x_values_colors_tuple=box_boundarys_x_values_colors_tuple)) # will added to the plots
max_width_mini_container = box_width + container.hc.w_max_polygon
background_counter = 0
# wichtig zu kucken ob der container noch Polygone enthält da die linkesten Punkte noch in der anderen Box liegen können und eine Box leer sein kann
# while len(container_sigma) > 0 and (box_width * box_counter) < (container.x_boundary):
while len(container_sigma) > 0:
mini_container = Mini_Container(max_width_mini_container, (container.y_boundary),
container.hc.w_max_polygon, container.hc.i)
translation = box_width * (box_counter - 1)
min_translation = math.inf
mini_container_y_border = 0
mini_container_x_border = 0
# new
pop_list = [] # enthält die counter der Polygone die zur box gehören
for counter, polygon in enumerate(container_sigma):
if polygon.min_x < (box_width * box_counter):
pop_list.append(counter)
if polygon.min_x < min_translation:
min_translation = polygon.min_x
# selbst wenn man das 0 Element poped gibt es keine Probleme
pop_helper = 0
if pop_list != []:
for counter in pop_list:
container_sigma[counter - pop_helper].translation(-min_translation, 0) # new
if mini_container_y_border < container_sigma[counter - pop_helper].max_y:
mini_container_y_border = container_sigma[counter - pop_helper].max_y
if mini_container_x_border < container_sigma[counter - pop_helper].max_x:
mini_container_x_border = container_sigma[counter - pop_helper].max_x
mini_container.polygons.append(container_sigma.pop(counter - pop_helper))
pop_helper += 1
# mini_container.plot_container()
mini_container.height = mini_container_y_border
mini_container.current_right_boundary = mini_container_x_border
mini_container_array.append(mini_container)
if (box_width * box_counter) < (container.x_boundary):
title = "Mini-Container{} height: {} (hc_{})".format(box_counter, truncate(mini_container.height, 1),
container.hc.i)
b_color = background_color_list[background_counter] # ----
container_and_mini_container_plots.append(
mini_container.plot_container(title=title, render=False, background_c=b_color))
box_counter += 1
background_counter += 1
# für die kürzere box
else:
title = "Mini-Container{} height: {} (hc_{})".format(box_counter, truncate(mini_container.height, 1),
container.hc.i)
# mini_container.plot_container(title)-
container_and_mini_container_plots.append(mini_container.plot_container(title=title, render=False))
mini_container_plots_list.append(container_and_mini_container_plots)
return (mini_container_array, mini_container_plots_list)
def plot_mini_containers(plot_steps: [[Figure]], render=True, colums=3, plot_width=600, plot_height=600) -> Column:
plots = []
for plot in plot_steps:
grid = gridplot(plot, ncols=colums, plot_width=plot_width, plot_height=plot_height, toolbar_location="left")
plots.append(grid)
if render:
show(layout(plots))
return layout(plots)
def create_multiple_convex_polygons(number: int, max_ngon: int, max_rand=1000) -> [ConvexPolygon]:
polygon_list = []
for count in range(0, number):
polygon_list.append(create_convex_polygon(max_ngon, max_rand))
return polygon_list
def create_convex_polygon(max_ngon: int,
max_rand=1000) -> ConvexPolygon: # die erste Koordinate der konvexen Polygone wird dupliziert zum schließen des Polygons
ngon = numpy.random.randint(3, max_ngon + 1)
# polygon_points=[]
convex_polygon = None
while type(convex_polygon) is not Polygon: # da bei der Convexen Hülle ein Punkt oder String rauskommen kann
polygon_points = []
while len(polygon_points) < ngon:
x = numpy.random.randint(0, max_rand + 1)
y = numpy.random.randint(0, max_rand + 1)
while (x, y) in polygon_points:
x = numpy.random.randint(0, max_rand + 1)
y = numpy.random.randint(0, max_rand + 1)
polygon_points.append((x, y))
convex_polygon = Polygon(polygon_points).convex_hull
c_polygon = ConvexPolygon(list(convex_polygon.exterior.coords))
return c_polygon
def plot_polygons(polygon_list: [ConvexPolygon], render=True, plot_width=450, plot_height=450, ncols=4) -> Column:
plots = []
colors = itertools.cycle(palette)
for counter, polygon in enumerate(polygon_list):
color = next(colors)
title = "Polygon {}".format(counter)
plots.append(polygon.plot_polygon(title=title, color=color, render=False))
grid = gridplot(plots, ncols=ncols, plot_width=plot_width, plot_height=plot_height, toolbar_location="left")
if render:
show(grid)
return grid
def plot_figures_as_grid(plot_list: [Figure], render=True, plot_width=600, plot_height=500, ncols=4) -> Column:
grid = gridplot(plot_list, ncols=ncols, plot_width=plot_width, plot_height=plot_height, toolbar_location="left")
if render:
show(grid)
return grid
def plot_polygons_in_single_plot(polygon_list: [ConvexPolygon], title="", plot_width=750, plot_height=500, render=True,
border=None, reverse_legend=False) -> Figure:
polygon_number = len(polygon_list)
TOOLTIPS = [("index", "$index"), ("(x,y)", "($x{0.0}, $y{0.0})"), ]
fig = figure(title=title, x_axis_label='x', y_axis_label='y', width=plot_width, height=plot_height,
tooltips=TOOLTIPS, toolbar_location="left")
colors = itertools.cycle(palette)
legend_items = []
legend_polygons = []
legend_all_polygons = []
legend_vertices = []
for counter, polygon in enumerate(polygon_list):
color = next(colors)
x = polygon.x_values
y = polygon.y_values
if polygon.plot_fill:
legend_label = "polygon {} filled".format(counter)
poly_fig = fig.patch(x, y, color=color, line_width=1, alpha=0.9, line_alpha=1, muted_alpha=0.05)
else:
legend_label = "polygon {}".format(counter)
poly_fig = fig.patch(x, y, color=color, line_width=1, alpha=0.1, line_alpha=1, muted_alpha=0.05)
circle_fig = fig.circle(x, y, color=color, line_width=1, muted_alpha=0.01, size=4)
legend_polygons.append((legend_label, [poly_fig]))
legend_vertices.append(circle_fig)
legend_all_polygons = legend_all_polygons + [poly_fig]
if border != None:
fig_border = fig.line(border[0], border[1], line_color="red", line_width=1, muted_alpha=0.2)
legend_items.append(("border", [fig_border]))
legend_items.append(("vertices", legend_vertices))
legend_items.append(("all polygons", legend_all_polygons))
legend_items = legend_items + legend_polygons
if reverse_legend:
legend_items.reverse()
legend = Legend(items=legend_items)
legend.label_text_font_size = "10px"
legend.click_policy = "mute"
fig.add_layout(legend, 'right')
if render:
show(fig)
return fig
def build_height_classes(polygon_list: [ConvexPolygon]) -> [HighClass]:
ordered_polygons = sorted(polygon_list, key=lambda polygon: polygon.height, reverse=True)
h_max_polygon = ordered_polygons[0].height
w_max_polygon = max([polygon.width for polygon in polygon_list])
alpha = 0.407
i = 0
height_classes = []
polygon_count = len(ordered_polygons)
while polygon_count > 0:
hc = HighClass(i, alpha, h_max_polygon, w_max_polygon)
hc_polygons = []
while polygon_count > 0 and hc.min_border < ordered_polygons[0].height and ordered_polygons[
0].height <= hc.max_border:
hc_polygons.append(ordered_polygons.pop(0))
polygon_count -= 1
hc.set_polygons(hc_polygons)
if len(hc.polygons) > 0:
height_classes.append(hc) # will man höhen Klassen ohne Polygone drinne ?
i += 1
return height_classes
def building_containers(height_classes: [HighClass]) -> [Container]:
containers = []
for height_class in height_classes:
container = Container(height_class)
containers.append(container)
return containers
def pack_polygons(polygons: [ConvexPolygon], angle=0) -> End_Container:
# building the endcontainer
list_hc = build_height_classes(polygons)
list_containers = building_containers(list_hc)
list_mini_containers, mini_container_plot_steps = build_mini_containers_and_plots(list_containers)
end_container = End_Container(list_mini_containers, angle)
# plots
p_tab = polygons_to_tab_plot(polygons)
p_header_tab = Panel(child=p_tab, title="Polygons")
hc_tab = hc_to_tab_plot(list_hc)
hc_header_tab = Panel(child=hc_tab, title="Height-Classes")
c_tab = containers_to_tab_plot(list_containers)
c_header_tab = Panel(child=c_tab, title="Containers")
mc_tab = mini_container_plots_to_tab_plot(mini_container_plot_steps)
mc_header_tab = Panel(child=mc_tab, title="Mini-Containers")
ec_tab = end_container_to_tab_plot(end_container)
ec_header_tab = Panel(child=ec_tab, title="End-Container")
all_tabs_with_header = Tabs(tabs=[p_header_tab, hc_header_tab, c_header_tab, mc_header_tab, ec_header_tab])
end_container.plot_steps_all = all_tabs_with_header
return end_container
def polygons_to_tab_plot(polygons: [ConvexPolygon], tab_poly_count=9, ncols=3, plot_width=450, plot_height=450) -> Tabs:
polygon_tab_list = []
polygons_in_one_tab = []
colors = itertools.cycle(palette)
for counter, polygon in enumerate(polygons):
color = next(colors)
polygon_title = "Polygon{}".format(counter)
polygon_plot = polygon.plot_polygon(title=polygon_title, color=color, render=False)
polygons_in_one_tab.append(polygon_plot)
if len(polygons_in_one_tab) >= tab_poly_count or (counter + 1 == len(polygons)):
# tab_layout= ([polygons_in_one_tab])
if counter + 1 - tab_poly_count < 0:
title = "Polygons {}-{}".format(0, counter)
else:
title = "Polygons {}-{}".format(counter + 1 - len(polygons_in_one_tab), counter)
grid_title = Div(text="<b>{}<b>".format(title))
polygons_grid = gridplot(polygons_in_one_tab, ncols=ncols, plot_width=plot_width, plot_height=plot_height,
toolbar_location="left")
tab_layout = layout(grid_title, polygons_grid)
tab = Panel(child=tab_layout, title=title)
polygon_tab_list.append(tab)
polygons_in_one_tab = []
polygon_tabs = Tabs(tabs=polygon_tab_list)
return polygon_tabs
def hc_to_tab_plot(list_hc: [HighClass], plot_width=450, plot_height=450) -> Tabs:
hc_tab_list = []
for counter, hc in enumerate(list_hc):
hc_plot = hc.plot_hc(render=False, plot_width=plot_width, plot_height=plot_height)
tab = Panel(child=hc_plot, title="High-Class {}".format(counter))
hc_tab_list.append(tab)
hc_tabs = Tabs(tabs=hc_tab_list)
return hc_tabs
def containers_to_tab_plot(list_containers: [Container], plot_width=700, plot_height=700) -> Tabs:
container_tab_list = []
for counter, container in enumerate(list_containers):
container_plot = container.plot_container_steps(plot_width=plot_width, colums=3, plot_height=plot_height,
render=False)
tab = Panel(child=container_plot, title="Container {}".format(counter, counter))
container_tab_list.append(tab)
container_tabs = Tabs(tabs=container_tab_list)
return container_tabs
def mini_container_plots_to_tab_plot(mini_container_plot_steps: [Figure], plot_width=700, plot_height=700,
ncols=3) -> Tabs:
mini_plots_tabs = []
for counter, m_plot in enumerate(mini_container_plot_steps):
m_plot_grid = gridplot(m_plot, ncols=3, plot_width=plot_width, plot_height=plot_height, toolbar_location="left")
grid_title = Div(text="<b>Hc{} to Mini-Containers<b>".format(counter))
mc_layout = layout(grid_title, m_plot_grid)
tab = Panel(child=mc_layout, title="Hc{} Mini-Containers".format(counter))
mini_plots_tabs.append(tab)
mini_tabs = Tabs(tabs=mini_plots_tabs)
return mini_tabs
def end_container_to_tab_plot(end_container: End_Container, plot_width=800, plot_height=800) -> Tabs:
end_container_tabs = []
polygons_plot = end_container.plot_polygons(render=False, plot_width=plot_width, plot_height=plot_height)
tab = Panel(child=polygons_plot, title="End-Container")
end_container_tabs.append(tab)
container_plot = end_container.plot_container(render=False, plot_width=plot_width, plot_height=plot_height)
tab = Panel(child=container_plot, title="Show Mini-Containers")
end_container_tabs.append(tab)
end_tabs = Tabs(tabs=end_container_tabs)
return end_tabs
def plot_containers(container_list: [Container], render=True, colums=3, plot_width=500, plot_height=500) -> Column:
container_plots = []
for container in container_list:
container_plots.append(container.plot_container(render=False))
grid = gridplot(container_plots, ncols=colums, plot_width=plot_width, plot_height=plot_height,
toolbar_location="left")
if render:
show(grid)
return grid
# https://kodify.net/python/math/truncate-decimals/
# Python.org (n.d.). math — Mathematical functions. Retrieved on October 22, 2019, from https://docs.python.org/3.8/library/math.html
def truncate(number: float, decimals=0) -> float:
"""
Returns a value truncated to a specific number of decimal places.
"""
if not isinstance(decimals, int):
raise TypeError("decimal places must be an integer.")
elif decimals < 0:
raise ValueError("decimal places has to be 0 or more.")
elif decimals == 0:
return math.trunc(number)
factor = 10.0 ** decimals
return math.trunc(number * factor) / factor
# output_notebook() # for using Bokeh in Jupyter Lab