Размещение «хороших» контрольных точек на кривых Безье

Question

Я уже некоторое время работаю над этой проблемой, и пока не могу найти хорошее решение.

Проблема: у меня упорядоченный список из трех (или более)2D точки, и я хочу обвести их с помощью кубической кривой Безье таким образом, чтобы она «хорошо выглядела».Часть «хорошо выглядит» довольно проста: я просто хочу, чтобы клин во второй точке сглаживался (например, кривая не сгибается назад).Итак, учитывая три точки, куда следует поместить две контрольные точки, которые будут окружать вторую точку в триплете при рисовании кривой.

Мое решение пока следующее, но оно неполное.Идея также может помочь передать внешний вид, который мне нужен.

Учитывая три точки, (x1, y1), (x2, y2), (x3, y3).Возьмем круг, вписанный каждой тройкой точек (если они коллинеарны, мы просто рисуем прямую линию между ними и идем дальше).Возьмите линию касательную к этому кругу в точке (x2, y2) - мы разместим контрольные точки, которые окружают (x2, y2) на этой касательной линии.

Это последняя часть, на которой я застрял,У меня проблема в том, чтобы найти способ разместить две контрольные точки на этой касательной линии - у меня есть достаточно хорошая эвристика относительно того, как далеко от (x2, y2) на этой линии они должны быть, но, конечно, естьдве точки на этой линии, которые находятся на таком расстоянии.Если мы вычислим один в «неправильном» направлении, кривая зациклится на себе.

Чтобы найти центр круга, описанного тремя точками (если любая из точек имеет одинаковое значение x, простоизмените порядок точек в приведенном ниже расчете):

double ma = (point2.y - point1.y) / (point2.x - point1.x);
double mb = (point3.y - point2.y) / (point3.x - point2.x);
CGPoint c; // Center of a circle passing through all three points.
c.x = (((ma * mb * (point1.y - point3.y)) + (mb * (point1.x + point2.x)) - (ma * (point2.x + point3.x))) / (2 * (mb - ma)));
c.y = (((-1 / ma) * (c.x - ((point1.x + point2.x) / 2))) + ((point1.y + point2.y) / 2));

Затем, чтобы найти точки на касательной, в этом случае найдите контрольную точку для кривой, идущей от точки 2 к точке 3:

double d = ...; // distance we want the point. Based on the distance between
                // point2 and point3.
// mc: Slope of the line perpendicular to the line between
// point2 and c.
double mc = - (c.x - point2.x) / (c.y - point2.y);
CGPoint tp; // point on the tangent line
double c = point2.y - mc * point2.x; // c == y intercept
tp.x = ???; // can't figure this out, the question is whether it should be
            // less than point2.x, or greater than?
tp.y = mc * tp.x + c;
// then, compute a point cp that is distance d from point2 going in the direction
// of tp.

Answer 1

Если вы действительно уверены, что у вас есть хороший способ выбрать, как далеко вдоль линии касания должны быть ваши точки, и вам нужно только решить, на какую сторону поставить каждую из них, то я бы посоветовал вам посмотреть один раз снова в том круге, к которому линия касается. У вас есть z1, z2, z3 в этом порядке на круге; представьте, что вы идете по кругу от z2 к z1, но вместо этого идете по касательной; вот с какой стороны должна быть контрольная точка «до z2»; контрольная точка «после z2» должна быть на другой стороне.

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

Если вы не возражаете против значительной сложности кода, в программе METAFONT Дона Кнута (основной целью которой является рисование шрифтов) есть сложный и очень эффективный алгоритм для решения именно вашей проблемы (и даже больше). Алгоритм принадлежит Джону Хобби. Вы можете найти подробное объяснение и рабочий код в METAFONT или, возможно, лучше в тесно связанном METAPOST (который генерирует вывод PostScript вместо огромных битовых карт).

Указывать на это немного сложно, хотя METAFONT и METAPOST являются «грамотными программами», что означает, что их исходный код и документация состоят из своего рода гибридного кода на Паскале (для METAFONT) или кода на C (для METAPOST) и разметка TeX. Есть программы, которые превратят это в красиво набранный документ, но, насколько я знаю, никто не разместил результат в Интернете. Итак, вот ссылка на исходный код, который вы можете или не можете найти совершенно непонятным: http://foundry.supelec.fr/gf/project/metapost/scmsvn/?action=browse&path=%2Ftrunk%2Fsource%2Ftexk%2Fweb2c%2Fmplibdir%2Fmp.w&view=markup - в котором вы должны искать «Выбор контрольных точек».

(Красиво набранный документ для METAFONT доступен в виде переплетенной книги под названием «METAFONT: программа». Но это стоит реальных денег, а код написан на Паскале.)

Answer 2

Звучит так, что вам, возможно, потребуется выяснить направление, в котором движется кривая, чтобы установить точки касания, чтобы они не сгибались назад. Из того, что я понимаю, было бы просто выяснить направление от (x1, y1) до (x2, y2), а затем пройти по касательной к линии вашего эвристического расстояния в направлении, ближайшем к направлению (x1, y1) -> (x2, y2), и выбрать точку касания там.