I decided to write a program to solve Tangram puzzles. This went a bit out of hand and I ended up with 600+ lines of code. I don't think it should have taken so much code.
Here is an image of a positive result:
Problem sources
The problems to be solved are .png images, I found on the web, of 480x480 pixels with a white background and tangram figures in various colours, details can be found in function get_random_image.
Algorithm
The algorithm used isn't ideal: it successfully finds a solution in only a small part of my test set. It depends (among others) on allowed distance differences (EPSILON in the code). For the purposes of this review, I am satisfied with a heuristic that does not solve all cases.
- Find corners points (using OpenCV)
- Find edges and more interesting points
- Find small triangles
- Find possible tangram pieces positions from the small triangles
- Find the combination of pieces such that all triangles are 'covered'
Questions
I like PEP8, however I like also to deviate from it for sake of readability in cases such as:
if ( condition_1 and condition_2 and not condition_3):Am I using white space correctly and/or readable?
I don't like to write classes in Python (mainly because of typing all the
self.everywhere) but are my classes sensible?
(I know it's long, that's part of the problem, the fun part is the solve method of TangramSolver)
Code
import cv2
import numpy as np
from glob import glob
from matplotlib import pyplot as plt
from itertools import product, permutations, combinations
from collections import namedtuple
# some 'constants'
EPSILON = 0.2
EPSILON_ANGLE = 3.0
ZERO = 0.0
ONE = 1.0
TWO = 2 * ONE
FOUR = 2 * TWO
SQ2 = np.sqrt(TWO)
SQ10 = np.sqrt(10.0)
FIND_REPEATS = 1
MAX_LENGTHS = 6
SPLITS = {}
for lengths in product([ZERO, SQ2, TWO], repeat=MAX_LENGTHS):
length = sum(lengths)
splits = list(lengths)[:-1]
if not length in SPLITS:
SPLITS[length] = set()
for split in np.cumsum(splits):
if split > 0.0 and split < length:
SPLITS[length].add(split)
NICE_LENGTHS = list(SPLITS.keys())
NICE_LENGTHS.sort()
class Point(namedtuple('Point', ['x', 'y'])):
'''
Point class...
'''
_epsilon = EPSILON
_format_str = '({:>6.03f},{:>6.03f})'
def __repr__(self):
return self._format_str.format(self.x, self.y)
def __eq__(self, other):
return ( abs(self.x - other.x) < Point._epsilon and
abs(self.y - other.y) < Point._epsilon )
def __hash__(self):
# return always the same hash, forcing dict and set always
# to use __eq__
return 0
def set_epsilon(eps):
Point._epsilon = eps
@property
def length(self):
return np.sqrt(self.x ** 2 + self.y ** 2)
def __add__(self, other):
return Point( self.x + other.x,
self.y + other.y )
def __sub__(self, other):
return Point( self.x - other.x,
self.y - other.y )
def __mul__(self, factor):
return Point( self.x * factor, self.y * factor)
def distance(self, other):
return (self - other).length
def dot_product(self, other):
return self.x * other.x + self.y * other.y
def cross_product(self, other):
return self.x * other.y - self.y * other.x
class Line(namedtuple('Line', ['p1', 'p2'])):
_format_str = '{} → {}'
def __repr__(self):
return self._format_str.format(repr(self.p1), repr(self.p2))
def __eq__(self, other):
return ( (self.p1, self.p2) == (other.p1, other.p2)
or (self.p1, self.p2) == (other.p2, other.p1) )
def __hash__(self):
# return always the same hash, forcing dict and set always
# to use __eq__
return 0
@property
def length(self):
return (self.p2 - self.p1).length
def angle(self, other=None):
if not other:
other = Line(Point(0.0, 0.0), Point(1.0, 0.0))
v1 = self.p2 - self.p1
v2 = other.p2 - other.p1
l1 = v1.length
l2 = v2.length
if l1 > 0.0 and l2 > 0.0:
val = v1.dot_product(v2) / (l1 * l2)
val = min( 1.0, val)
val = max(-1.0, val)
phi = np.arccos (val)
return 180 * phi / np.pi
else:
return None
def point_along(self, distance):
vect = (self.p2 - self.p1)
vect = vect * (1.0 / vect.length)
return self.p1 + vect * distance
class Triangle(namedtuple('Triangle', ['p1', 'p2', 'p3'])):
_format_str = '{} ᐊ {} ᐊ {}'
def __repr__(self):
return self._format_str.format(repr(self.p1),
repr(self.p2),
repr(self.p3),)
def __eq__(self, other):
return ( self.p1 in other
and self.p2 in other
and self.p3 in other)
def __hash__(self):
# return always the same hash, forcing dict and set always
# to use __eq__
return 0
@property
def center(self):
third = 1.0 / 3.0
return self.p1 * third + self.p2 * third + self.p3 * third
def is_inside(self, point):
raise NotImplementedError
def is_neighbour(self, other):
'''
checks if other triangle is a neighbour, ie. if it has
two mutual corner points
'''
count = 0
if other.p1 in self: count += 1
if other.p2 in self: count += 1
if other.p3 in self: count += 1
return count == 2 #and not self.is_inside(other.center)
class Piece(namedtuple('PieceBase', ['corners', 'triangles'])):
_format_str = 'Piece:\n{}\n{}'
def __init__(self, corners, triangles):
pass
def __repr__(self):
return self._format_str.format(repr(self.corners),
repr(self.triangles))
def __eq__(self, other):
return set(self) == set(other)
def is_inside(self, test_point):
N = len(self.corners)
cross_products = []
for i in range(N):
p1 = self.corners[i]
p2 = self.corners[(i+1) % N]
v1 = p2 - p1
v2 = test_point - p1
cross_products.append(v1.cross_product(v2))
pos = [c >= 0.0 for c in cross_products]
neg = [c <= 0.0 for c in cross_products]
return all(pos) or all(neg)
def ouside_triangles(self, triangles):
'''
returns the triangles which center is outside this piece
'''
return [t for t in triangles if not self.is_inside(t.center)]
class Tangram():
def __init__(self, filename):
self.set_image(filename)
self.set_gray()
self.set_scale()
self.set_height()
self.set_up_plot()
def set_image(self, filename):
self.image = cv2.imread(filename)
def set_gray(self):
self.gray = cv2.cvtColor(self.image, cv2.COLOR_BGR2GRAY)
self.blurred = cv2.blur(self.gray, (5,5))
def set_scale(self):
# background is 255 in our case, we count the none background
# pixels, this correspons to the 4 x 4 = 16 tangram surface
mask = self.gray < 250
mask.ravel()
pixels = np.sum(mask)
self.scale = np.sqrt(pixels / 16.0)
def set_height(self):
self.height = self.gray.shape[1]
def get_corners(self):
points = cv2.goodFeaturesToTrack(
self.gray,
maxCorners = 100,
qualityLevel = 0.01,
minDistance = 5,
)
points = points[:,0,:] # re-arange a bit
return [self.to_tangram_coor(Point(*p)) for p in points]
def to_tangram_coor(self, point):
ix, iy = point.x, point.y
tx = ix / self.scale
ty = (self.height - iy) / self.scale
return Point(tx, ty)
def to_image_coor(self, point):
tx, ty = point.x, point.y
ix = tx * self.scale
iy = self.height - ty * self.scale
return Point(int(ix), int(iy))
def valid_value_at(self, point):
'''
check if the point is in tangram and not in the background
'''
point = self.to_image_coor(point)
value = self.blurred[point.y, point.x]
return value != 255
def set_up_plot(self):
'''
create a plot and add some stuff to it
'''
# set matplotlib up,... interactive, delete old plots
plt.ion()
plt.close('all')
self.fig, self.axes = plt.subplots(ncols=5,
nrows=2,
figsize=(20,10))
self.axes = self.axes.flatten()
self.axes[ 0].set_title('original image')
self.axes[ 1].set_title('initial points & edges')
self.axes[ 2].set_title('all points')
self.axes[ 3].set_title('all triangles')
self.axes[ 4].set_title('solution')
self.axes[ 5].set_title('big triangles')
self.axes[ 6].set_title('squares')
self.axes[ 7].set_title('medium triangles')
self.axes[ 8].set_title('paralleograms')
self.axes[ 9].set_title('small triangles')
img = self.gray.copy()
img = cv2.blur(img, (3,3))
self.axes[0].imshow(self.image)
self.axes[0].axis('off')
for i in range(1,10):
self.axes[i].imshow(img, cmap='gray', vmin=-200)
self.axes[i].axis('off')
plt.subplots_adjust(left=0.02, right=0.98,
top=0.98, bottom=0.02)
def annotate(self, plot_no, ix, iy, text):
ax = self.axes[plot_no]
ax.annotate(text,
xy=(ix, iy),
xytext=(-3, 5),
textcoords='offset points',
ha='right',
va='bottom' )
def add_points_to_plot(self, plot_no, set_of_points, **kwargs):
'''
Add point to the a plot.
Formatting can be done with the *kwargs*
'''
ax = self.axes[plot_no]
for i, point in enumerate(set_of_points):
ix, iy = self.to_image_coor(point)
ax.plot(ix, iy, **kwargs)
self.annotate(plot_no, ix, iy, str(i))
def add_lines_to_plot(self, plot_no, set_of_lines, **kwargs):
ax = self.axes[plot_no]
for line in set_of_lines:
p1, p2 = line
ix1, iy1 = self.to_image_coor(p1)
ix2, iy2 = self.to_image_coor(p2)
ax.plot([ix1, ix2], [iy1, iy2], **kwargs)
def add_triangles_to_plot(self, plot_no, list_of_triangles, ** kwargs):
set_of_lines = set()
for i, triangle in enumerate(list_of_triangles):
p1, p2, p3 = triangle
set_of_lines.add(Line(p1, p2))
set_of_lines.add(Line(p2, p3))
set_of_lines.add(Line(p3, p1))
ix, iy = self.to_image_coor(triangle.center)
self.annotate(plot_no, ix, iy, str(i))
self.add_lines_to_plot(plot_no, set_of_lines, **kwargs)
def add_piece_to_plot(self, plot_no, piece, **kwargs):
list_of_points = list(piece.corners)
list_of_points.append(list_of_points[0])
N = len(list_of_points)
set_of_lines = set()
for i in range(N - 1):
p1 = list_of_points[i]
p2 = list_of_points[i+1]
set_of_lines.add(Line(p1, p2))
self.add_lines_to_plot(plot_no, set_of_lines, **kwargs)
def add_pieces_to_plot(self, plot_no, pieces, **kwargs):
for piece in pieces:
self.add_piece_to_plot(plot_no, piece, **kwargs)
class TangramSolver():
def __init__(self, filename = None):
self.t = Tangram(filename)
def solve(self):
points = set(self.t.get_corners())
edges = set(self.find_edges(points))
self.t.add_lines_to_plot(1, edges, lw=1, color='r')
self.t.add_points_to_plot(1, points, marker='o', ms=5, color='k')
for repeat in range(FIND_REPEATS):
points = points.union(self.find_more_points(edges))
edges = set(self.find_edges(points))
point_neighbours = self.find_sq2_neighbours(points)
triangles = self.find_triangles(point_neighbours)
neighbours = self.find_triangle_neighbours(triangles)
self.t.add_points_to_plot(2, points, marker='o', color='k')
self.t.add_triangles_to_plot(3, triangles, lw=1, color='k')
big_triangles = self.find_big_triangles (triangles, neighbours)
squares = self.find_squares (triangles, neighbours)
medium_triangles = self.find_medium_triangles(triangles, neighbours)
parallelograms = self.find_parallelograms (triangles, neighbours)
small_triangles = self.find_small_triangles (triangles, neighbours)
# plot some stuff...
for plotno, color, pieces in [ (5, 'red', big_triangles),
(6, 'yellow', squares),
(7, 'blue', medium_triangles),
(8, 'olivedrab', parallelograms),
(9, 'purple', small_triangles), ]:
self.t.add_pieces_to_plot(plotno, pieces, color=color, lw=2)
# here starts the fun
for p1 in big_triangles:
leftovers1 = p1.ouside_triangles(triangles)
for p2 in self.reduce_pieces(leftovers1, big_triangles):
leftovers2 = p2.ouside_triangles(leftovers1)
for p3 in self.reduce_pieces(leftovers2, squares):
leftovers3 = p3.ouside_triangles(leftovers2)
for p4 in self.reduce_pieces(leftovers3, medium_triangles):
leftovers4 = p4.ouside_triangles(leftovers3)
for p5 in self.reduce_pieces(leftovers4, parallelograms):
leftovers5 = p5.ouside_triangles(leftovers4)
for p6 in self.reduce_pieces(leftovers5, small_triangles):
leftovers6 = p6.ouside_triangles(leftovers5)
for p7 in self.reduce_pieces(leftovers6, small_triangles):
leftovers7 = p7.ouside_triangles(leftovers6)
if len(leftovers7) == 0:
print('Succes')
good_pieces = [p1, p2, p3, p4, p5, p6, p7]
self.t.add_pieces_to_plot(4, good_pieces, color='k', lw=2)
return
print('Failed')
return
def inside_tangram(self, line):
N = 20 # oops, magic number..., anyway... :
for i in range(1, N-1):
line_length = line.length
point = line.point_along(line_length * i / N )
if not self.t.valid_value_at(point):
return False
return True
def almost_equal(self, a, b, eps=EPSILON):
return abs(a-b) < eps
def is_nice_lenght(self, length, eps=EPSILON):
for nice_length in NICE_LENGTHS:
if abs(length - nice_length) < eps:
return True
return False
def is_nice_angle(self, angle, eps=EPSILON_ANGLE):
for nice_angle in [-180, -135, -90, -45, 45, 90, 135, 180]:
if abs(angle - nice_angle) < eps:
return True
return False
def is_nice_triangle_angle(self, angle, eps=EPSILON_ANGLE):
for nice_angle in [-90, -45, 45, 90]:
if abs(angle - nice_angle) < eps:
return True
return False
def is_nice_edge(self, angle, edge):
return ( self.is_nice_angle(angle)
and self.is_nice_lenght(edge.length)
and self.inside_tangram(edge) )
def find_edges(self, points):
edges = set()
for center, p1, p2 in permutations(points, r=3):
edge1 = Line(center, p1)
edge2 = Line(center, p2)
angle = edge1.angle(edge2)
if self.is_nice_edge(angle, edge1):
edges.add(edge1)
return edges
def find_more_points(self, edges, eps=EPSILON):
results = set()
for edge in edges:
for length, splits in SPLITS.items():
if self.almost_equal(length, edge.length, eps):
for split in splits:
results.add(edge.point_along(split))
return results
def triangle_inside_tangram(self, triangle, eps=EPSILON):
'''
checks some points inside the triangle to be inside
the tangram
'''
global t # ugly, i know...
p1, p2, p3 = triangle
test_points = [
p1 + ((p2 * 0.5 + p3 * 0.5) - p1) * 0.2,
p2 + ((p3 * 0.5 + p1 * 0.5) - p2) * 0.2,
p3 + ((p1 * 0.5 + p2 * 0.5) - p3) * 0.2,
p1 + ((p2 * 0.5 + p3 * 0.5) - p1) * 0.8,
p2 + ((p3 * 0.5 + p1 * 0.5) - p2) * 0.8,
p3 + ((p1 * 0.5 + p2 * 0.5) - p3) * 0.8 ]
return all([self.t.valid_value_at(tp) for tp in test_points])
def reduce_neighbours(self, triangles, all_neighbours):
neighbours = {}
for t in triangles:
neighbours[t] = [n for n in all_neighbours[t] if n in triangles]
return neighbours
def reduce_pieces(self, triangles, pieces):
return [ p
for p in pieces
if set(p.triangles).issubset(set(triangles)) ]
def find_sq2_neighbours(self, points, eps=EPSILON):
'''
Returns a dict with for every point a list with neighbouring
points at roughly a SQ2 distance
'''
sq2_neighbours = {}
for p1 in points:
neighbours = []
for p2 in points:
if self.almost_equal(Line(p1, p2).length, SQ2, eps):
neighbours.append(p2)
sq2_neighbours[p1] = neighbours
return sq2_neighbours
def find_triangles(self, sq2_neighbours, eps=EPSILON):
triangles = set()
for p1, neighbours in sq2_neighbours.items():
for p2, p3 in permutations(neighbours, 2):
if self.almost_equal(Line(p2, p3).length, TWO, eps):
triangle = Triangle(p1, p2, p3)
if self.triangle_inside_tangram(triangle):
triangles.add(triangle)
return triangles
def find_triangle_neighbours(self, triangles):
neighbours = {}
for t1 in triangles:
neighbours[t1] = [ t2
for t2 in triangles
if t1.is_neighbour(t2) ]
return neighbours
def find_big_triangles(self, triangles, neighbours):
'''
top1
/\
/ \
/_t1_\
/\ t2 /\
/ \ / \
/_t3_\/_t4_\
c1 top2 c2
'''
big_triangles = []
for t1 in triangles:
top1 = t1[0]
for t2 in neighbours[t1]:
top2 = t2[0]
if not self.almost_equal(Line(top1, top2).length, TWO):
continue
# now find two neighbours of this neighbour
for t3, t4 in permutations(neighbours[t2], r=2):
if t3 == t1 or t4 == t1:
continue
p31 = t3[1]
p32 = t3[2]
p41 = t4[1]
p42 = t4[2]
c1, c2 = None, None
if self.almost_equal(Line(p31, p41).length, FOUR):
c1, c2 = p31, p41
if self.almost_equal(Line(p31, p42).length, FOUR):
c1, c2 = p31, p42
if self.almost_equal(Line(p32, p41).length, FOUR):
c1, c2 = p32, p41
if self.almost_equal(Line(p32, p42).length, FOUR):
c1, c2 = p32, p42
if c1 and c2:
corners = (top1, c1, c2)
triangles = (t1, t2, t3, t4)
big_triangles.append(Piece(corners, triangles))
break
return big_triangles
def find_squares(self, triangles, neighbours):
'''
top1
/\
/ \
/_t1_\
\ t2 /
\ /
\/
top2
'''
squares = []
for t1 in triangles:
top1 = t1[0]
for t2 in neighbours[t1]:
top2 = t2[0]
if self.almost_equal(Line(top1, top2).length, TWO):
corners = (top1, t1[1], top2, t1[2])
triangles = (t1, t2)
squares.append(Piece(corners, triangles))
break
return squares
def find_medium_triangles(self, triangles, neighbours):
medium_triangles = []
for t1 in triangles:
top1 = t1[0]
for t2 in neighbours[t1]:
top2 = t2[0]
if top1 != top2:
continue
# now see if they are a medium square...
for p1a, p1b, p2a, p2b in ((t1[1], t1[2], t2[1], t2[2]),
(t1[1], t1[2], t2[2], t2[1]),
(t1[2], t1[1], t2[1], t2[2]),
(t1[2], t1[1], t2[2], t2[1]) ):
if ( p1a == p2a
and self.almost_equal(Line(p1b, p2b).length, 2 * SQ2)):
corners = (p1a, p1b, p2b)
triangles = (t1, t2)
medium_triangles.append(Piece(corners, triangles))
break
return medium_triangles
def find_parallelograms(self, triangles, neighbours):
parallelograms = []
for t1 in triangles:
for t2 in neighbours[t1]:
st1 = set(t1)
st2 = set(t2)
opposites = st1.symmetric_difference(st2)
both = st1.intersection(st2)
p1, p2 = opposites
if self.almost_equal(Line(p1, p2).length, SQ10):
b1, b2 = both
corners = (p1, b1, p2,b2)
triangles = (t1, t2)
parallelograms.append(Piece(corners, triangles))
break
return parallelograms
def find_small_triangles(self, triangles, neighbours):
small_triangles = []
for t1 in triangles:
small_triangles.append(Piece(tuple(t1), [t1]))
return small_triangles
def get_random_image():
'''
return a random tangram image (file name), taken from:
http://www.supercoloring.com/puzzle-games/
stored in directory 'source_images', they are 480x480 pixels .png
images, with a white background and tangram images in various
colors.
'''
images = glob('source_images/*.png')
return np.random.choice(images)
def main():
filename = get_random_image()
#filename = 'source_images/521-tangram-leopard-shape-puzzle-game.png'
filename = 'source_images/116-tangram-cat-shape-puzzle-game.png'
print(filename)
ts = TangramSolver(filename)
ts.solve()
return ts
if __name__ == '__main__':
Point.set_epsilon(EPSILON)
ts = main()
Piecehave an empty__init__()? \$\endgroup\$