Skip to content

Instantly share code, notes, and snippets.

@metaflow metaflow/1.py

Created Jul 9, 2020
Embed
What would you like to do?
#!/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')
@metaflow

This comment has been minimized.

Copy link
Owner Author

metaflow commented Jul 9, 2020

[True, False, False, False, False]
found solution for 4
15.22560167312622 s
107_212_344_442_

[False, False, False, False, False]
found solution for 5
53.712339639663696 s
000_114_217_311_407_

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.