Равномерно распределить n точек внутри эллипса

Question

Как равномерно распределить n точек внутри эллипса с учетом n и длины его малой оси (можно считать, что главной осью является ось x и размер 1)?Или, если это невозможно, как вы выбираете n точек таким образом, чтобы наименьшее расстояние между любыми двумя было максимизировано?

Сейчас мне непросто работать с дорогими имитаторами отталкивания электронов (в надежде, что есть лучшее решение, такое какфункция подсолнечника в этот вопрос для распределения n точек по кругу).n, скорее всего, будет между 10 и 100 баллами, но было бы неплохо, если бы он работал отлично для всех n

Answer 1

Довольно простой подход:

Сделать начальное значение для аппроксимации расстояния D, например D=Sqrt(Pi*b/N ), где b - длина вспомогательной оси.

Создание треугольной сетки (с равносторонними треугольниками для обеспечения наиболее плотной упаковки) точек с размером ячейки D. Подсчитайте количество точек, лежащих внутри данного эллипса.

Если оно меньше N, уменьшите расстояние D, больше - увеличьте D. Повторяйте, пока внутри точно не будет N точек.

Зависимость CountInside <=> D является монотонной для фиксированной начальной точки, поэтому вы можете использовать бинарный поиск, чтобы получить результат быстрее.

Могут быть сложные случаи с 2-4 симметричными точками вблизи границы - когда они выходят наружу или внутрь одновременно. Если вы поймаете этот случай, немного сдвиньте начальную точку.