上記urlにあるネスティングツールでは
で、図形詰み込みを行っていますが、 少数の部品であれば、部品の回転や、GAがなくても、詰み込み可能と思い、 pythonで書いてみた。
# -*- coding: utf-8 -*- 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]] ] # cf. https://svgnest.com/ def main(): # 領域(bin)のload poly_bin = Polygon( shell=co_bin, holes=[]) # 部品群(parts)のload poly_parts = [] for co_part in co_parts: poly_part = Polygon( shell=co_part, holes=[]) # 後程、minkowski差を求める為、原点へ仮移動 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): # binに内接する範囲を算出 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 #plot_polygons(poly_inner,[placed_part],poly_mnkwski) # inner_fit_rect()とminkowski_diff()のedge交点のうち # 最もbinの原点に近いものをpartの配置先とする 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 # partを配置先へ移動 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] # 最もbinの原点に近いものを算出 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 # 最もbinの原点に近いものを算出 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 # bin (min_x_b,min_y_b,max_x_b,max_y_b) = poly_b.bounds # part # a:binより b:part が大きい場合、算出不可 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() # Plots a Polygon to pyplot `ax` # cf. https://stackoverflow.com/questions/55522395 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() # https://tjkendev.github.io/procon-library/python/geometry/line_cross_point.html 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: # 2つの線分が平行 return None # s = sn/d sn = b2 * (x2-x0) - a2 * (y2-y0) # t = tn/d #tn = b0 * (x2-x0) - a0 * (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()
↑こう書くと、↓こう表示されます
