Jakiś czas temu trafiłem na zagadkę następującą:
Znajomy zaprosił mnie na strzelnicę. Jednak zamiast tradycyjnych tarcz, wszystkie tarcze na jego strzelnicy były tarczami apollońskimi o symetrii D2 (a więc dwa duże koła o krzywiźnie 2 wzdłuż jednej średnicy, dwa mniejsze o krzywiźnie 3 wzdłuż prostopadłej średnicy i tak dalej).
Co więcej, były to tarcze rekurencyjne - a więc nie tylko miały nieskończenie wiele coraz mniejszych kół, ale dodatkowo każde koło było samo w sobie tarczą apollońską (przeskalowaną w dół, żeby zmieściła się w tym kole).
Czyli mamy dwie nieskończoności: raz, pojedyncza tarcza apollońska sama w sobie jest fraktalem (nieskończenie wiele kół), a dwa, każde z tych nieskończenie wielu kół zawiera całą nieskończoną tarczę apollońską.
Coś w ten deseń:
No i teraz pytanie: zakładając, że liczba punktów uzyskanych za każdy strzał jest równa sumie pól wszystkich (nieskończenie wielu) kół zawierających punkt, w który trafiliśmy, należy wykombinować jaka jest maksymalna możliwa liczba punktów za jeden strzał. Przyjmujemy, że promień tarczy R=1.
Wbrew pozorom, chociaż mamy tu dwie zagnieżdżone nieskończoności, zagadka jest dość prosta (rozwiązanie pozostawiam Czytelnikowi).
Najtrudniejszy - przynajmniej dla mnie - był proces przekonania elemelka, żeby mi napisał kod w Pythonie, który generuje powyższy obrazek 🙂
Skoro już napisał, to się podzielę:
import math
import matplotlib.pyplot as plt
from matplotlib import cm
from dataclasses import dataclass, field
from typing import List, Optional
# ============================================================
# Basic circle
# ============================================================
@dataclass
class Circle:
center: complex
radius: float
curvature: float = 0.0
parent: Optional["Circle"] = None
children: List["Circle"] = field(default_factory=list)
depth: int = 0 # nesting level
@property
def x(self): return self.center.real
@property
def y(self): return self.center.imag
# ============================================================
# Math utilities (Descartes + simple geometry)
# ============================================================
class GasketMath:
@staticmethod
def descartes_curvatures(k1, k2, k3):
s = k1 + k2 + k3
inner = k1*k2 + k2*k3 + k3*k1
inner = max(inner, 0.0)
t = 2.0 * math.sqrt(inner)
return s + t, s - t
@staticmethod
def tangency_distance(k1, k4, r1, r4):
if k1 > 0 and k4 > 0:
return r1 + r4
else:
return abs(r1 - r4)
@staticmethod
def circle_intersections(z1, r1, z2, r2, eps=1e-12):
d = abs(z2 - z1)
if d < eps:
return []
if d > r1 + r2 + eps:
return []
if d < abs(r1 - r2) - eps:
return []
a = (r1*r1 - r2*r2 + d*d) / (2*d)
h2 = r1*r1 - a*a
if h2 < -eps:
return []
h = math.sqrt(max(h2, 0.0))
direction = (z2 - z1) / d
p_mid = z1 + a * direction
if h < eps:
return [p_mid]
offset = h * direction * 1j
return [p_mid + offset, p_mid - offset]
# ============================================================
# (-1,2,2,3) seed in unit disk
# ============================================================
class Minus1_2_2_Seed:
@staticmethod
def canonical_circles():
outer = Circle(0+0j, 1.0, -1.0)
c1 = Circle(-0.5+0j, 0.5, 2.0)
c2 = Circle( 0.5+0j, 0.5, 2.0)
c3 = Circle( 0+2/3j, 1/3, 3.0)
return [outer, c1, c2, c3]
# ============================================================
# Local gasket generator in the unit disk
# ============================================================
class LocalGasketGenerator:
"""
Builds the (-1,2,2,3) gasket in the unit disk, down to
circles of radius >= min_local_radius. Returns all *inner*
circles (outer excluded).
"""
def __init__(self, math_engine, seed):
self.m = math_engine
self.seed = seed
def generate(self, min_local_radius: float) -> List[Circle]:
base = self.seed.canonical_circles()
outer = base[0]
circles = base[:]
inner = [circles[1], circles[2], circles[3]]
sig_to_idx = {}
def sig(c: Circle):
return (round(c.center.real, 6),
round(c.center.imag, 6),
round(c.radius, 6))
for idx, c in enumerate(circles):
sig_to_idx[sig(c)] = idx
triples = set()
for i in range(4):
for j in range(i + 1, 4):
for k in range(j + 1, 4):
triples.add((i, j, k))
queue = list(triples)
while queue:
i, j, k = queue.pop(0)
c1, c2, c3 = circles[i], circles[j], circles[k]
k1, k2, k3 = c1.curvature, c2.curvature, c3.curvature
k4a, k4b = self.m.descartes_curvatures(k1, k2, k3)
for k4 in (k4a, k4b):
if k4 <= 0:
continue
r4 = 1.0 / k4
if r4 < min_local_radius:
continue
d1 = self.m.tangency_distance(k1, k4, c1.radius, r4)
d2 = self.m.tangency_distance(k2, k4, c2.radius, r4)
pts = self.m.circle_intersections(c1.center, d1,
c2.center, d2)
if not pts:
continue
for z4 in pts:
d3 = self.m.tangency_distance(k3, k4, c3.radius, r4)
if abs(abs(z4 - c3.center) - d3) > 1e-6 * max(1.0, k4):
continue
if abs(z4) + r4 > 1.0 + 1e-6:
continue
cand = Circle(z4, r4, k4)
s = sig(cand)
if s in sig_to_idx:
continue
idx_new = len(circles)
circles.append(cand)
sig_to_idx[s] = idx_new
inner.append(cand)
for a, b in ((i, j), (i, k), (j, k)):
triple = tuple(sorted((a, b, idx_new)))
if triple not in triples:
triples.add(triple)
queue.append(triple)
return
# ============================================================
# Recursive nested generator (clone + scale)
# ============================================================
class NestedGasketGenerator:
def __init__(self, unit_gasket: List[Circle],
img_size: int = 2000,
min_pixel_radius: float = 5.0):
self.unit_gasket = unit_gasket
self.img_size = img_size
self.min_pixel_radius = min_pixel_radius
self.scale_px = img_size / 2.0
self.global_circles: List[Circle] = []
def _recurse(self, parent: Circle):
for lc in self.unit_gasket:
g_radius = parent.radius * lc.radius
if g_radius * self.scale_px < self.min_pixel_radius:
continue
g_center = parent.center + parent.radius * lc.center
child = Circle(
g_center,
g_radius,
curvature=1.0 / g_radius,
parent=parent,
depth=parent.depth + 1
)
parent.children.append(child)
self.global_circles.append(child)
self._recurse(child)
def generate(self) -> List[Circle]:
root = Circle(0+0j, 1.0, -1.0, depth=0)
self.global_circles = [root]
self._recurse(root)
return self.global_circles
# ============================================================
# Renderer
# ============================================================
def render(circles: List[Circle], img_size=2000):
fig, ax = plt.subplots(figsize=(6, 6))
ax.set_aspect("equal")
ax.set_xlim(-1, 1)
ax.set_ylim(-1, 1)
ax.axis("off")
# sort so big circles are drawn first
circles_sorted = sorted(circles, key=lambda c: c.radius, reverse=True)
depths =
max_depth = max(depths) if depths else 1
for c in circles_sorted:
ax.add_patch(plt.Circle(
(c.x, c.y),
c.radius,
fill=False,
linewidth=0.4
))
plt.show()
# ============================================================
# Main
# ============================================================
if __name__ == "__main__":
IMG_SIZE = 2200
MIN_PIXEL_RADIUS = 50
gm = GasketMath()
seed = Minus1_2_2_Seed()
local_gen = LocalGasketGenerator(gm, seed)
min_local_radius = MIN_PIXEL_RADIUS / (IMG_SIZE / 2.0)
unit_gasket = local_gen.generate(min_local_radius)
print("Unit gasket circles:", len(unit_gasket))
nested_gen = NestedGasketGenerator(
unit_gasket,
img_size=IMG_SIZE,
min_pixel_radius=MIN_PIXEL_RADIUS
)
all_circles = nested_gen.generate()
print("Total circles:", len(all_circles))
render(all_circles, img_size=IMG_SIZE)
Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]
Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.