Раскидать точки внутри выпуклого многоугольника

− Скрыть

1) Poisson-disk (Bridson) внутри многоугольника

Идея. Кидаем точки так, чтобы между любыми двумя было не меньше радиуса r. Это даёт равномерный “псевдо-шестигранник”.
Почему просто. Не нужны Вороной/Делоне. Только список активных точек и проверка расстояний в окрестной решётке.

Как подобрать радиус под N точек. Пусть площадь многоугольника = A. Возьмите шаг гекса

\(s \approx \sqrt{\frac{2}{\sqrt{3}}\cdot\frac{A}{N}}\)

и положите минимальную дистанцию \(r \approx 0.9\,s\) (чуть меньше, чтобы гарантированно уместиться). Если вышло заметно больше/меньше N — отрегулируйте r двоичным поиском.

Скетч алгоритма Bridson (O(N)):

1. Постройте AABB многоугольника и регулярную сетку с ячейкой \(h=r/\sqrt{2}\).
2. Случайно выберите стартовую точку внутри полигона; поместите её в список active и в сетку.
3. Пока active не пуст:

  * Возьмите случайную точку p из active.
  * Сгенерируйте до k (обычно 30) кандидатов равномерно в кольце \([r,2r]\) вокруг p.
  * Для каждого кандидата: проверьте “точка внутри полигона” (выпуклый: набор полуплоскостей) и отсутствие соседей ближе r (смотрите только клетки сетки вокруг).
  * Если кандидат прошёл — добавьте в точки и в active.
  * Если все k провалились — удалите p из active.
4. Если итоговое количество отличается от N — слегка подвиньте r и повторите (обычно 1–2 итерации достаточно).

Плюсы: простота, хорошее визуальное равномерное распределение, нет Вороного.
Минусы: N получается “как получится” для фиксированного r (но это решаемо подбором r).

---

2) Low-discrepancy + лёгкая “репульсия” (Lloyd-lite без Вороного)

Идея. Сначала получите равномерные, но детерминированные точки с помощью малодисперсной последовательности (Halton/Hammersley) и равномерного сэмплинга по площади. Потом 5–20 шагов “отталкивания”, без Вороного.

Шаги:

1. Триангуляция выпуклого многоугольника фаном от вершины: \((v_0,v_i,v_{i+1})\).
2. Предварительно накопите площади треугольников и сделайте CDF по площади.
3. Для \(i=1..N\): возьмите \(u_i\) из Hammersley \((i/N, \phi_2(i))\). По \(u_i.x\) выберите треугольник через CDF, внутри него сэмплируйте равномерно:

  \(a=\sqrt{\xi_1},\quad b=\xi_2,\quad p=(1-a)\,A + a(1-b)\,B + ab\,C\)

  где \(\xi_1,\xi_2 \in [0,1)\).
4. Релаксация без Вороного: несколько итераций маленьких шагов

  \(\Delta p_j = \sum_{k\neq j} w(r_{jk})\,\frac{p_j-p_k}{r_{jk}}\)

  где \(w(r)=\max(0, r^{-2}-R^{-2})\) с отсечкой радиуса \(R \approx 2s\). После шага спроецируйте точку назад внутрь многоугольника (для выпуклого — просто пройтись по полуплоскостям и сдвинуть к ближайшей границе, если нужно).
  Это \~O(N·k) с соседями, но ускоряется uniform-grid’ом/клетками как в Bridson.

Плюсы: просто, детерминированно, быстро сходится к “почти центроидальному” виду.
Минусы: нужны 5–20 лёгких итераций.

---

3) “Гекс-решётка по треугольникам” (полностью детерминированно)

Идея. Разбейте выпуклый многоугольник на треугольники (как выше), распределите по ним числа точек пропорционально площади, а внутри каждого треугольника положите гекс-узор (почти регулярная сетка) с нужным шагом.

Шаги:

1. Посчитайте общий шаг \(s\) как выше: \(s \approx \sqrt{\frac{2}{\sqrt{3}}\cdot A/N}\).
2. Для каждого треугольника \(\triangle ABC\) задайте локальную координатную систему, разложите его на параллельные “ряды” вдоль одной стороны с вертикальным шагом \(h=\frac{\sqrt{3}}{2}s\), смещая каждый второй ряд на \(s/2\).
3. Оставьте точки, попавшие внутрь треугольника (проверка барицентриками), пока не наберёте отведённую квоту для треугольника (квоты округлить так, чтобы сумма = N).
4. При желании добавьте крошечный джиттер \(\pm 0.05s\) и один-два шага “мягкой” репульсии из варианта 2 — и картинка будет очень ровной.

Плюсы: предсказуемая гекс-структура, супер-простая геометрия, без случайностей.
Минусы: на сложных формах у границ видно “обрезку” гекса (легко лечится малым джиттером/репульсией).

---

Что выбрать?

Нужен минимальный код и красивый “blue-noise”: Bridson с подбором r (вариант 1).

Нужна детерминированность и гладкость без Вороного: Hammersley + лёгкая репульсия (вариант 2).

Нужна максимально регулярная сетка: гекс в треугольниках (вариант 3).