Почему окрестности 5×5 недостаточно для ячейки Вороного

Один из способов строить процедурные регионы — взять квадратную сетку и случайно разместить по точке в каждой клетке. Чтобы вычислить полную ячейку Вороного, обычно строят диаграмму для локальной окрестности.

Борис из BorisTheBrave показал, что привычная область 5×5 может дать неверную границу: точка из клетки со смещением (3, 1) тоже способна на неё повлиять.

Автор определил набор из 36 соседних клеток, каждая из которых может оказаться значимой, и приложил формальное доказательство в Lean.

Это результат для вычисления полной ячейки. У поиска ближайшей точки для шума Worley свои требования к окрестности.

Контрпример и доказательство полезны для проверки генератора регионов или процедурной геометрии.