There are only 21 ways to place regular polygons in gapless tilings. The point where the polygons meet is called a vertex. Vertices are named by the polygons meeting there. For instance, the vertex where four squares meet is 4.4.4.4. In this post, I will make code to find and draw all possible vertices.
Regular polygons
A regular polygon has $n$ sides. The interior angle $\alpha$ between two adjacent sides is \begin{equation} \alpha=\frac{n-2}{2n}. \end{equation} The turning angle $\beta=1/n$ of a polygon is the angle to the centre between two adjacent points. For simplicity, I write angles as fractions of a complete turn. Multiply by $2\pi$ or $360^\circ$ to get radians or degrees.
The pointiest polygon is the regular triangle with $\alpha=1/6$. When increasing $n$, $\alpha$ increases towards $1/2$.
Searching for vertices
For a tiling to be gapless, the sum of interior angles $\alpha$ at a vertex must be 1. Thus, the complete set of vertices can be found by finding all sets $v_i$ so that: \begin{equation} \sum_{n_j\in v_i} \frac{n_j-2}{2n_j} = 1\,. \end{equation}
Before searching, it helps to have ranges on the possible number of polygons $m$ and sides $n$ in $v_i$. The count $m$ must be larger than 2, as no two regular polygons can add up to 1. Furthermore, the highest $m$ is six as 3.3.3.3.3.3 as $\sum_{n \in 3.3.3.3.3.3} \alpha=6\cdot1/6=1$. For $m=6$ this is the only possible vertex.
For $m=3$, the two shape combination leaving the smallest angle $\alpha\lt1/2$ is 3 and 7, as that 3 and 6 leaves exactly $\alpha=1/2$, which can’t be a polygon. The remaining angle then is \begin{equation} \alpha=1-\left(\alpha_3+\alpha_2\right)= 1-\left(\frac{3-2}{2\cdot3}+ \frac{7-2}{2\cdot7}\right)= \frac{10}{21}\,, \end{equation} and with $(n-2)/(2n)=10/21$ we get n=42. Similarly for $m=4$, 3.3.4 leaves $\alpha\le1-(2/6+2/8)=5/12$, corresponding to $n=12$. Finally for $m=5$, 3.3.3.3 leaves $\alpha\le1-(4/6)=1/3$, corresponding to $n_5=6$.
In summary:
\[
m:3 \quad 3\le n\le 42
\]
\[
m:4 \quad 3\le n\le 12
\]
\[
m:5 \quad 3\le n\le 6
\]
\[
m:6 \quad n=3
\]
All possible vertices are found by searching for combinations of $m$ elements with $n$ inside the constrained range. Note that this brute force approach will trivial clones of vertices in the form of rotations and mirror images. Moreover, there are some cases of different vertices with the same polygon content. Thus, I first generate (sorted) combinations with replacements of polygons for each $m$. If a set sums to 1, I yield permutations not already stored as a mirror or rotation.
Python search implementation
For the search I only rely on python 3.8+ and its built in libraries. You don’t need to read the code unless you’re interested in the deeper details of how I find vertices. There are likely more efficient solutions, but I think this works good enough for me :)
Click to expand the python code…
Imports:
from itertools import combinations_with_replacement, permutations
from fractions import Fraction as F
Constraints
# Range of polygon count at vertex
m_min = 3
m_max = 6
# Range of n-gon n at vertex
n_min = 3
n_max = [42, 12, 6, 3]
Fucntions
def n_gon(n: str) -> F:
"""Make n-gon interior angle as fraction of full turn"""
return F(n-2, 2*n)
def rotrev(s) -> tuple[int]:
"""Generate all rotations and mirrors of s"""
d = deque(s)
for i in range(len(d)):
d.rotate(1)
yield tuple(d)
yield tuple(reversed(d))
def find_vertices() -> list[tuple[int]]:
"""Find vertices"""
found = []
# Loop over number of n-gons
for i, m in enumerate(range(m_min, m_max+1)):
# Loop over all possible vertex candidates
for comb in combinations_with_replacement(range(m_min, n_max[m-n_min]+1), r=m):
# Only consider proper vertices
if sum(n_gon(c) for c in comb) != 1:
continue
# Add permutations
for p in permutations(comb):
# Reject rotated or reversed forms
if any(d in found for d in rotrev(p)):
continue
found.append(p)
return found
Running the search takes less than a seconds on my laptop
vertices = find_vertices()
Search result
This table was made processing the resulting vertex list. Here $m$ still is the number of polygons, each integer column the counts for a particular shape, and $u$ the number of unique shapes.
| vertex | $m$ | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 12 | 15 | 18 | 20 | 24 | 42 | $u$ |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3.7.42 | 3 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 3 |
| 3.8.24 | 3 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 3 |
| 3.9.18 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 3 |
| 3.10.15 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 3 |
| 3.12.12 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 2 |
| 4.5.20 | 3 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 3 |
| 4.6.12 | 3 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 3 |
| 4.8.8 | 3 | 0 | 1 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 5.5.10 | 3 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 6.6.6 | 3 | 0 | 0 | 0 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 3.3.4.12 | 4 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 3 |
| 3.4.3.12 | 4 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 3 |
| 3.3.6.6 | 4 | 2 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 3.6.3.6 | 4 | 2 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 3.4.4.6 | 4 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| 3.4.6.4 | 4 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 |
| 4.4.4.4 | 4 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 3.3.3.3.6 | 5 | 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 3.3.3.4.4 | 5 | 3 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 3.3.4.3.4 | 5 | 3 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 |
| 3.3.3.3.3.3 | 6 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| total | - | 15 | 10 | 2 | 7 | 1 | 2 | 1 | 2 | 4 | 1 | 1 | 1 | 1 | 1 | - |
Noteworthy observations
- There are a total of 21 vertices (10 $m=3$, 7 $m=4$, 3 $m=5$, 1 $m=6$)
- There are 1-3 polygon types in a vertex (10 $u=3$, 8 $u=2$, 3 $u=1$)
- The three single polygon type vertices are triangles, squares, and hexagons - the only three ways to tile the plane with a single polygon type!
- Only 3-, 4-, 5-, 6-, 8-, 10- and 12-gons occur in more than one vertex
- 5 and 10 only ever occurr together
- 15 vertices contains triangles, 10 squares, 7 hexagons, and 4 dodecagons
Below is the code I used to generate the table and insights
Click to expand the python code…
Imports (in addition to above code)
import pandas as pd
Functions
def vertex_str(vtx: tuple[int]) -> str:
"""Make vertex notation from ints."""
return '.'.join(map(str, vtx))
def make_df(vertices: list[tuple[int]]) -> pd.DataFrame:
"""Make data frame with vertex summary."""
vertices = find_vertices()
ngons = {i for j in vertices for i in j}
df = pd.DataFrame({"m": len(f), "vertex": f} for f in vertices)
for ngon in {i for j in vertices for i in j}:
df[ngon] = df["vertex"].apply(lambda x: list(x).count(ngon))
df["vertex"] = df["vertex"].apply(vertex_str)
df = df.set_index("vertex")[["m"]+sorted(list(ngons))]
df["u"] = (df[list(ngons)]>0).sum(axis=1)
df.loc["n_vertices"]=(df>0).sum()
return df
Running
df=make_df(vertices)
print(df)
print(df[:-1]["m"].value_counts())
print(df[:-1]["u"].value_counts())
Drawing vertices
To draw vertices correctly, I define a polygon by $n$ and one side. Swapping the side start and end points mirrors the polygon.
Click to expand the python code…
Imports
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
from matplotlib.collections import PatchCollection
Functions
def make_patch(points: np.ndarray, ax, fc="white"):
"""Helper to draw polygon patch to ax"""
ax.add_collection(
PatchCollection([mpatches.Polygon(points)], fc=fc, ec='k',lw=1)
)
def coords(n:int, line: np.ndarray) -> np.ndarray:
"""
Args:
* n (int) - n in n-gon
* line (np.array) - ((x0,y0), (x1,y1)) line segment
Returns:
np.ndarray: shape (n, 2) x,y coordinate pairs
"""
d = np.diff(line.T, axis=1)
r = np.linalg.norm(d)
a = np.arange(n)*(
np.pi-np.pi*2*float(n_gon(n)))+\
np.arctan2(d[0], d[1])
p = line[0][:, None]
return np.hstack(((p+np.cumsum(
r*np.array([np.sin(a), np.cos(a)]),
axis=1)), p)).T
Colors
colors = {
3: "royalblue",
4: "orangered",
5: "hotpink",
6: "gold",
7: "magenta",
8: "darkorange",
9: "yellowgreen",
10: "lightsteelblue",
12: "limegreen",
15: "lightcoral",
18: "khaki",
20: "orchid",
24: "plum",
42: "palegreen",
}
Running
fig, axs = plt.subplots(5,5,figsize=(10,10))
axs = axs.flatten() # all subplits as list
g0 = np.array([[1,0],[0,0]]) # line to start with
for i, vertex in enumerate(vertices):
ax = axs[i]
ps = [] # save coordinates for bounding box
ax.plot(0, 0,"ko", ms=4) # Draw vertex
# Add polygons
for gon in vertex:
p = coords(gon, g0)
ps.extend(p.tolist())
make_patch(p, ax, colors[gon])
g0 = p[:2][::-1] # move starting line for next iteration
# Bounding box
xmin, ymin = np.min(ps, axis=0)*1.05
xmax, ymax = np.max(ps, axis=0)*1.05
ax.set(title=vertex_str(vertex), xlim=(xmin,xmax), ylim=(ymin,ymax));
# Ensure equal aspect and no axes for all plots
for i in range(i, 5*5):
ax = axs[i]
ax.set_aspect('equal', adjustable='box')
ax.axis('off')
# Save result
fig.savefig("vertices.png", facecolor='white', transparent=False, bbox_inches="tight")
