Аппроксимация кривой Безье второго уровня на ActionScript 3

[Chum]

Доброго времени суток. Требуется код на AS3.
Есть кривая Безье второго порядка построенная по 3 точкам, координаты известны, есть точка A координаты которой тоже известны и которая лежит на кривой. Требуется получить координаты двух опорных точек кривых Безье созданных на основе исходной кривой с разделением в точке A. Если кто-то уже сталкивался с такой проблемой - поделитесь плиз. Гуглил, какой-то материал находил но всё не то. Знаю что задача скорее для форума по начерталке, но в инете при вводе выскакивают только услуги по изготовлению контрольных работ и т.д.

[Tails]

Тут смотрели? http://silin.su/#AS3/geom/fit

[Chum]

Да это я видел. Я уже строю замкнутые контуры методом curveTo. Но там есть одна фишечка которую очень бы хотелось реализовать и по-этому вопрос должен быть решён так как он задан.

[Александр Мостовой]

Код сейчас не смогу написать, но попытаюсь объяснить:

Кривая Безье расчитывается параметрически как фаза параметра t от 0 до 1.
x(t) = p0.x * (1-t)^2 + 2 * p2.x * t * (1 - t) + p1.x * t^2;
y(t) = p0.y * (1-t)^2 + 2 * p2.y * t * (1 - t) + p1.y * t^2;
А по сути она строится геометрически откладыванием процентного положения коэффициента t на опорных прямых. Допустим t = 0.1. Мы на левом отрезке p0p1 отсыитываем десятую часть (тока Q0) и на правом p1p2 тоже десятую часть соответственно (тока Q1). ПОтом соединяем их и на получившейся прямся отрезке снова отситываем десятую часть, которая и будет текущей точкой.
http://upload.wikimedia.org/wikipedia/commons/1/19/Bezier_quadratic.png

http://upload.wikimedia.org/wikipedia/commons/3/35/Bezier_quadratic_anim.gif

Если вам известен только x или y (как обычно бывает, ведь нельзя мышью точно попасть в линию. Это частая ошибка брать изначально известные х и у, ведь не факт что эта точка принадлежит кривой безье. Нужно по х найти точный y или наоборот)
решаете уранение из которого находите текущую фазу точки в кривой Безье.
то есть обычное квадратное уравнение.
Например, кликнув мышью в области x = 20;

20 = p0.x * (1-t)^2 + 2 * p2.x * t * (1 - t) + p1.x * t^2
Находим t. Из нее находим соответсвующую x координату y. (по y(t)) Тперь мы знаем обе координаты точки - пусть это бeдет B(x,y)
Находим по t точку построения на линии p0p1, пусть это будет точка Q0.
Q0.x = p0.x + t * (p1.x - p0.x);
Q0.y = p0.y + t * (p1.y - p0.y);



И теперь для того что бы нарисовать сектор кривой безье делаем нашу точку B ( точка разделения кривой) второй опорной, как до этого у нас была точка p2
А точку Q0 (которая на отрезке p0 p1) - делаем якорем

graphics.moveTo(p0.x, p0.y);
graphics.curveTo(B.x, B.y, Q0.x, Q0.y);
Эта линия у нас оказывается совпадающей с исходной. Но конечная точка у нее приходится на нашу точку деления кривой Безье - B(x,y)



То есть вам к этому нужно только решать квадратное уравнение из которого находить t -текущую фазу кривой Безье
B.x = p0.x * (1-t)^2 + 2 * p2.x * t * (1 - t) + p1.x * t^2
//где B.x - исходная точка сечения кривой Безье

[Chum]

Речь идёт о добавлении на замкнутый контур отрисованный кривыми Безье ещё одной точки. Пользователь подводит курсор к линии, линия в данном случае sprite которому задано:
spr.buttonMode = true;
В момент отображения курсора ссылкой пользователь кликает мышью, координаты известны, точка добавляется. Пока у меня это реализовано очень грубо - точка добавляется с прямыми кривыми, т.е. опорные точки лежат на самих кривых. Хочется что бы рисунок не нарушался.
Спасибо за ответ, давайте пока отложим разговор, я немного доработаю это упражнение и выложу на форум для более предметного разговора.

[Chum]

Вот предмет разбирательства двух тем созданных мной на этом форуме:
О многомерных массивах:
http://www.flasher.ru/forum/showthread.php?t=195384
и собственно этой.
Что это - это упражнение по построению кривыми Безье второго порядка замкнутого регулируемого контура.
При загрузке SWF-файл находится в режиме создания замкнутого контура, о чём свидетельствует желтый цвет кнопки в правом верхнем углу. Из этого режима нельзя выйти не создав контур.
Первоначально контур отображается ломаной линией.
Нажав после создания одного или нескольких контуров, кнопку перехода - отобразится зелёным цветом, переходим в режим регулирования сплайнов.
Сейчас можно изменять форму сплайна при помощи опорных и якорных точек, а также добавлять в контур новые точки, подведя курсор к линии и тогда когда он отбразится в виде ссылки - кликнуть.
Для лучшего понимания вопроса темы необходимо "вытянуть" при помощи жёлтой кнопки линию сплайна до сигарообразной формы и кликнуть по линии.curve1.swf

[Александр Мостовой]

Ну да, так я ваш вопрос и понял изначально
1. Находите t по формуле
http://upload.wikimedia.org/math/9/e/b/9ebb3fee21d54ba61df214692bf0622e.png
2 находите соответствующий y(t) по формуле
y(t) = p0.y * (1-t)^2 + 2 * p2.y * t * (1 - t) + p1.y * t^2;
3. Находите точку Q0 ( на рисунке)
Q0.x = p0.x + t * (p1.x - p0.x);
Q0.y = p0.y + t * (p1.y - p0.y);
Рисуете сегмент кривой, где Q0 - опорная, а точка вашего клика B - конечная.
Все 3 точки вам известны.

Во второй части сегмента - наоборот, - точка B начальная, а Q1 опорная

[Chum]

Спасибо. Ситуация более-менее проясняется. Думаю что моих знаний в математике хватит для того что бы допилить этот вопрос.

[Александр Мостовой]

Ну здесь в общем никаких других формул не нужно вычислять. Если не очень понятно к каким точкам их применять - спрашивайте.
Да в этой формуле
http://upload.wikimedia.org/math/9/e...692bf0622e.png
можете взять либо либо x координаты точек либо y - не принципиально, там просто указаны P1, P2, если по Х выбираете току клика мышью - то p1.x, p2.x соотвтетсвенно подставить

[Chum]

Что-то не очень идёт у меня решение этого вопроса.
Начальное условие: известны координаты точек P0, P1, P2, B. Требуется определить координаты точек Q0 и Q1.
В рисунке:
http://upload.wikimedia.org/wikipedia/commons/1/19/Bezier_quadratic.png
В формуле:
29257
Значение t в данном случае: величина в долях отрезка P0-Q0 с учётом того что отрезок P0-P1 принять за 1.
Пытаюсь определить величину t как проекцию на ось X и в формуле использую координаты x точек.
Проблемы:
1.В частных случаях в зависимости от того куда направлен изгиб кривой подкоренное выражение принимает отрицательное значение и следовательно результат NaN
2.Так как значение t принимает единственное значение, непонятно зачем задан знак "плюс-минус" перед корнем.

[-De-]

1) Не может быть такого набора точек (например как на картинке, но ищете по у координате, и ставите точку В очень высоко).
2) Если корня два, то выбирать тот, который одинаковый для У и Х. Т.к. например если на рис. считать по у координатам, то явно будет два значения t, при которых у будет равен у-координате точки В, они-то и найдутся по формуле.

[silin]

если не изобретать велосипед по-новой, а воспользоваться готовым решением, http://code.google.com/p/bezier/,
то все как-то проще выглядит :)
// исходные данные
var p0:Point = new Point(10, 200);
var p1:Point = new Point(50, 10);
var p2:Point = new Point(300, 100);
var b:Point = new Point(40, 125);

var bezier:Bezier = new Bezier(p0, p1, p2);
// итератор
var t:Number = bezier.getClosest(b);
// искомые точки
var q0:Point = Point.interpolate(p1, p0, t);
var g1:Point = Point.interpolate(p2, p1, t);

// посмтреть
graphics.lineStyle(1, 0xFF0000);
graphics.moveTo(p0.x, p0.y);
graphics.curveTo(p1.x, p1.y, p2.x, p2.y);

graphics.lineStyle(1, 0x00FF00);
graphics.moveTo(q0.x, q0.y);
graphics.lineTo(g1.x, g1.y);

graphics.lineStyle(1, 0xC0C0C0);
graphics.moveTo(p0.x, p0.y);
graphics.lineTo(p1.x, p1.y);
graphics.lineTo(p2.x, p2.y);

[Chum]

- De -
Не может быть такого набора точек (например как на картинке
Если Вы имеете ввиду 4 точки, координаты которых объявлены как известные: P0, P1, P2, B - такой случай может быть.
Найти требуется либо t, либо координаты Q0 и Q1.

[-De-]

Я имел в виду не как на картинке, только P0, P1, P2 как на картинке, а В задать значительно выше.

[Chum]

- De -
Я имел в виду не как на картинке, только P0, P1, P2 как на картинке, а В задать значительно выше.
B не задаётся, эта точка выбирается на кривой.
silin: Bezier - смотрел документацию по AS3 и у меня в ней нет такого класса.

Добавлено через 2 минуты
А, Вы имеете ввиду библиотеку SWC, я сторонник "лисапедов".

[silin]

>>А, Вы имеете ввиду библиотеку SWC, я сторонник "лисапедов".
да не обязательно swc, исходники тоже где-то в сети еще лежат, здесь поройтесь http://bezier.googlecode.com/svn/trunk/bezier/src/, если интересна реализация
ну какбе бывает лучше посмотреть как подобное сделано и на хорошем уровне, чем изобретать такое 'Пытаюсь определить величину t как проекцию на ось X '

[Chum]

По своему вопросу: пока имею такое решение, может быть кому-то будет интересно, может кто-то предложит лучший вариант, данное решение требует определённой проверки и обкатки.

http://upload.wikimedia.org/wikipedia/commons/3/35/Bezier_quadratic_anim.gif

Код преднамеренно не упрощал, для большей читабельности:

/* Аргументы: 1 - Массив координат точек = [P0.x, P0.y, P2.x, P2.y, P1.x, P1.y, P1.x, P1.y, B.x, B.y],
2 - Количество шагов подбора, выведено в качестве аргумента для того, чтобы в первом приближении
задать большее значение, а в последующих - меньшее. Координаты точки P1 указываются дважды. */

public function approksCurve(arg1:Array, arg2:int):Array {
var rez:Array = new Array();
/* Настроечные параметры */
var kolSh:int = arg2; /* Количество шагов задания значения t */
var prir1x:Number = (arg1[0] - arg1[4]) / kolSh; /* --- Приращение по осям X,Y */
var prir1y:Number = (arg1[1] - arg1[5]) / kolSh;
var prir2x:Number = (arg1[6] - arg1[2]) / kolSh;
var prir2y:Number = (arg1[7] - arg1[3]) / kolSh;
var tek1x:Number;
var tek1y:Number;
var tek2x:Number;
var tek2y:Number;
var provZ:Number;
var minZn:Number = Math.abs((arg1[8]-arg1[0])*(arg1[3]-arg1[1])-(arg1[9]-arg1[1])*(arg1[2]-arg1[0]));
var minIn:int = 0;
for (var i:int = 0; i < kolSh; i++) {
tek1x = arg1[0] - i * prir1x;
tek1y = arg1[1] - i * prir1y;
tek2x = arg1[6] - i * prir2x;
tek2y = arg1[7] - i * prir2y;
provZ = Math.abs((arg1[8] - tek1x) * (tek2y - tek1y) - (arg1[9] - tek1y) * (tek2x - tek1x));
if (minZn > provZ) {
minZn = provZ;
minIn = i;
}
}
/* Возвращает координаты точек Q0 и Q1 */
rez[0] = arg1[0] - (minIn * prir1x); /* Координата Q0.x */
rez[1] = arg1[1] - (minIn * prir1y); /* Координата Q0.y */
rez[2] = arg1[6] - (minIn * prir2x); /* Координата Q1.x */
rez[3] = arg1[7] - (minIn * prir2y); /* Координата Q1.y */
if (minZn > 0 && minZn < 1) return rez;
else {
arg1[0] = arg1[0] - ((minIn - 1) * prir1x);
arg1[1] = arg1[1] - ((minIn - 1) * prir1y);
arg1[2] = arg1[2] - ((minIn - 1) * prir2x);
arg1[3] = arg1[3] - ((minIn - 1) * prir2y);
arg1[4] = arg1[4] - ((minIn + 1) * prir1x);
arg1[5] = arg1[5] - ((minIn + 1) * prir1y);
arg1[6] = arg1[6] - ((minIn + 1) * prir2x);
arg1[7] = arg1[7] - ((minIn + 1) * prir2y);
return approksCurve(arg1, 2000);
}
}

Если кто-то работал над подобной задачей и может что-то подсказать - подскажите плиз.

[Александр Мостовой]

2.Так как значение t принимает единственное значение, непонятно зачем задан знак "плюс-минус" перед корнем.

t не всегда принимает одно значение. Решение уровнения по сути нахождение пересечения прмой и параболы. А она, как известно, может быть повернута так, что прямая пересечет ее два раза (тогда вам нужно выбрать какой корень подходит) либо вообще не пересечет - выражение под корнем будет отрицательным.

Правда я в приведенных в начале темы формулах немного не учел, что у нас оси Y повернутые зеркально координаты
Вот в общем переписал уравнение (только точку B переименовал в S, что бы не путать с коэффициентами b уравнения at^2 + bt + c):

Выожил на онлайн компилятор
http://wonderfl.net/c/rflQ

package
{
import flash.display.GraphicsPathCommand;
import flash.display.Shape;
import flash.display.Sprite;
import flash.display3D.Context3DVertexBufferFormat;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.filters.DropShadowFilter;
import flash.filters.GradientBevelFilter;
import flash.text.TextField;
import flash.utils.getTimer;
import flash.utils.setTimeout;

import flashx.textLayout.operations.CreateSubParagraphGroupOperation;

[SWF(width="670", height="550", frameRate="31", backgroundColor="#ffffff")]
public class Test3 extends Sprite
{

private var p0 :Dot;
private var p1 :Dot;
private var p2 :Dot;
private var q0 :Dot;
private var q1 :Dot;
private var sProto :Dot;
private var s :Dot;

private var scene :Shape;
private var graph :Shape;

public static var main :Test3;

public function Test3()
{
main = this;
addEventListener(Event.ADDED_TO_STAGE, addedToStageHandler)
}

private function init():void
{
graphics.beginFill(0xffffee);
graphics.drawRect(0, 0, stage.stageWidth, stage.stageHeight);

scene = new Shape();
addChild(scene);
sProto = new Dot(0xcccccc, "sProto", 200, 450);//Точка которую мы двигаем, гипотетически рассматриваем как клик мышью
p0 = new Dot(0xff0000, "p0", 100, 400);
p1 = new Dot(0xff0000, "p1", 250, 80);
p2 = new Dot(0xff6600, "p2", 440, 390);
q0 = new Dot(0x00ddff, "q0");
q1 = new Dot(0xff6600, "q1");
s = new Dot(0x00ff00, "s"); //Точка пересечения кривой Безье и прямой
s.mouseEnabled = false;
q0.mouseEnabled = false;
q1.mouseEnabled = false;
s.x = sProto.x;

update();

addEventListener(Event.ENTER_FRAME, enterFrameHandler);
addEventListener(MouseEvent.MOUSE_MOVE, mouseMoveHandler);
stage.addEventListener(MouseEvent.MOUSE_DOWN, stage_mouseDownHandler);
}

private function update():void
{
s.x = sProto.x;

var t:Number = getT();

q0.x = p0.x + (p1.x - p0.x) * t;
q0.y = p0.y - (p0.y - p1.y) * t;

q1.x = p1.x + (p2.x - p1.x) * t;
q1.y = p1.y + (p2.y - p1.y) * t;

s.y = q0.y - (q0.y - q1.y) * t;

//рисуем кривую
scene.graphics.clear();
scene.graphics.lineStyle(10, 0xff6666, 0.3);
scene.graphics.moveTo(p0.x, p0.y);
scene.graphics.curveTo(p1.x, p1.y, p2.x, p2.y);

//ось ресуем сегменты кривой
scene.graphics.lineStyle(1, 0x00ff00, 1);
scene.graphics.moveTo(p0.x, p0.y);
scene.graphics.curveTo(q0.x, q0.y, s.x, s.y);
scene.graphics.lineStyle(1, 0x0000ff, 1);
scene.graphics.curveTo(q1.x, q1.y, p2.x, p2.y);


//ось пересечения с кривой
scene.graphics.lineStyle(1, 0xcccccc);
scene.graphics.moveTo(s.x, -10);
scene.graphics.lineTo(s.x, 700);
scene.graphics.moveTo(p0.x, p0.y);
scene.graphics.lineTo(p1.x, p1.y);
scene.graphics.lineTo(p2.x, p2.y);
scene.graphics.moveTo(q0.x, q0.y);
scene.graphics.lineTo(q1.x, q1.y);

}

private function getT():Number
{
//Решаем классическое квадратное уравнение относительно t. a*t^2 + b*t +c = 0;

var t :Number;
var a :Number = p2.x - 2 * p1.x + p0.x;
var b :Number = (2 * p1.x - 2 * p0.x);
var c :Number = (p0.x - s.x);
var d :Number = b * b - 4 * a * c;

if (d > 0)
{
var t1:Number = (- b + Math.sqrt(d)) / (2 * a);
var t2:Number = (- b - Math.sqrt(d)) / (2 * a);
if (t1 > 0 && t1 < 1) t = t1;
if (t2 > 0 && t2 < 1) t = t2;

}
else
{
t = 0;
}
return t;
}

private function addedToStageHandler(event:Event):void
{
init();
}

private function enterFrameHandler(event:Event):void
{
update();
}

private function mouseMoveHandler(event:Event):void
{
update();
}
private function stage_mouseDownHandler(event:Event):void
{
sProto.x = mouseX;
update();
}
}
}

import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.text.TextField;

class Dot extends Sprite{

private var color :uint;
private var caption :String;

public function Dot(color:uint, caption:String, x:Number = 0, y:Number = 0)
{
this.color = color;
this.caption = caption;
this.x = x;
this.y = y;
init();
}

private function init():void
{
var shp:Shape = new Shape();
shp.graphics.beginFill(color);
shp.graphics.drawCircle(0, 0, 5);
addChild(shp);
Test3.main.addChild(this);


mouseEnabled = true;
useHandCursor = true;

addEventListener(MouseEvent.MOUSE_DOWN, mouseDownHandler);
addEventListener(MouseEvent.MOUSE_UP, mouseUpHandler);
//stage.addEventListener(MouseEvent.MOUSE_DOWN, stage_mouseDownHandler);

var tf:TextField = new TextField();
tf.text = caption;
tf.selectable = false;
tf.mouseEnabled = false;
addChild(tf);
}

private function mouseDownHandler(event:Event):void
{
startDrag(true);
event.stopImmediatePropagation();
}

private function mouseUpHandler(event:Event):void
{
stopDrag();
}

private function stage_mouseDownHandler(event:MouseEvent):void
{
event.stopImmediatePropagation();
}
}

Мы просто решаем систему из 3-х уравнений
q0.x = p0.x + (p1.x - p0.x) * t;
q1.x = p1.x + (p2.x - p1.x) * t;
s.x = q0.x + (q1.x - q0.x) * t;

http://wonderfl.net/c/rflQ/fullscreen