上記urlにあるネスティングツールでは
- 大量の多角形部品を
- 部品を回転させながら
- GA(Genetic Algorithm、遺伝的)アルゴリズムと
- NFP (No Fit Polygon = ≒ ミンコフスキー差 ?)アルゴリズム
で、図形詰み込みを行っていますが、
少数の部品であれば、部品の回転や、GAがなくても、詰み込み可能と思い、
pythonで書いてみた。
import copy
import pyclipper
import io
import matplotlib.pyplot as plt
import numpy as np
import re
import sys
from functools import cmp_to_key
from matplotlib.path import Path
from matplotlib.patches import PathPatch
from matplotlib.collections import PatchCollection
from shapely import affinity
from shapely.geometry import Polygon, LineString, Point
co_bin = [
[ 0, 0],[120, 0],[120,50],[0,50]]
co_parts = [
[[ 0, 0],[ 20, 0],[ 20,50],[ 0,50]],
[[20, 0],[ 60, 0],[ 60,50],[40,50],[40,30],[20,30]],
[[20,30],[ 40,30],[ 40,50],[20,50]],
[[60, 0],[100, 0],[100,30]],
[[60, 0],[100,30],[100,50],[60,50]]
]
def main():
poly_bin = Polygon( shell=co_bin, holes=[])
poly_parts = []
for co_part in co_parts:
poly_part = Polygon( shell=co_part, holes=[])
poly_part = align_to_origin( poly_part )
poly_parts.append( poly_part )
poly_parts = sort_parts(poly_parts)
placed_parts = []
placed_part = Polygon(shell=[], holes=[])
while len(poly_parts):
for j, poly_part in enumerate(poly_parts):
poly_inner = inner_fit_rect( poly_bin,poly_part )
if not poly_inner:
continue
new_part_pos = None
if placed_part.area:
poly_mnkwski = minkowski_diff( placed_part,poly_part )
if not poly_mnkwski:
continue
new_part_pos = calc_new_part_pos_1( poly_inner, poly_mnkwski)
else:
new_part_pos = calc_new_part_pos_0( poly_inner )
if not new_part_pos:
continue
poly_part = affinity.translate( poly_part,
xoff=new_part_pos[0],
yoff=new_part_pos[1] )
placed_parts.append( poly_part )
placed_part = placed_part.union( poly_part )
poly_parts.pop(j)
plot_polygons(poly_bin, placed_parts)
break
def calc_new_part_pos_0( poly_inter ):
if type(poly_inter) is Point:
[(x_0,y_0)] = list(poly_inter.coords)
return (x_0,y_0)
if type(poly_inter) is LineString:
tmp_coords = list( poly_inter.coords )
tmp_coords = sort_coords( tmp_coords )
return tmp_coords[0]
tmp_coords = list( poly_inter.exterior.coords )
tmp_coords = sort_coords( tmp_coords )
return tmp_coords[0]
def calc_new_part_pos_1( poly_inner, poly_mnkwski):
edges_inner = conv_to_lines( poly_inner )
edges_mnkwski = conv_to_lines( poly_mnkwski )
cross_points = []
for edge_inner in edges_inner:
for edge_mnkwski in edges_mnkwski:
cross_point = line_cross_point(edge_inner, edge_mnkwski)
if cross_point:
cross_points.append( cross_point )
if len(cross_points) == 0:
return None
cross_points = sort_coords( cross_points )
return cross_points[0]
def conv_to_lines(org_poly):
org_coords = []
if type(org_poly) is LineString:
org_coords = org_poly.coords
elif type(org_poly) is Polygon:
org_coords = org_poly.exterior.coords
else:
return []
ret_lines = []
for k in range(len(org_coords) - 1):
co_0 = org_coords[k]
co_1 = org_coords[k+1]
if co_0 == co_1:
continue
ret_lines.append( LineString( org_coords[k:k+2]) )
return ret_lines
def align_to_origin(poly):
(min_x, min_y, max_x, max_y) = ( poly.bounds )
new_poly = affinity.translate(poly, xoff= -1 * min_x, yoff= -1 * min_y)
return new_poly
def sort_parts(poly_parts):
ret_parts = sorted(poly_parts,
key=lambda x: x.area,
reverse=True)
return ret_parts
def sort_coords( coords ):
def sort_coords_sub(coord_a,coord_b):
if coord_a[0] < coord_b[0]:
return -1
if coord_a[0] > coord_b[0]:
return 1
if coord_a[1] < coord_b[1]:
return -1
if coord_a[1] > coord_b[1]:
return 1
return 0
ret_coords = sorted( coords, key=cmp_to_key(sort_coords_sub) )
return ret_coords
def inner_fit_rect(poly_a,poly_b):
(min_x_a,min_y_a,max_x_a,max_y_a) = poly_a.bounds
(min_x_b,min_y_b,max_x_b,max_y_b) = poly_b.bounds
if max_x_a - min_x_a < max_x_b - min_x_b or \
max_y_a - min_y_a < max_y_b - min_y_b:
return None
coords_b = poly_b.exterior.coords[0]
min_x = min_x_a - min_x_b + coords_b[0]
min_y = min_y_a - min_y_b + coords_b[1]
max_x = max_x_a - max_x_b + coords_b[0]
max_y = max_y_a - max_y_b + coords_b[1]
poly = Polygon(
shell=[[min_x,min_y],[max_x,min_y],[max_x,max_y],[min_x,max_y]],
holes=[])
return poly
def minkowski_diff(poly_a,poly_b):
shell_a = list( poly_a.exterior.coords )
shell_b = list( poly_b.exterior.coords )
minkowskis = pyclipper.MinkowskiDiff(shell_b, shell_a)
if len(minkowskis) == 1:
return Polygon( shell=minkowskis[0], holes=[])
tmp_poly_0 = Polygon( shell=minkowskis[0], holes=[])
tmp_poly_1 = Polygon( shell=minkowskis[1], holes=[])
if tmp_poly_0.area < tmp_poly_1.area:
return tmp_poly_1
return tmp_poly_0
def plot_polygons(poly_bin, poly_parts,poly_other=None):
fig, ax = plt.subplots()
if poly_bin:
plot_polygon(ax,
poly_bin,
facecolor='None',
edgecolor='black',
alpha=1)
for poly_part in poly_parts:
plot_polygon(ax,
poly_part,
facecolor='lightblue',
edgecolor='blue',
alpha=0.2)
if poly_other:
plot_polygon(ax,
poly_other,
facecolor='None',
edgecolor='red',
alpha=1)
plt.show()
def plot_polygon(ax, poly, **kwargs):
if poly.type == "MultiPolygon":
for polygon_tmp in poly.geoms:
plot_polygon(ax, polygon_tmp, **kwargs)
return
path = Path.make_compound_path(
Path(np.asarray(poly.exterior.coords)[:, :2]),
*[Path(np.asarray(ring.coords)[:, :2]) for ring in poly.interiors])
patch = PathPatch(path, **kwargs)
collection = PatchCollection([patch], **kwargs)
ax.add_collection(collection, autolim=True)
ax.autoscale_view()
def line_cross_point(line_p, line_q):
((x0, y0), (x1,y1)) = tuple( line_p.coords )
((x2, y2), (x3,y3)) = tuple( line_q.coords )
if (x0, y0) in ((x2, y2), (x3,y3)):
return (x0, y0)
if (x1, y1) in ((x2, y2), (x3,y3)):
return (x1, y1)
a0 = x1 - x0; b0 = y1 - y0
a2 = x3 - x2; b2 = y3 - y2
d = a0*b2 - a2*b0
if d == 0:
return None
sn = b2 * (x2-x0) - a2 * (y2-y0)
ret_x = x0 + a0*sn/d
ret_y = y0 + b0*sn/d
if x0 <= ret_x <= x1 and x2 <= ret_x <= x3 and \
y0 <= ret_y <= y1 and y2 <= ret_y <= y3:
return (ret_x,ret_y)
return None
if __name__ == '__main__':
main()
↑こう書くと、↓こう表示されます
