Векторная алгебра

[evg_m]

Всю тему просмотрел, но не детально поэтому ответ только на последний пост (без учета предыдущих).

прямая задана двумя точками.

ax+by =c
две точки (x1,x2) (x2,y2)
прямая (y1-y2)*x + (x2-x1)*y + (x1*y2-x2*y1) = 0
четыре стены (еще четыре прямые) параллельные осям координат (сторонам экрана монитора поэтому верт./ горизонт.)
y=0 | x=0 | y=m | x=n

расстояние от которой до стены будет равно 10.

это новые прямые
y=0+10 | m-10 ( для горизонтальных стен (сторон монитора))

пересечение двух прямых =решение системы двух уравнений
(y1-y2)*x + (x2-x1)*y + (x1*y2-x2*y1) = 0
y=10 (для одной из вертикальных стен)

(y1-y2)*x + (x2-x1)*10 + (x1*y2-x2*y1) = 0
x=0-( (x2-x1)*10 + (x1*y2-x2*y1) ) / (y1-y2)

Исходя из этих данных я могу найти эту точку?

y=10 (для одной из вертикальных стен)
x=0-( (x2-x1)*10 + (x1*y2-x2*y1) ) / (y1-y2)

[ACE Valery]

четыре стены (еще четыре прямые) параллельные осям координат (сторонам экрана монитора поэтому верт./ горизонт.)

Не факт, что параллельны осям координат. Стены могут находиться под каким-либо углом к осям координат.

[Abstraction]

Abstraction, а вот этот угол я как раз не знаю.

Ну так каждое значение ф порождает свою картинку (по сути, весь чертёж можно крутить вокруг точки А на любой угол, и все углы и длины сторон сохранятся).

прямая (L) задана двумя точками. А между этими точками есть еще одна точка (P), расстояние от которой до стены (W) будет равно 10. Исходя из этих данных я могу найти эту точку?

Да, разумеется. Но если L не параллельна W, то есть неоднозначность: таких точек две, по одной с каждой стороны стены.
Пусть прямая W задана уравнением x*Wx + y*Wy + Wz = 0, причём Wx^2+Wy^2 = 1. Будем называть такое задание произвольной прямой её нормальной формой. Пусть также известно, что "наша" сторона стены - это полуплоскость x*Wx + y*Wy + Wz > 0.
Аналогично, пусть прямая L задана уравнением x*Lx + y*Ly + Lz = 0 и Lx^2+Ly^2 = 1. Эту форму можно построить по двум точкам: взять уравнение (x-x2)(y1-y2) - (x1-x2)(y-y2) = 0, и поделить на ((x1-x2)^2+(y1-y2)^2). Тогда точка P определена парой уравнений:
x*Lx + y*Ly + Lz = 0,
x*Wx + y*Wy + Wz = 10.
Формулу написать можно, но проще написать код:

Point PointOnLineDistantFromLine(Line L, Line W, double d){
  Point ret;
  double det = L.x*W.y-L.y*W.x;
  if(det==0) throw LinesParallelIntersectionException();
  ret.x = (-W.y*L.z+L.y*W.z-L.y*d) / det;
  ret.y = (W.x*L.z-L.x*W.z+L.x*d) / det;
  return ret;
}

[evg_m]

Не факт, что параллельны осям координат. Стены могут находиться под каким-либо углом к осям координат.

а зачем выбирать такую систему координат. Вы можете использовать любую систему координат. В т.ч. такую чтобы оси совпадали с двумя вашими стенками (именно тогда х=0/ y=0). Упоминание о мониторе было только для того чтобы "объяснить" употребление слова "горизонтальное" применительно к оси y.

второй вариант. У любой стены опять же есть координаты двух ее окончаний(углов). Т.е. есть две точки, значит есть уравнение прямой проходящей через эти две точки. Заменяем простое уравнение прямой параллельной оси (y=10) на общее уравнение прямой проходящей через концы стены(углы) и решаем.

[ACE Valery]

Пусть прямая W задана уравнением x*Wx + y*Wy + Wz = 0

Ну вот о чем я и говорю постоянно - не понимаю я этих книжных формул. Что это за уравнение? И почему мы решили, что моя прямая им задана? Я об этой прямой знаю только, что она - перпендикуляр к прямой L.

Пусть также известно, что "наша" сторона стены - это полуплоскость x*Wx + y*Wy + Wz > 0

Аналогично - не известно. То есть я вижу, какая "наша" сторона, а как об этом сказать компьютеру?

Вот что меня и смущает в учебниках геометрии. "Пусть известно". Не известно ничего. Известно только то, что я написала. Если из этого можно что-то вывести, подскажите, как. Я не издеваюсь, у меня правда сложности с применением математических формул в программировании.

есть уравнение прямой проходящей через эти две точки

Да, есть. Но я как-то не поняла ваш подход. Разве на параллельной прямой не все точки будут иметь расстояние до данной прямой, равное 10?

Еще раз что я хочу сделать:
круги.png
Есть шар с центром в С (координаты известны), он находится от прямой АВ (заданной двумя точками) на расстоянии, скажем, 13. Через какой-то промежуток времени шар пересчитывает координаты, и теперь его центр с точке D(координаты известны), расстояние до прямой АВ, скажем, 8. Мне нужно, чтобы шар не залетал никаким образом за прямую АВ, т.е. чтобы расстояние от центра до АВ никогда не превышало радиус шара (скажем, 10). Поэтому на этой итерации я хочу оттолкнуть шар в такую точку, где его расстояние до АВ станет 10. Но я не знаю координат этой точки. Вот их мне нужно узнать.

[Abstraction]

Ну вот о чем я и говорю постоянно - не понимаю я этих книжных формул. Что это за уравнение? И почему мы решили, что моя прямая им задана? Я об этой прямой знаю только, что она - перпендикуляр к прямой L.

Тогда с самого начала. Прямая на плоскости - некоторое множество точек. Прямая в программе - некоторая структура данных. Одно с другим можно связать с помощью математической модели. Достаточно удобный вариант такой модели - тройка чисел (Wx, Wy, Wz), такая что Wx^2+Wy^2=0. Такую тройку можно организовать в программе и соотнести с прямой на плоскости.

Соответственно, пусть у нас есть прямая L в виде (Lx, Ly, Lz). Её можно построить по двум точкам, по точке и вектору, по ещё чему-нибудь... неважно, она есть. В любой точке можно построить к ней перпендикуляр (читайте - другую тройку чисел, представляющую перпендикулярную прямую). На уровне кода:

Line BuildPerpendicular(Line to, Point through);

//...
Line W = BuildPerpendicular(L, somePoint);

Всё, у нас есть прямая W. А прямая L была получена где-то выше по коду.

Аналогично - не известно. То есть я вижу, какая "наша" сторона, а как об этом сказать компьютеру?

Так же, как сказали ему о каких-то точках. Можно сделать функцию вида

MakePositiveHalf(Line* pLine, Point p);

, которая бы делала "положительной" полуплоскостью ту, к которой принадлежит точка p. Достаточно точной аналогией является модель полигона в OpenGL - она тоже требует от программиста отслеживать не только вершины полигона, но и разницу между "внешней" и "внутренней" стороной.

Да, есть. Но я как-то не поняла ваш подход. Разве на параллельной прямой не все точки будут иметь расстояние до данной прямой, равное 10?

Так она не параллельна. Смотрите:

Есть шар с центром в С (координаты известны), он находится от прямой АВ (заданной двумя точками) на расстоянии, скажем, 13. Через какой-то промежуток времени шар пересчитывает координаты, и теперь его центр с точке D(координаты известны), расстояние до прямой АВ, скажем, 8. Мне нужно, чтобы шар не залетал никаким образом за прямую АВ, т.е. чтобы расстояние от центра до АВ никогда не превышало радиус шара (скажем, 10). Поэтому на этой итерации я хочу оттолкнуть шар в такую точку, где его расстояние до АВ станет 10. Но я не знаю координат этой точки. Вот их мне нужно узнать.

Line wall = BuildLineByPoints(A, B);
Line ballCourse = BuildLineByPoints(C, D);
MakePositiveHalf(&wall, C);
Point newBallPosition;

if(DistanceToLine(wall, D) < radius){
  newBallPosition = PointOnLineDistantFromLine(ballCourse, wall, radius);
} else {
  newBallPosition = D;
}

На этом уровне абстракции конкретное представление линий и точек несущественно. А уровнем ниже, в предлагаемом мной варианте, имеем:

Line BuildLineByPoints(Point a, Point b){
  Line ret;
  double norm = hypot(a.x-b.x, a.y-b.y);
  ret.x = (b.y-a.y)/norm;
  ret.y = (a.x-b.x)/norm;
  ret.z = (b.x*a.y - a.x*b.y)/norm;
  return ret;
}

void MakePositiveHalf(Line* l, Point p){
  if(DistanceToLine(*l, p) >= 0) return;
  l->x = -l->x;
  l->y = -l->y;
  l->z = -l->z;
}

double DistanceToLine(Line l, Point p){
  return p.x*l.x + p.y*l.y + l.z;
}

[ACE Valery]

В общем, поднасобирав инфы тут и в книгах, в результате получила такое решение (вдруг кому понадобится)

// функция принимает две точки прямой, с которой собираемся сталкиваться
// и время шага в секундах (т.е. у меня проверка на столкновение 
//делалась раз в 10 мс, поэтому 10/1000 = 0.01)
//возвращает данные о том, коснулся ли шар линии

public function isHitLine(beginLine : Point, endLine : Point, dt : Number) : Boolean {	
	
//вычисляем, в какой точке шарик будет через заданное время	
var newPosition : Point = setNewPositionDt(dt);	

//вычисляем расстояние до линии от той точки, в которую подвинется шарик		
var d : Number = VectorUtils.getDistanseFromPointToLine(newPosition, beginLine, endLine);

//вычисляем текущее расстояние до линии
var nowDist:Number = VectorUtils.getDistanseFromPointToLine(position, beginLine, endLine);
	
//смотрим, лежат ли точки текущего положения шарика 
//и следующего в одной плоскости (т.е. не перекатился ли центр шара за линию)	
var pointsAtSamePlain:Boolean = isPointsAtSamePlain(position, newPosition, beginLine, endLine);

// тут все понятно: если шар четко прикоснулся к линии, то возвращаем
// сведения что есть пересечение, если не дошел до линии, то нет	
	if (Math.ceil(d) == radius && pointsAtSamePlain) {
		return true;
	}
	if (Math.ceil(d) > radius && pointsAtSamePlain) {
		return false;
	}	

// это в случае, если шар зашел за линию, вычисляем, какое расстояние
//он прошел за переданное в функцию время 
	var distByDt:Number = pointsAtSamePlain ? (nowDist - d) : (nowDist + d);

// вычисляем, какое расстояние он должен был пройти, 
//чтобы только прикасаться к линии
	var needDist:Number = nowDist - radius;

// вычисляем время, необходимое для того, чтобы шар как раз только коснулся линии
	var newDt:Number = (needDist * dt) / distByDt;

//двигаем шар на это время		
	move(newDt);

// возвращаем, что шар коснулся линии			
	return true;
}

Проверка на то, находятся ли точки в одной полуплоскости

private function isPointsAtSamePlain(point1:Point, point2:Point, beginLine:Point, endLine:Point):Boolean 
{
	var f1:Number = (point1.x - beginLine.x) / (endLine.x - beginLine.x) - 
			(point1.y - beginLine.y) / (endLine.y - beginLine.y);
	var f2:Number = (point2.x - beginLine.x) / (endLine.x - beginLine.x) - 
			(point2.y - beginLine.y) / (endLine.y - beginLine.y);
	if (f1 == 0 && f2 == 0) return true;
	if ((f1 > 0 && f2 > 0) || (f1 < 0 && f2 < 0)) return true;
	return false;
}

Расстояние от точки до линии, заданной двумя точками

static public function getDistanseFromPointToLine(point : Point, beginLine : Point, endLine : Point) : Number {
	var vectorToPoint : Point = new Point(beginLine.x - point.x, beginLine.y - point.y);
	var lineVector : Point = new Point(endLine.x - beginLine.x, endLine.y - beginLine.y);
	var distance:Number = Math.abs(getPseudoScalar(vectorToPoint, lineVector) / getVectorLength(lineVector));
			
	return distance;			
}

Векторное произведение векторов в двумерном пространстве

static public function getPseudoScalar(vector1:Point, vector2:Point):Number {
	return vector1.x * vector2.y - vector1.y * vector2.x;
}

Длина вектора

static public function getVectorLength(vector:Point):Number {
	return Math.sqrt(Math.pow(vector.x, 2) + Math.pow(vector.y, 2));
}

З.Ы. Сорри за форматирование, ничего лучше не получилось((

[ACE Valery]

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

Собственно вопрос:
а) как из уравнения прямой по двум точкам перейти к общему уравнению прямой (ибо в учебниках только с его помощью находятся пересечения)?
б) что мне нужно учесть в формулах, чтоб просчитывались только отрезки, а не прямые, на которых они лежат?

[Poma][a]

Качаем книжку : тыц

Открываем задачу 2D - понимаем, что это по нашей теме..
И там есть 2 решения.. стр.114 и далее..

[Serge_Bliznykov]

я, в свою очередь тоже вставлю свои "5 копеек"
во-первых, тема "Пересечение отрезков"
не оно?

а во-вторых, там в теме мой пост, это из книги
С. Окулов. Программирование в алгоритмах

взять можно
тут
или
тут