アステカダイヤモンドのビジュアライザ
使い方・計算量
タイリング
アステカダイヤモンドのドミノタイリング及び、色付けを行うコードです。 当初は非交差経路を構成してから、それに応じてタイリングを行っていましたが、ドミノシャッフリングを用いた方法へと変更しました。
タイリング + 色付け
用途: 北極圏定理の視覚化
計算量: nをアステカダイヤモンドの次数として、 $O(n^3)$ です。
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
import random
def generate_aztec_diamond(n):
size = 2 * n
# 0: 空白(背景), 1: North(上), 2: South(下), 3: West(左), 4: East(右)
grid = np.zeros((size, size), dtype=int)
for k in range(1, n + 1):
current_parity = (k - 1) % 2
for r in range(size - 1):
for c in range(size - 1):
if (r + c) % 2 == current_parity:
if grid[r, c] == 2 and grid[r, c+1] == 2 and \
grid[r+1, c] == 1 and grid[r+1, c+1] == 1:
grid[r, c] = 0; grid[r, c+1] = 0
grid[r+1, c] = 0; grid[r+1, c+1] = 0
elif grid[r, c] == 4 and grid[r+1, c] == 4 and \
grid[r, c+1] == 3 and grid[r+1, c+1] == 3:
grid[r, c] = 0; grid[r+1, c] = 0
grid[r, c+1] = 0; grid[r+1, c+1] = 0
next_grid = np.zeros((size, size), dtype=int)
for r in range(size):
for c in range(size):
val = grid[r, c]
if val == 1: next_grid[r - 1, c] = 1
elif val == 2: next_grid[r + 1, c] = 2
elif val == 3: next_grid[r, c - 1] = 3
elif val == 4: next_grid[r, c + 1] = 4
grid = next_grid
for r in range(size - 1):
for c in range(size - 1):
if (r + c) % 2 == current_parity:
dr = r - n + 1
dc = c - n + 1
if abs(dr) + abs(dc) < k:
if grid[r, c] == 0 and grid[r+1, c] == 0 and \
grid[r, c+1] == 0 and grid[r+1, c+1] == 0:
if random.random() < 0.5:
grid[r, c] = 1; grid[r, c+1] = 1 # 上にNorth
grid[r+1, c] = 2; grid[r+1, c+1] = 2 # 下にSouth
else:
grid[r, c] = 3; grid[r+1, c] = 3 # 左にWest
grid[r, c+1] = 4; grid[r+1, c+1] = 4 # 右にEast
return grid
def plot_aztec_diamond(n):
grid = generate_aztec_diamond(n)
# 0:白, 1:赤, 2:青, 3:緑, 4:黄
cmap = ListedColormap(['#e1e9ee', '#FF595E', '#1982C4', '#8AC926', '#FFCA3A'])
plt.figure(figsize=(8, 8), facecolor='#e1e9ee')
plt.imshow(grid, cmap=cmap, interpolation='nearest')
plt.axis('off')
plt.show()
plot_aztec_diamond(100)非交差経路
タイリング + 色付け + 経路描画
用途: 北極圏定理の視覚化
計算量: nをアステカダイヤモンドの次数として、 $O(n^3)$ です。
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
import random
import matplotlib.patheffects as pe
def generate_aztec_diamond(n):
size = 2 * n
grid = np.zeros((size, size), dtype=int)
for k in range(1, n + 1):
current_parity = (k - 1) % 2
for r in range(size - 1):
for c in range(size - 1):
if (r + c) % 2 == current_parity:
if grid[r, c] == 2 and grid[r, c+1] == 2 and \
grid[r+1, c] == 1 and grid[r+1, c+1] == 1:
grid[r, c] = 0; grid[r, c+1] = 0
grid[r+1, c] = 0; grid[r+1, c+1] = 0
elif grid[r, c] == 4 and grid[r+1, c] == 4 and \
grid[r, c+1] == 3 and grid[r+1, c+1] == 3:
grid[r, c] = 0; grid[r+1, c] = 0
grid[r, c+1] = 0; grid[r+1, c+1] = 0
next_grid = np.zeros((size, size), dtype=int)
for r in range(size):
for c in range(size):
val = grid[r, c]
if val == 1: next_grid[r - 1, c] = 1
elif val == 2: next_grid[r + 1, c] = 2
elif val == 3: next_grid[r, c - 1] = 3
elif val == 4: next_grid[r, c + 1] = 4
grid = next_grid
for r in range(size - 1):
for c in range(size - 1):
if (r + c) % 2 == current_parity:
dr = r - n + 1
dc = c - n + 1
if abs(dr) + abs(dc) < k:
if grid[r, c] == 0 and grid[r+1, c] == 0 and \
grid[r, c+1] == 0 and grid[r+1, c+1] == 0:
if random.random() < 0.5:
grid[r, c] = 1; grid[r, c+1] = 1
grid[r+1, c] = 2; grid[r+1, c+1] = 2
else:
grid[r, c] = 3; grid[r+1, c] = 3
grid[r, c+1] = 4; grid[r+1, c+1] = 4
return grid
def get_non_intersecting_paths(grid, n):
size = 2 * n
paths = []
vertical_halves = np.zeros((size, size), dtype=int)
for c in range(size):
r = 0
while r < size:
if grid[r, c] == 3:
vertical_halves[r, c] = 1 # 上半分
vertical_halves[r+1, c] = -1 # 下半分
r += 2
else:
r += 1
r = 0
while r < size:
if grid[r, c] == 4:
vertical_halves[r, c] = 1 # 上半分
vertical_halves[r+1, c] = -1 # 下半分
r += 2
else:
r += 1
for i in range(n):
r = n + i
c = i
path_x = [c - 0.5]
path_y = [r]
while c < size:
if r < 0 or r >= size:
break
val = grid[r, c]
if val == 0:
break
elif val == 1 or val == 2:
path_x.append(c + 1.5)
path_y.append(r)
c += 2
elif val == 3 or val == 4:
half = vertical_halves[r, c]
if half == -1:
path_x.append(c + 0.5)
path_y.append(r - 1)
r -= 1
c += 1
elif half == 1:
path_x.append(c + 0.5)
path_y.append(r + 1)
r += 1
c += 1
else:
break
paths.append((path_x, path_y))
return paths
def plot_aztec_diamond_with_paths(n):
grid = generate_aztec_diamond(n)
paths = get_non_intersecting_paths(grid, n)
# 0:白, 1:赤, 2:青, 3:緑, 4:黄
cmap = ListedColormap(['#e1e9ee', '#FF595E', '#1982C4', '#8AC926', '#FFCA3A'])
plt.figure(figsize=(10, 10), facecolor='#e1e9ee')
plt.imshow(grid, cmap=cmap, interpolation='nearest')
for path_x, path_y in paths:
plt.plot(path_x, path_y,
color='#111111',
linewidth=1.8,
alpha=1.0,
path_effects=[pe.Stroke(linewidth=3.5, foreground='white'), pe.Normal()])
plt.axis('off')
plt.tight_layout()
plt.show()
plot_aztec_diamond_with_paths(25)出力結果
.png)
.png)