Была у нас кривая A, кубическая или квадратическая, обозначенная тонкой красной линией. Была, да сплыла. После неких манипуляций осталось два смежных кусочка, A и B, совпадающих с исходной кривой с заданной погрешностью (ну, для примера, в экранных масштабах координат, с точностью 0.1 пиксела). Известно так же, что исходная кривая была либо кубической, либо квадратической. Еще известно, что точка сочленения всегда находится либо в минимуме, либо в максимуме по оси Y (кубическая кривая может быть разбита на три под-кривые). Но параметры исходной кривой (контрольные и опорные точки) — утеряны.
Задача заключается в том, чтобы объединить кривые B и C в одну, поскольку известно, что изначально это была одна кривая. Точнее сказать, надо еще проверить, а можно ли выполнить это объединение в пределах заданной погрешности, поскольку могут быть и "ложные" случаи, когда в верхней или нижней точке стыкуются разные кривые.
В более общей формулировке задача звучит так: Есть смежные кривые B и C. Необходимо проверить, можно ли объединить их в одну, не превышая заданной погрешности. И если можно, то вычислить контрольные точки объединенной кривой BC.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
MS>Задача заключается в том, чтобы объединить кривые B и C в одну, поскольку известно, что изначально это была одна кривая. Точнее сказать, надо еще проверить, а можно ли выполнить это объединение в пределах заданной погрешности, поскольку могут быть и "ложные" случаи, когда в верхней или нижней точке стыкуются разные кривые.
Для квадратической кривой, ИМХО, можно тупо попробовать решить систему уравнений.
И еще, как заданы кривые B и C? Для "мягкого" стыка у них на концах должны совпадать значения всех производных (на практике достаточно первой и второй).
Здравствуйте, Cyberax, Вы писали:
C>Для квадратической кривой, ИМХО, можно тупо попробовать решить систему уравнений.
У меня есть другая мысль — можно, исходя из свойства кривых Безье, попробовать обойтись поиском точек пересечения прямых. Пока эта мысль очень сырая.
А насчет уравнений, да, квадратические еще вполне решаемы. Но вот кубические... Я тут попробовал решить вычисление точек пересечения кубической кривой с горизонталью. Должно было быть максимум три корня. Взял уравнение и начал расписывать. И с самого начала мне это не понравилось. В конце концов взял quickmath.com и вбил туда уравнение. Да, действительно, выдало три решения... На страницу мелкого печатного текста каждое. Но самое главное — откуда-то вылезло i. То есть, я конечно знаю, есть такие комплексные числа, но я понятия не имею, что мне с этим i делать в решении кубического уравнения! И каков смысл этого i в данном случае — тоже не понятно. В общем, плюнул.
C>И еще, как заданы кривые B и C? Для "мягкого" стыка у них на концах должны совпадать значения всех производных (на практике достаточно первой и второй).
Кривые заданы точками. Для квадратической — три точки, для кубической — четыре. Да, именно это свойство я и хочу использовать, вычислив ожидаемые опорные точки объединенной кривой и оценив расстояния до реальных точек. Вроде-бы как все делается с прямыми, но пока не уверен.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Cырая и сумбурная мысль:
Пусть искомая кривая задается контрольными точками A0..A3, известные точками B0..B3 и С0..С3, причем B0=A0, B3=C0, C3=A3
Если кривая A разделена на B и С при параметре tx, то должны выполняться условия B1 = A0 + (A1-A0) * tx, С2 = A3 + (A2-A3)*(1-tx), и согласование A(tx) = B3. A1.x и A1.y не независимы, как и A2.x и A2.y, так что фактически три неизвестных получается, и из трех уравнений их можно найти. Далее проверяем, например, что середины кривых B и С совпадают (с допуском) с соотв. точками A (или несколько точек).
>А насчет уравнений, да, квадратические еще вполне решаемы. Но вот кубические... Я тут попробовал решить вычисление точек пересечения кубической кривой с горизонталью. Должно было быть максимум три корня. Взял уравнение и начал расписывать. И с самого начала мне это не понравилось. В конце концов взял quickmath.com и вбил туда уравнение. Да, действительно, выдало три решения... На страницу мелкого печатного текста каждое. Но самое главное — откуда-то вылезло i. То есть, я конечно знаю, есть такие комплексные числа, но я понятия не имею, что мне с этим i делать в решении кубического уравнения! И каков смысл этого i в данном случае — тоже не понятно. В общем, плюнул.
с этим как раз особых проблем не должно быть. Кубическое уравнение имеет один или три (два из них могут совпадать) действительных корня. Для данной цели функция его решения должна возвращать количество вещественных корней и сами корни, игнорируя комплексные.
Здравствуйте, McSeem2, Вы писали:
MS>В более общей формулировке задача звучит так: Есть смежные кривые B и C. Необходимо проверить, можно ли объединить их в одну, не превышая заданной погрешности. И если можно, то вычислить контрольные точки объединенной кривой BC.
Неясно, как заданы кривые B и C... Формулами?
Тупой путь, имхо, прост: взять побольше контрольных точек,
провести через них объединенную кривую МНК нужного порядка
и посчитать отклонение в контрольных точках.
Здравствуйте, McSeem2, Вы писали:
MS>На страницу мелкого печатного текста каждое. Но самое главное — откуда-то вылезло i. То есть, я конечно знаю, есть такие комплексные числа, но я понятия не имею, что мне с этим i делать в решении кубического уравнения! И каков смысл этого i в данном случае — тоже не понятно. В общем, плюнул.
Мнимая единица бывает появляется в процессе решения — это вполне нормально, в конечных ответах мнимые числа должны сокращаться. Если не сокращаются — можно их тупо выбрасывать (как и в случае квадратного уравнения).
C>>И еще, как заданы кривые B и C? Для "мягкого" стыка у них на концах должны совпадать значения всех производных (на практике достаточно первой и второй). MS>Кривые заданы точками. Для квадратической — три точки, для кубической — четыре. Да, именно это свойство я и хочу использовать, вычислив ожидаемые опорные точки объединенной кривой и оценив расстояния до реальных точек. Вроде-бы как все делается с прямыми, но пока не уверен.
Вспомнил еще подробности про Безье. Еще можно попробовать воспользоваться тем, что кривые соединяются в локальном экстремуме. То есть, в точке где производная равна нулю — так мы можем сбросить одну степень с уравнений.
Здравствуйте, McSeem2, Вы писали:
VC>>Неясно, как заданы кривые B и C... Формулами? MS>Все кривые — Безье. Квадратческие всегда задаются тремя точками, кубичекие — четрьмя.
Какими точками, кстати? Контрольными или точками на кривых?
Здравствуйте, Cyberax, Вы писали:
C>Какими точками, кстати? Контрольными или точками на кривых?
Контрольными. Все как обычно для кривых Безье. Две точки — концы (опорные точки) и одна контрольная для квадратической, две контрольных — для кубической. Я, кстати, ни разу не встречался с таким феноменом, чтобы кривые Безье задавались точками на самих кривых.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
C>>Какими точками, кстати? Контрольными или точками на кривых? MS>Контрольными. Все как обычно для кривых Безье.
Тогда просто вычисляешь точку экстремума (это достаточно просто) и просто смотришь значение второй производной для обоих кривых.
Если я правильно помню диф. геометрию, то это все можно проделать даже для параметрической формы (B(t)=(1-t)^2*P0 + 2*t*(1-t)*P1 + t^2*P2).
MS>Две точки — концы (опорные точки) и одна контрольная для квадратической, две контрольных — для кубической. Я, кстати, ни разу не встречался с таким феноменом, чтобы кривые Безье задавались точками на самих кривых.
Я просто подумал, что это у тебя может быть какая-то хитрая задача, что контрольные точки неизвестны.
Здравствуйте, Cyberax, Вы писали:
C>Если я правильно помню диф. геометрию, то это все можно проделать даже для параметрической формы (B(t)=(1-t)^2*P0 + 2*t*(1-t)*P1 + t^2*P2).
Я думаю, все даже гораздо проще, и легко решается даже для общего случая, не учитывая никакие экстремумы. По-моему, все решается простыми пропорциями на отрезках (см. разбиение кривый методом de Casteljau). Вот закончу с некоторой рутиной и поэкспериментирую.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, McSeem2, Вы писали:
C>>Если я правильно помню диф. геометрию, то это все можно проделать даже для параметрической формы (B(t)=(1-t)^2*P0 + 2*t*(1-t)*P1 + t^2*P2). MS>Я думаю, все даже гораздо проще, и легко решается даже для общего случая, не учитывая никакие экстремумы. По-моему, все решается простыми пропорциями на отрезках (см. разбиение кривый методом de Casteljau). Вот закончу с некоторой рутиной и поэкспериментирую.
У тебя есть готовый проект на котором можно поэкспериментировать? А то мне тут enterprise-программирование в очередной раз надоело, надо над чем-нибудь мозг поломать для разнобразия.
Здравствуйте, Cyberax, Вы писали:
C>У тебя есть готовый проект на котором можно поэкспериментировать? А то мне тут enterprise-программирование в очередной раз надоело, надо над чем-нибудь мозг поломать для разнобразия.
Попробовал сделать проект, заодно и все решил. Оказалось все тривиально, как я и предполагал.
Нам известны точки 1, 12, 123, 1234, 234, 34, 4. Надо найти точки 2 и 3. Они всегда находятся на прямых, заданных точками 1-12 и 4-34 соответственно. При этом расстояние 1-12 соотносится с 12-2 так же, как 123-1234 с 1234-234.
Какая-то объединенная кривая вычисляется при любом раскладе. Далее, на вычисленной кривой проверяем ошибку по совокупности простых критериев — снова делим получившуюся кривую при t=d1/(d1+d2) и смотрим на расстояние от вычисленных контрольных точек до исходных.
Для квадратической кривой — еще проще.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, Ka3a4oK, Вы писали:
KK>Сразу извиняюсь за оффтоп. Максим, над чем сейчас работаешь? Antigrain забросил? Давно не было твоих сообщений в рассылке.
Не забросил, но пока не до этого. Просто имеются некоторые меркантильные интересы, исходящие из обладания кусочком небольшой, но успешной компании. А работаю в основном над вычислительной геометрией и прочими там алгоритмческими задачами.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
MS>Не забросил, но пока не до этого. Просто имеются некоторые меркантильные интересы, исходящие из обладания кусочком небольшой, но успешной компании. А работаю в основном над вычислительной геометрией и прочими там алгоритмческими задачами.
MS>Не забросил, но пока не до этого. Просто имеются некоторые меркантильные интересы, исходящие из обладания кусочком небольшой, но успешной компании. А работаю в основном над вычислительной геометрией и прочими там алгоритмческими задачами.
