Равнозамедленное движение по ломаной

[alrusdi]

В общем задача такая: Необходимо визуализировать равнозамедленное движение точки по ломаной линии (динамичеки задаваемой массивом точек). Составляющие отрезки по длине различны. Может быть кто-то видел готовое решение или близкое (например равномерное движение по ломаной)?
Поиск я использовать умею...

[Волгоградец]

Используй Tween.

[alrusdi]

Tween, к сожалению, не годиться. Ищу портируемое на другие языки решение. Я представляю как это нужно сделать, но алгоритм нетривиальный достаточно. Вот думаю может готовое найдется.

[chingachgoog]

Я бы задумался над классом Point и его методами (например, normalize)

[Division]

Первое что пришло в голову. Значит, есть массив координат.
Есть объект который движется по ломанной, заданной этими координатами.
У объекта есть скорость и текущее положение (просто вещественное число).
Для начала найдем длину ломанной. То есть сумму длин всех отрезков. Причем длину каждого отрезка нам также нужно хранить в массиве. Надеюсь школьные формулы все помнят (: Далее нам потребуется ещё один массив. Он по размеру будет такой же как массив координат. Только содержать будет не координаты, а длину ломанной от начала до данной точки. То есть с помощью него мы сможем зная пройденный путь(наше текущее положение) определить на каком из отрезков мы находимся. Надеюсь с этим всё понятно. Главное подготовить эти данные, остальное всё просто. Потом происходит анимация. К нашей координате всё время прибавляется скорость, и скорость уменьшается на какой-то коэфициент(равнозамедленное, ага). После того как расчитали новое значение нашей координаты, определим на каком отрезке мы находимся. Это просто, мы же знаем на каком участке пути какое расстояние будет пройдено. Далее нам нужен нормализованный вектор текущего отрезка. Назовем его V. Потом найдем разность между пройденным нами расстоянием и расстоянием до начала текущего отрезка. Фактически это будет расстояние, которое мы прошли по текущему отрезку. Если мы это расстояние поделим на длину текущего отрезка, получим некий коэфициент. Он всегда будет от 0 до 1. Назовем его k.
Так вот, наша текущая координата будет определяться формулой
pos = x0 + V * L * k
где pos - это координата начала отрезка, x0 - начальная координата отрезка, V - нормальзованный вектор, полученный из этого отрезка(находить по типу normalize(x1-x0)) L - длина отрезка, K - коэфициент от 0 до 1. Векторную алгебру все помнят? (:
Описал как всегда смутно. ИМХО реализуется всё очень просто, нужно только немного подумать.

[Alex_beginner]

У меня два варианта:

1. Если Вы хорошо разбираетесь в математике, то по данным узловых точек можно "состряпать" линейный сплайн и потом и пользоваться для указания направления движения точки;
2. Tween для равнозамедленного движения - роскошь, которую могут позволить себе не многие, поэтому проще локально опысывать траекторию движения точки линейными уравнениями, получаемыми из значений координат двух ближайших узловых точек ломаной линии. В реализации данный вариант еще проще, чем на словах, поэтому не привожу здесь код. Думаю, Вы без труда его реализуете.

[alrusdi]

Спасибо за внимание))
Может кому-нибудь в будущем понадобится этот код
Натуральным языком алгоритм описан Division, только что там про коэффициент K значит я так и не понял.
Alex_beginer, Что в данном случае подразумеваете под термином линейный сплайн? Опишите Ваш алгоритм натуральным языком?

//создадим объект, который будет двигаться равнозамедленно по ломаной
_root.createEmptyMovieClip("myobj", 1);
myobj.lineStyle(0, 0xFF0000, 100);
myobj.moveTo(-3, -3);
myobj.lineTo(3, -3);
myobj.lineTo(3, 3);
myobj.lineTo(-3, 3);
myobj.lineTo(-3, -3);

//массив точек ломаной
var mypath:Array = Array(
		Array(13,355),
		Array(50,305),
		Array(145,305),
		Array(229,267),
		Array(190,184),
		Array(268,127),
		Array(307,154),
		Array(294,241),
		Array(348,273),
		Array(408,225),
		Array(414,69)
);

var mypathlenght=0;
var myobjdistance=0;

//это для рисования ломаной
_root.lineStyle(0, 0x0000FF, 100);
_root.moveTo(mypath[0][0], mypath[0][1]);

for (var i=1; i<mypath.length; i++){
	//для каждого отрезка ломаной посчитаем его длину
	//хранить будем сумму длин отрезков до данного участка
	mypathlenght+=calcLength(mypath[i-1], mypath[i]);
	mypath[i][2]=mypathlenght;
	
	//также для каждого отрезка сохраним его нормализованный вектор
	//он даст нам направление движения
	mypath[i][3]=getNormalVector(mypath[i-1], mypath[i]);
	//нарисуем отрезок ломаной
	_root.lineTo(mypath[i][0], mypath[i][1]);
}

//высчитаем необходимую скорость движения
//скорость визуализации движения также будет зависеть от fps ролика
var mypathspeed=mypathlenght/33;
var curspeed=mypathspeed;

_root.onEnterFrame= function(){
	//посчитаем дистанцию которую на данный момент должен пройти объект
	myobjdistance+=curspeed;
	//определим отрезок на котором будет находится объект в данный момент
	var i = getIndexOfCurrentLine(myobjdistance);
	var locallength=0;
	if (i){
		if (i==-1){
			//объект дошел до конца пути
			//переместим его для точности в конечную точку траектории
			_root.onEnterFrame=null;
			i=mypath.length-1;
			_root.myobj._x=mypath[i][0];
			_root.myobj._y=mypath[i][1];
			return;
		}
		//объект находится на втором или последующих отрезках
		//посчитаем сколько он должен пройти от начала текущего отрезка
		var locallength=myobjdistance-mypath[i][2];
	}else{
		//объект на первом отрезке, значит общая дистанция которую он прошел
		//равна расстоянию пройденому им от начала отреска
		var locallength=myobjdistance;
	}
	//уменьшим скорость (движение равнозамедленное)
	curspeed*=0.97;
	//переместим объект от начала текущего отрезка
	//на посчитаное выше расстояние вдоль нормализованного вектора данного отрезка
	ix=mypath[i][0]+mypath[i+1][3][0]*locallength;
	iy=mypath[i][1]+mypath[i+1][3][1]*locallength;
	_root.myobj._x=ix;
	_root.myobj._y=iy;
}


function getIndexOfCurrentLine(ilength){
	for (var i=0; i<mypath.length; i++){
		if (ilength<mypath[i+1][2]){ return i;}
	}	
	return -1;
}

//расстояние между двумя точками равно корню из суммы квадратов
//разности соответствующих координат sqrt( (x2-x1)^2 + (y2-y1)^2 )
function calcLength(ar1, ar2){
	return Math.sqrt((ar2[0]-ar1[0])*(ar2[0]-ar1[0]) + (ar2[1]-ar1[1])*(ar2[1]-ar1[1]));
}

//чтобы нормализовать вектор нужно его составляющие поделить на длину
function getNormalVector(ar1, ar2){
        var ku = calcLength(ar1, ar2);
        nx = (ar2[0]-ar1[0]) / ku;
        ny = (ar2[1]-ar1[1]) / ku;
		return Array(nx, ny);
}

[Alex_beginner]

Alex_beginer, Что в данном случае подразумеваете под термином линейный сплайн? Опишите Ваш алгоритм натуральным языком?

Описываю натуральным языком.

Линейный сплайн (кусочно-линейное интерполирование) представляет собой, некое уравнение, которое позволяет описывать ломаную линию. Как известно из основных постулатов Теории численных методов, полином стпени N может иметь N-1 локальный максимум и минимум и график может раскачиваться, чтобы пройти через точки ломаной линии. Поэтому, N-полиномиальное описание такой ломаной негодится, в принципе. Для описания такой линии лучше использовать линейный сплайн - уравнение, построенное по значениям узловых точек. Как правило, для описания такой кусочно-линейной кривой используют полином Лагранжа. Более детально, об этом можно прочитать в специализированной литературе по математике, имеющейся на пыльных полках многих букинистичеких магазинов.

[Division]

K - коэфициент от 0 до единицы. То есть мы знаем длину текущего отрезка(по которому движемся в данный момент). Знаем, какое расстояние мы по нему уже прошли. Делим это расстояние на длину отрезка, получаем коэфициент K (: Если прошли половину отрезка, K будет равен 0.5. Если находимся в начале отрезка - 0. В конце - ближе к единице. Короче если умножить нормализованный вектор полученный из текущего отрезка, на K, потом к начальной точке отрезка прибавить полученный вектор, то получим наши текущие координаты.

UPD: Чет я втыкаю (: А ведь действительно, можно просто умножить нормализованный вектор на пройденное по отрезку расстояние. И не нужно никаких коэфициентов...

Да, и ещё...
Если curspeed*=0.97, то такое движение не равнозамедленное (:

[Alex_beginner]

Теперь поговорим более подробно о методе со сплайнами.

Порядок такой:

1. Рассчитываете все коэффициенты сплайна по данным узловых точек;
2. Известно, что расстояние между двумя ближайшими точками рассчитывается как:

R = корень_квадратный((x2-x1)^2+(y2-y1)^2);
где

x1,y1 - координаты предыдущей рассчитаной точки на предыдущей итерации.
R - расстояние между двумя ближайшими точками;
Таким образом, на текущей итерации для данного уравнения неизвестны только x2,y2;
3. Предполагается, что если расстояние проходимое точкой на всех отрезках ломаной для каждой итерации будет одинаковым, то движение точки можно назвать равномерным, т.е. точка движется с постоянной скоростью. Теперь, если расстояние проходимое точкой в каждой итерции будет изменяться по линейному закону, то такое движение можно назвать равнозамедленным, либо равноускоренным, в соответсвующих случаях
4. Уравнение сплайна представляет собой функцию y=f(x), а приведенное выше уравнение, также может быть представлено в виде y=f(x) (здесь y=y2; x=x2). В результате мы имеем систему уравнений из двух уравнений и двух неизвестных, найдти корни которой в общем ввиде несоставит труда, если пользоваться методом подстановки.
5. Теперь используя коэффициент R как постоянную в каждой итерации мы получаем равномерное движение. Изменяем его по линейному закону получаем равнозамедленное или равноускоренное движение.
6. Вот, собственно, и вся теория.