フラクタル・ジッタード・ボロノイ分割

興味深いボロノイのバリアントを見つけました。これは、各ボロノイセルに美しいフラクタル境界を与え、計算が非常に効率的です。自然界でもしばしばフラクタルな性質を持つ海岸線などに適しているようです。https://www.shadertoy.com/view/sfKSDw 説明しましょう。「ジッタード」ボロノイとは、無限のグリッドから始め、グリッドの各正方形にサイトと呼ばれるランダムな点を1つ選びます。次に、それらのサイトからボロノイ図を作成します。これはWorleyノイズと同じですが、距離を出力する代わりに、最も近い点の選択を出力し、平面を分割します。これは、ポイントごとに計算するのが非常に簡単であるという良い特性を持っています。ポイントpに対して、最も近い25個のグリッドセルを見つけ、それぞれのサイト（ハッシュ化された疑似乱数ジェネレーター経由）を見つけ、そしてあなたのポイントに最も近いものがどれかを見つけます。ボロノイ図を実際に構築したり、平面の無限のサイズを心配したりする必要はありません。私たちの新しい手順を数学的に説明します。 1) 再び、無限のグリッドの正方形から始め、PRNG（擬似乱数ジェネレーター）で各グリッドにサイトを選びます。これらはルート、レイヤー0のサイトです。 2) 新しいグリッドを作成し、サイズを半分にし、それらのためにレイヤー1のサイトを選びます。各レイヤー1サイトについて、その親サイト（最も近いサイトとして定義される）をレイヤー0で見つけます。 3) この手順を無期限に繰り返します。毎回、グリッドサイズを半分にし、上のレイヤーで親を見つけます。各サイトが属する分割は、親を上にたどって到達するルートサイトです。再帰すると、平面がサイトで満たされ、これは平面のほぼすべての場所での分割に拡張できます。しかし、実際にはこれをどのように計算するのでしょうか？無限のグリッドも無限の再帰も持つことはできません。さて、無限のグリッドは通常のジッタード・ボロノイと同様に扱うことができます。与えられたポイントpに対して、すべてのレベルで実際に意味のあるセルは固定数しかありません。無限の再帰については、明らかな解決策は、有限回数（ズームレベルに依存）のイテレーションを行い、最終レイヤーのボロノイ図を作成することです。これはフラクタル形状の良い近似になります。コードで見てみましょう。ループ終了条件を少しコードゴルフしました。 from functools import cache from math import sqrt # 各レイヤーのジッタード・ボロノイ def cell_size(layer): return 2 ** (-layer) @cache def site(layer, cell): """整数グリッドセル(x, y)に属するサイトを返します。 hash2は(layer, cell)に基づいて、[0, 1)の範囲の2つの疑似乱数を決定論的に返さなければなりません。 """ s = cell_size(layer) offset = hash2(layer, cell) return s * (cell + offset) def nearest_site(layer, p): """pに最も近いレイヤーiのサイトを見つけます。""" s = cell_size(layer) centre_cell = floor(p / s) best_cell = None best_site = None best_distance = infinity # 最も近い5x5のセルを検索すれば十分です: # より遠いセルは最も近いサイトを含むことはできません。 for dx in range(-2, 3): for dy in range(-2, 3): cell = centre_cell + (dx, dy) q = site(layer, cell) d = squared_distance(p, q) if d < best_distance: best_distance = d best_cell = cell best_site = q return best_cell, best_site # 親/ルート @cache def parent(layer, cell): """レイヤー`layer`のサイトの親を返します。""" return nearest_site(layer - 1, site(layer, cell))[0] @cache def root(layer, cell): """レイヤーのセルに関連付けられたレイヤー0のセルを返します。""" while layer > 0: cell = parent(layer, cell) layer -= 1 return cell def partition(p, depth): """フラクタル分割の有限深度近似。""" cell, _ = nearest_site(depth, p) return root(depth, cell) 1つのバリアントは、固定深度を持たず、早期停止条件を持つことです。ポイントpがレイヤーiのサイトに特に近い場合、停止し、そこから親をたどることができます。それはサイトに十分に近く、それ以降のすべてのレイヤーはそれに同意するでしょう。 def nearest_site_safe(layer, p, check_safe=False): """pに最も近いレイヤーiのサイトを見つけます。また、より細かいサイトのすべての可能なレイヤーiの祖先が同じルートを持つかどうかを判断します。もしそうなら、それ以上の再帰は結果を変えることはできません。""" s = cell_size(layer) centre_cell = floor(p / s) best_cell = None best_site = None best_distance = infinity # 任意のより深いレイヤーで選択されたサイトは、 # pからこの距離までのレイヤーiの祖先を持つことができます。 influence_radius = 2 * sqrt(2) * s possible_roots = set() # ±2は最も近いサイトを見つけるのに十分です。 # 安全性をチェックする際には±3を使用します。これは、 # influence_radius内にある可能性のあるサイトを含むすべてのセルを含みます。 radius = 3 if check_safe else 2 for dx in range(-radius, radius + 1): for dy in range(-radius, radius + 1): cell = centre_cell + (dx, dy) q = site(layer, cell) d = squared_distance(p, q) if d < best_distance: best_distance = d best_cell = cell best_site = q if check_safe and d <= influence_radius ** 2: possible_roots.add(root(layer, cell)) safe = len(possible_roots) == 1 return best_cell, best_site, safe def partition_adaptive(p, max_depth): """pを含む分割を計算します。結果が変わらないことが保証されるとすぐに早期停止します。 そのような保証が得られない場合は、max_depthを有限近似として使用します。""" for layer in range(max_depth + 1): cell, _, safe = nearest_site_safe(layer, p, check_safe=True) if safe: break return root(layer, cell)