Как найти равноудалённые точки на кривой Безье, или эллипсе?

Question

[AnswerSearcher]

Возникла необходимость сабжа, бьюсь второй день, не спиться даже.

Ребята, я честно обыскивался интернетом, не буду спорить что нашёл некоторые решения (stackoverflow.com/questions/10477/equidistant-poin... , mathoverflow.net/questions/28070/finding-n-points-... но с моими дошкольными познаниями о геометрии эффективность данных ответов сводится к нулю, и позволяет только данные объекты на экран вывести.

Да, я знаю, геометрию нужно знать если задаёшься такими вопросами, но сейчас у меня не слишком много времени на это, но я обязательно буду посвящать этому время при изучении материалов.

P.S. Пишу скрипт на яваскрипт, честно — необходимо разместить картинки на эллипсе равноудалённо, но если это слишком ресурсозатратно подойдут и кривые.

P.P.S. Если кому необходимо визуализировать суть проблемы и во что у меня не получается - www.saccade.com/writing/graphics/RE-PARAM.PDF на второй странице наглядная демонстрация (только не на эллипсе или кривой).

Answer 1

[Армянское Радио]

Правильный ответ нашелся на stackoverflow

Фактически, тамошний автор использовал вариант с параметрическим уравнением эллипса:

Но каждый шаг параметра альфа у него не константа, а определяется по формуле:

Для вычисления длины эллипса L можно применять формулу Рамануджана:

Comments

[AnswerSearcher]

Большое спасибо Армянскому Радио за помощь в адаптации данного мат аппарата на практике, и прояснению тонких моментов!

[Армянское Радио]

AnswerSearcher: Рад был помочь!

[Scrandre]

Поправлю: в алгоритме решения на stackoverflow используется вторая формула Рамануджана, которая даёт более точные результаты.

[Армянское Радио]

Scrandre: спасибо. Кстати, есть мнение, что при современных мощностях компьютеров, в наглую проинтегрировать по квадратурной формуле Гаусса будет еще быстрее и точнее.

[AnswerSearcher]

Армянское Радио: Вариант в плане точности, конечно, идеальный, но решение предполагается анимировать (сдвигать точки по эллипсу), и к тому же использовать на веб-странице которую будут загружать с мобильных устройств, поэтому вопрос хорошего приближённого алгоритма всё же стоит.
Наткнулся, также, на решение через алгоритм Бесселя (paulbourke.net/geometry/ellipsecirc/), прошу специалистов подсказать насколько этот метод (теоретически) хорош при использовании для задач моего типа?

[AnswerSearcher]

Fix: paulbourke.net/geometry/ellipsecirc

[Армянское Радио]

AnswerSearcher:
Я думаю, что стоит вычислить интеграл по квадратурной формуле Гаусса с четырьмя узловыми точками и посмотреть на качество. Хуже четырех знаков после запятой получиться не должно.

Answer 2

[Rsa97]

А что значит "равноудалённо"? Равное декартово расстояние между точками или равная длина дуги кривой?
Для эллипса задача аналитически не решается, поскольку решение содержит эллиптический интеграл, не берущийся в общем виде.
Можно преобразовать эллипс в набор точек по Брезенхему, сохраняя кроме координат расстояние до предыдущей точки (сдвиг только по X или Y даёт 1, одновременный сдвиг даёт sqrt(2)) и просуммировать расстояния, получив длину приближённой линии. Затем делим эту длину на нужное количество частей, получая шаг по дуге и от стартовой точки суммируем расстояния до получения нужного шага.

Comments

[AnswerSearcher]

Спасибо, в свободное время попробую оформить ваш алгоритм, сравнить эффективность с другими, в частности с тем который быстро нашёлся на просторах сети в качестве решения.

Answer 3

[uvelichitel]

С эллипсом кажется довольно просто - расставить на окружности, потом сплюснуть.
Сплющивание просто сделать можно так
X_эллипса=X_окр
Y_эллипса=Y_окр*a/b
где a, b полуоси эллипса

Comments

[AnswerSearcher]

В том то и дело что при сплющивании они приближаются друг к другу на перифокусах, а надо чтобы были равноудаленны, если не ошибаюсь то имеется в виду декартово расстояние.