#!/usr/bin/env python3 | |
from shapely.geometry.polygon import Polygon | |
from shapely.geometry.multipolygon import MultiPolygon | |
from shapely.geometry.linestring import LineString | |
from shapely.affinity import rotate, translate | |
import shapely | |
import shapely.ops as ops | |
import matplotlib.pyplot as plt | |
import math | |
import numpy as np | |
import os | |
import sys | |
import time | |
import itertools | |
def draw_polygon(p, color): | |
if type(p) is shapely.geometry.MultiPolygon: | |
for x in p.geoms: | |
draw_polygon(x, color) | |
return | |
xs = [] | |
ys = [] | |
for x, y in p.exterior.coords: | |
xs.append(x) | |
ys.append(y) | |
plt.fill(xs, ys, color) | |
p1 = Polygon([(0, 0), (15, 0), (15, 15), (0, 15)]) | |
p2 = Polygon([(0, 0), (29, 0), (29, 29)]) | |
p3 = Polygon([(0, 0), (21, 0), (0, 21)]) | |
p4 = Polygon([(0, 0), (20.5, 0), (31.1, 10.5), (20.5, 21), (0, 21)]) | |
p5 = Polygon([(0, 0), (10.6, 10.6), (21.2, 0), (41.5, 21), (0, 21)]) | |
p1 = translate(p1, 45, 5) | |
p2 = translate(p2, 0, 25) | |
p3 = translate(p3, 30, 25) | |
p4 = translate(p4, 38, 40) | |
p5 = translate(p5, 2, 2) | |
colors = ['red', 'orange', 'yellow', 'green', 'blue'] | |
# Zip polygons with colors to have a consisten coloring. | |
polygons = list(zip([p1, p2, p3, p4, p5], colors)) | |
dpi = 80 | |
fig = plt.figure(dpi = dpi, figsize = (512 / dpi, 512 / dpi) ) | |
plt.axis([0, 70, 0, 70]) | |
for p, c in polygons: | |
draw_polygon(p, c) | |
fig.savefig('initial-state.png') | |
plt.close() | |
def dfs(left: MultiPolygon, label: str, used: [], placed: [], polygons: [], side): | |
eps = 0.05 | |
all = True | |
for x in used: | |
all = all and x | |
if all: | |
fig = plt.figure(dpi=dpi, figsize=(512 / dpi, 512 / dpi)) | |
plt.axis([0, side+1, 0, side+1]) | |
draw_polygon(left, 'black') | |
for p in placed: | |
draw_polygon(p[0], p[1]) | |
fig.savefig(f'{label}.png') | |
plt.close() | |
return True | |
# (lines that slightly overlap the square, (dx, dy) of polygon to cover the square w/o thin | |
# leftovers. | |
checks = [(LineString([(-eps, eps), (side+eps, eps)]), (-3 * eps, -2 * eps)), | |
(LineString([(side-eps, -eps), (side-eps, side + eps)]), | |
(2 * eps, -3 * eps)), | |
(LineString([(eps, -eps), (eps, side + eps)]), | |
(-2 * eps, -3 * eps)), | |
(LineString([(-eps, side-eps), (side + eps, side - eps)]), (-3 * eps, +2 * eps))] | |
for p, u, i in zip(polygons, used, range(0, len(polygons))): # which polygon | |
if u: | |
continue | |
coords = list(p[0].exterior.coords) | |
for xy, j in zip(coords, range(0, len(coords))): # Vertice to place | |
x, y = xy | |
for a in range(0, 8): # Rotations | |
name = f'{label}{i}{j}{a}' | |
for line, dxy in checks: | |
if not line.intersects(left): | |
continue | |
cross = line.intersection(left) | |
x0 = side | |
y0 = side | |
for cx, cy in cross.coords: | |
if (x0 > cx) or (np.isclose(x0, cx, atol=eps) and y0 > cy): | |
x0, y0 = cx, cy | |
x0 += dxy[0] | |
y0 += dxy[1] | |
t = translate(p[0], x0 - x, y0 - y) | |
t = rotate(t, a * 45, (x0, y0)) | |
try: | |
intersection = left.intersection(t) | |
if not np.isclose(intersection.area, t.area, rtol=0.05): | |
continue | |
d = left.difference(t) | |
if type(d) is shapely.geometry.Polygon: | |
d = MultiPolygon([d]) | |
if type(d) is shapely.geometry.MultiPolygon: | |
good = True | |
for g1 in d.geoms: | |
good = good and (len(g1.interiors) == 0) | |
if not good: | |
continue | |
used[i] = True | |
placed.append((t, p[1])) | |
try: | |
if dfs(d, f'{name}_', used, placed, polygons, side): | |
return True | |
except KeyboardInterrupt: | |
sys.exit(1) | |
except Exception as e: | |
# print('exception', e) | |
pass | |
placed.pop() | |
used[i] = False | |
except KeyboardInterrupt: | |
sys.exit(1) | |
except Exception as e: | |
# print('exception', e) | |
pass | |
if len(placed) == 0: | |
# No reasons to check more intersection lines if it's a first polygon to place. | |
break | |
return False | |
def solve(use: int): | |
""" | |
fill a square using `use` polygons. | |
""" | |
for j in range(1 << 5): | |
t = 0 | |
# set position means that we marked this polygon as used already and it will not be placed again. | |
used = [True] * 5 | |
sum = 0 | |
for i in range(5): | |
used[i] = (j & (1 << i)) != 0 | |
if not used[i]: | |
sum += polygons[i][0].area | |
t += 1 | |
if t != use: | |
continue | |
print(used) | |
side = math.sqrt(sum) | |
square = Polygon([(0, 0), (side, 0), (side, side), (0, side)]) | |
if dfs(MultiPolygon([square]), '', used, [], polygons, side): | |
return True | |
return False | |
start = time.time() | |
if solve(4): | |
print('found solution for 4') | |
print(time.time() - start, 's') | |
start = time.time() | |
if solve(5): | |
print('found solution for 5') | |
print(time.time() - start, 's') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
[True, False, False, False, False]

found solution for 4
15.22560167312622 s
[False, False, False, False, False]

found solution for 5
53.712339639663696 s