плавная кривая через точки, используя только горизонтальные, вертикальные линии и дуги с фиксированным радиусом

Имея упорядоченный список точек, я хочу нарисовать гладкую кривую, проходящую через все точки. Каждая часть кривой может быть горизонтальной, вертикальной или дугой заданного радиуса r (все дуги будут иметь одинаковый радиус). Переходы должны быть плавными, т. е. заголовок в конце одной части должен совпадать с заголовком в начале следующей части. Между любыми двумя последовательными входными точками может быть любое количество дуг или отрезков прямой линии.

Это что-то вроде железнодорожной колеи, которая должна идти ортогонально или по участкам с фиксированной кривизной.

Есть ли хороший алгоритм для построения такой кривой? (или, в случаях, когда такая линия невозможна, я хотел бы это знать.)

Я изучил кривые Безье, но это кажется излишним, и я не смог найти хороший способ применить свои ограничения.


geometry smoothing graph-layout
person Mzzzzzz    schedule 06.07.2012    source источник

Ответы (1)


arrow_upward
2
arrow_downward

То, о чем вы просите выше, подразумевает для меня, что вы ищете касательную непрерывность своей кривой в точках (аналогично сплайну с касательной непрерывностью в узлах). Аналогия с железнодорожными путями, по крайней мере, передает это требование. Учитывая строгие ограничения прямых линий и дуг окружности фиксированного радиуса, я уверен, что вы не сможете этого сделать. Почему бы не рассмотреть сплайн-интерполяцию ваших точек, если вместо этого вам нужна такая гладкость? Чтобы понять почему, рассмотрим следующее изображение:

возможная конфигурация точки данных

Попробуйте заменить отрезок линии между B и C дугой окружности. Вы можете сделать это, чтобы сделать соединение непрерывным, но чтобы сделать его касательным непрерывным, вам понадобится много удачи, так как есть только один круг, который является непрерывным по касательной. к отрезку AB, который также касается точки C. Вероятность того, что эта окружность имеет касательную в точке C, совпадающую с касательной к прямой CD, невелика. Возможно, ваши данные выстроятся таким образом, но вы не можете на это полагаться.

Если я неправильно понял ваш вопрос, сообщите мне, и я изменю ответ.

person mathematician1975    schedule 06.07.2012
comment
Спасибо, я должен был упомянуть об этом: точки не будут плотными относительно заданного радиуса r, поэтому в большинстве случаев такой тип размещения должен быть возможен. - person Mzzzzzz; 06.07.2012
comment
Даже в этом случае вам будет трудно добиться непрерывности касательной, если только ваши точки не удовлетворяют очень жестким критериям. Вы можете подогнать кривую, которая выглядит как непрерывная по касательной, но я сомневаюсь, что это так. Но только вы можете решить, достаточно ли этого для ваших нужд. Удачи! - person mathematician1975; 06.07.2012
comment
Ах, кажется, я понимаю, что мне нужно уточнить: между каждой парой точек может быть несколько прямых сегментов или дуг. Например, на вашем изображении вы можете начать с вертикальной линии вверх от A, дуги в 90 градусов к B, затем горизонтальной линии к B. Затем от B вы можете начать с горизонтального сегмента, затем дуги вниз к C , и так далее. Извините за текстовое описание, но я не думаю, что смогу добавить изображение в свой комментарий. - person Mzzzzzz; 12.07.2012
comment
@ marcopolo1010 Теперь я понимаю, что вы имеете в виду. Вы хотите создать свою собственную кривую из прямой линии и дуги, чтобы полученная конструкция интерполировала ваши данные. Ну, я бы предположил, что это возможно, но потенциальная проблема заключается в том, что такая конфигурация вряд ли будет уникальной — я уже могу представить множество таких кривых, возможных только для изображения выше. На самом деле я бы выбрал сплайн-интерполант, если вам действительно не нужны только дуги и линии. Я, конечно, никогда не слышал об алгоритме, который делает то, что вы хотите, но все равно удачи! - person mathematician1975; 12.07.2012
comment
Я предполагаю, что ОП использует инструмент с ЧПУ, который может делать только дуги и прямые линии, поэтому его требование. - person bradgonesurfing; 19.02.2013