簡易なNFP (No Fit Polygon)アルゴリズムによる多角形の図形詰み込み問題(bin packing) - end0tknr's kipple - web写経開発
上記entryの別階
# -*- coding: utf-8 -*- import copy import pyclipper import io import math import matplotlib.pyplot as plt import numpy as np import re import sys import random 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, box from shapely.ops import unary_union units_def = {"54_full":{"w":5625,"h":2475}, "54_sub" :{"w":5625,"h":1350}, "49_full":{"w":5175,"h":2475}, "49_sub" :{"w":5175,"h":1350}, "45_full":{"w":4725,"h":2475}, "45_sub" :{"w":4725,"h":1350}, "40_full":{"w":4275,"h":2475}, "40_sub" :{"w":4275,"h":1350}, "36_full":{"w":3825,"h":2475}, "36_sub" :{"w":3825,"h":1350}, "32_full":{"w":3375,"h":2475}, "32_sub" :{"w":3375,"h":1350}, "27_full":{"w":2925,"h":2475}, "27_sub" :{"w":2925,"h":1350} } #floor_coords = [[0,0], [2925+3825+4725, 0], [2925+3825+4725, 2475+2475], # [2925+3825, 2475+2475], [2925+3825, 2475+2475+1350], # [0, 2475+2475+1350] ] floor_coords = [ [0, 1350], [4725, 1350], [4725, 0], [11475, 0],[11475, 6300], [0, 6300] ] outer_wall_coords = [ # 外壁 [[ 0,1350],[ 4725,1350]], [[ 4725,1350],[ 4725, 0]], [[ 4725, 0],[11475, 0]], [[11475, 0],[11475,6300]], [[11475,6300],[ 0,6300]], [[ 0,6300],[ 0,1350]] ] inner_wall_coords = [ # 内壁 [[ 4725,1350],[4725,2475]], [[ 4725,1350],[11475,1350]], [[ 0,3825],[4725,3825]] ] # floor_coords = [[0,0], [2925+3825+4725, 0], [2925+3825+4725, 2475+2475+1350], # [0, 2475+2475+1350] ] def main(): setter = UnitSetter() found_plans = [] for flip_dir in [ [0,0] ]: #for flip_dir in [ [0,0], [1,0], [0,1], [1,1] ]: tmp_coords = setter.flip_coords( floor_coords, flip_dir) tmp_plan = FloorPlan(tmp_coords) # tmp_plan.plot_polygons() plans = setter.find_set_units( tmp_coords ) for plan in plans: plan.calc_score() plan.plot_polygons() class Unit(): def __init__(self, name ): self.name = name self.w = units_def[name]["w"] self.h = units_def[name]["h"] coords = [[0,0],[self.w,0],[self.w,self.h],[0, self.h]] self.shapely = Polygon( shell=coords, holes=[]) dummy_cost = (self.w * self.h) - (self.w * self.h) * 0.1 self.cost = dummy_cost class FloorPlan(): def __init__(self, coords ): self.shapely = Polygon( shell=coords, holes=[]) self.set_units = [] # 配置済みのunit群 self.rest_area = Polygon( shell=coords, holes=[]) # unit未設置の範囲 def add_set_unit(self, unit:Unit ): self.set_units.append( unit ) # 設置済みunitの追加 self.set_rest_area() # unit未設置範囲の更新 def set_rest_area(self): # unit未設置範囲の更新 set_units = Polygon( shell=[], holes=[]) for set_unit in self.set_units: set_units = set_units.union( set_unit.shapely ) self.rest_area = self.shapely.difference( set_units ) def calc_score(self): ret_score = 0 ret_score -= self.rest_area.area # 未割当ての面積 tmp_score = self.calc_inner_wall_score() # unitと壁の重なり ret_score += tmp_score print( ret_score, tmp_score ) def calc_inner_wall_score(self): inner_walls = [] for coord in inner_wall_coords: wall = LineString( coord ) inner_walls.append( wall ) #print( inner_walls ) ret_data = 0 for unit in self.set_units: #print( unit.shapely.boundary ) for inner_wall in inner_walls: intersect = unit.shapely.boundary.intersection(inner_wall) ret_data += intersect.length return ret_data def plot_polygons( self ): fig, ax = plt.subplots() self.plot_polygon(ax, self.shapely,facecolor='None',edgecolor='black') for unit in self.set_units: self.plot_polygon(ax, unit.shapely, facecolor='lightblue', edgecolor='blue', alpha=0.2 ) plt.show() def plot_polygon(self, ax, poly, **kwargs): """ https://stackoverflow.com/questions/55522395 """ if poly.geom_type == "MultiPolygon": for polygon_tmp in poly.geoms: self.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() class UnitSetter(): def __init__(self): pass def flip_coords( self, floor_coords:list, dir:list ): new_coords = [] min_coord = [None,None] for coord in floor_coords: coord = list(coord) if coord[0] != 0 and dir[0] == 1: coord[0] *= -1 if coord[1] != 0 and dir[1] == 1: coord[1] *= -1 new_coords.append( coord ) if min_coord[0] == None or coord[0] < min_coord[0]: min_coord[0] = coord[0] if min_coord[1] == None or coord[1] < min_coord[1]: min_coord[1] = coord[1] for coord in new_coords: if min_coord[0] < 0: coord[0] -= min_coord[0] if min_coord[1] < 0: coord[1] -= min_coord[1] return new_coords def find_set_units( self, floor_coords:list ): i = 0 max_plans = 20 max_retry = 200 tmp_plans = [] while i < max_retry and len(tmp_plans) < max_plans: floor_plan = FloorPlan( floor_coords ) floor_plan = self.do_set_units( floor_plan ) if floor_plan.rest_area.area < 9922500: tmp_plans.append(floor_plan) i += 1 ret_plans = [] for floor_plan in sorted(tmp_plans, key=lambda x: x.rest_area.area ): """ 未割当の面積が少ない順へ """ ret_plans.append( floor_plan ) return ret_plans def do_set_units( self, floor_plan:FloorPlan ): i = 0 remain_area = floor_plan.shapely.area unit_names = list(units_def.keys()) while floor_plan.rest_area.area > 0 and i < len(unit_names): i += 1 # unit設置先の座標を算出 tmp_coords = \ self.sort_coords(list(floor_plan.rest_area.exterior.coords) ) new_unit_pos = tmp_coords[0] # 設置するunitをランダムに選定 random.shuffle( unit_names ) for unit_name in unit_names: unit = Unit( unit_name ) # unitを配置先へ移動 unit.shapely = affinity.translate( unit.shapely, xoff=new_unit_pos[0], yoff=new_unit_pos[1] ) # unit設置可否を確認 chk_result = self.chk_new_unit_pos( floor_plan, unit ) if chk_result == True: floor_plan.add_set_unit( unit ) i = 0 break return floor_plan def chk_new_unit_pos( self, floor_plan:FloorPlan, unit:Unit ): diff = unit.shapely.difference( floor_plan.rest_area ) if diff.area > 0: return False if len( floor_plan.set_units ) == 0: return True unit_lines = self.conv_to_lines( unit.shapely ) for i, unit_line in enumerate( unit_lines ): edge_result = self.chk_unit_edge_position(unit_line, floor_plan ) if edge_result == False: return False return True chk_result = self.chk_position(unit, floor_plan ) if chk_result == False: return floor_plan.set_units.append( unit ) #floor_plan.plot_polygons() return unit def chk_unit_edge_position(self, unit_line:LineString, floor_plan:FloorPlan): """ ┌①──┐┌───┐┌───┐┌②───┐┌③───┐ ┌④───┐ ┠───┤├───┤├──┐│├───┐│├──┐ │ ├───┐│ ○新設 ││新設 ││新設│││新設 │││新設│ │ │新設 ││ ┠──┬┘┝━━○┘┝━━○│┝━━×┘│┝━━×┐│┌┷━━×┘│ │既設│ │既設│ │既設│││既設│ ││既設 │││ 既設│ │ └──┘ └──┘ └──┴┘└──┴─┘└───┴┘└───┴─┘""" # 外壁線とUnit辺が重なっている→ OK ① plan_lines = self.conv_to_lines( floor_plan.shapely ) for plan_line in plan_lines: if plan_line.covers( unit_line ) == True: return True # 間取り内部での長短継→ NG ②～④ for placed_unit in floor_plan.set_units: # 設置済みunitと接するか? intersect = unit_line.intersection( placed_unit.shapely ) if intersect.is_empty or intersect.geom_type != "LineString": continue for coord in intersect.coords: intersect_point = Point( *coord ) # unit間の線が、間取内部にある if not floor_plan.shapely.contains( intersect_point ): continue if (coord == unit_line.coords[0] or \ coord == unit_line.coords[1] ) and \ (coord == placed_unit.shapely.exterior.coords[0] or \ coord == placed_unit.shapely.exterior.coords[1] or \ coord == placed_unit.shapely.exterior.coords[2] or \ coord == placed_unit.shapely.exterior.coords[3] ): continue return False return True def conv_to_lines(self, 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 sort_coords( self, coords ): def sort_coords_sub(coord_a,coord_b): if coord_a[0] == coord_b[0]: if coord_a[1] < coord_b[1]: return -1 if coord_a[1] > coord_b[1]: return 1 return 0 if coord_a[0] < coord_b[0]: return -1 if coord_a[0] > coord_b[0]: return 1 return 0 ret_coords = sorted( coords, key=cmp_to_key(sort_coords_sub) ) return ret_coords if __name__ == '__main__': main()
