Помогите придумать алгоритм

[zemer]

Здравствуйте уважаемые форумчани!

На графике системы координат в пространстве расположены 3 точки. Две из них статичные точки на рисунке обозначены зеленым цветом. Через них проходит прямая линия, которая начинается в точке x1,y1 пересекает точку x2,y2 и продолжается.

Третья точка динамичная – обозначена красным цветом. По условию эта точка может двигаться хаотично вверх или вниз и пересекать линию. Точка двигается только вперед по координате Х. В моем случаи это временной диапазон, но я не буду этим усложнять задачу. Достаточно понять, что точка двигается только вперед по горизонтали.

После получения координат первых двух зеленых точек, нужно определить в какой момент динамичная красная точка пересечет линию.

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

[dark256]

Системы линейных уравнений.
Первые 2 точки задают линейное уравнение.
Для третьей точки подставляете Х, получаете У и проверяете на равенство.

[undefined]

первая ссылка в гугле
Уравнение прямой по двум точкам:
(y-y1)/(y2-y1)=(x-x1)/(x2-x1)
Подставляешь вместо x,y свои x3,y3.Если равенство выполняется - значит точка лежит на прямой
Хотя лучше проверять не строгое равенство, а приближенно, т.к. точно на прямую точка редко когда будет попадать:

var eps:Number=1e-4;
var delta:Number=(y3-y1)/(y2-y1)-(x3-x1)/(x2-x1);
if (Math.abs(delta)<eps) {
...
}

Чем меньше eps,тем точнее точка x3,y3 должна попасть на прямую чтоб условие сработало.

[zemer]

Спасибо! Отличный результат, вопрос исчерпан. Все гениальное просто!

Добавлено через 55 минут


Помогите еще определить 5 точку(оранжевым цветом) пересечения двух линий, если известно 2 точки первой линии и 2 точки второй линии.

[undefined]

Параметрическое уравнение прямой 1-2:
x(t)=(x2-x1)*t+x1;
y(t)=(y2-y1)*t+y1;(1)
Надо найти такой t,чтоб точка x(t),y(t) лежала еще и на прямой 3-4
Для этого подставляем x(t),y(t) в уравнение из предыдущего поста:
(y(t)-y3)/(y4-y3)=(x(t)-x3)/(x4-x3)
Раскрываем скобки,приводим подобные и выражаем t.Подставляем найденный t в (1) и получаем искомые координаты.Все выкладки оставляю автору для тренировки.

Добавлено через 27 минут
Да забыл момент- надо отдельно обрабатывать случай если y4=y3 (прямая 3-4 параллельна оси X) случай x4=x3 как я понял исключен

[zemer]

t = (((y4-y3)/((y2-y1)+(y1-y3)))-((x4-x3)/((x2-x1)+(x1-x3))))*2;
y5 = (y2-y1)*t+y1;
x5 = (x2-x1)*t+x1;

но у меня почему-то точка сходиться, вроде верно подсчитал
Формула

[undefined]

но у меня почему-то точка сходиться

Как это?

[zemer]

Вот подвигай за зеленые кружки и сам увидишь
файл

[undefined]

значит t неверно посчитал.Подставь свои x5,y5 в
(y5-y3)/(y4-y3)=(x5-x3)/(x4-x3)
и проверь выполняется ли равенство

Добавлено через 12 минут
да, явно не то ты насчитал:

var x1:Number=0;
var y1:Number=0;
 
var x2:Number=50;
var y2:Number=100;
 
var x3:Number=100;
var y3:Number=50;
 
var x4:Number=20;
var y4:Number=100;
var t:Number=(((y4-y3)/((y2-y1)+(y1-y3)))-((x4-x3)/((x2-x1)+(x1-x3))))*2;
trace(t);//-1.2000000000000002 (неверно)
/*
this.graphics.lineStyle(1,0,1);
this.graphics.moveTo(x1,y1);
this.graphics.lineTo(x2,y2);
 
this.graphics.moveTo(x3,y3);
this.graphics.lineTo(x4,y4);
*/
var x5:Number=(x2-x1)*t+x1;
var y5:Number=(y2-y1)*t+y1;
trace((y5-y3)/(y4-y3),(x5-x3)/(x4-x3));//-3.4 2(неверно)

t должно лежать в диапазоне [0,1] т.к. точка пересечения лежит между точками 1-2