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

[Sibedir]

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

Прямую можно описать одной точкой и углом наклона. Одна точка - это наши P1 или P2. А угол накорна зависит от расности координат (tg(ф) = ΔY/ΔX = k). Имеем: y := k(x - X1) + Y1

б) что мне нужно учесть в формулах, чтоб просчитывались только отрезки, а не прямые, на которых они лежат?

ACE Valery, формулам глубоко фиолетово что они описывают, прямую или отрезок. Работать нужно не с формулами, а с математикой. Ладно, эт всё лирика.

Задача
Имеем 2-а отрезка заданые 2-ми точками. Надо определить, пересекаются ли эти отрезки и если да, то найти точку пересечения.

Рассуждения:
Первое:
Отрезки пересекаются = Имеется общая точка
Общая точка = Точка пересечения
Точка пересечения отрезков = Точка пересечения прямых, на которых лежат отрезки

Далее
Отрезки пересекаются, если выполняются 2 условия:
- прямые, на которых лежат отрезки, пересекаются;
- координата точки пересечения прямых лежит внутри диапозонов координат (проекций на оси) обоих отрезков.

Прямые же пересекаются, если имеют разные углы наклона

Окей
Имеем 3 задачи:
1. Прямые пересекаются -> tg(ф1) <> tg(ф2)
2. Точка пересечения -> решение системы уравнений
3. Точка внутри отрезна ->
X <= max(X1, X2)
X >= min(X1, X2)
Y <= max(Y1, Y2)
Y >= min(Y1, Y2)

Ремарка
Прикол в том, что прямые пересекаются чуть реже чем всегда, а расчет tg(ф) требует работы с дробями. Поэтому проверять это условие первым не целесообразно. Для отсечения большого куска заведомо непересекающихся пар можно проверить следующие условия:
max(X11, X12) >= min(X21, X22)
max(Y11, Y12) >= min(Y21, Y22)
Далее всё окей.

Короче
1. Отсекаем заведомо непересекающиеся пары
max(X11, X12) >= min(X21, X22)
max(Y11, Y12) >= min(Y21, Y22)

2. Прямые пересекаются
k1 = tg(ф1)
k2 = tg(ф2)
k1 <> k2

3. Координата X точки пересечения
f1(x) = f2(x)

4. Точка внутри отрезков
X <= max(X11, X12) X >= min(X11, X12)
X <= max(X21, X22) X >= min(X21, X22)

5. Координата Y точки пересечения
Y := f1(X)

[phomm]

Накроил по наводке Serge_Bliznykov (а по его наводке лежит совет от Rin ссылающийся на жж некоего программера на плюсах) программку на сишарпе (правда, "искаропки" там нет векторных операций, пришлось чуть-чуть подпортить код).
Будет полигончик для отработки алгоритмов. Можно навернуть проверку скорости работы даже

[ACE Valery]

phomm, спасибо большое за программку.

Но все-таки это уже дело чести - разобраться.

Sibedir, мне уже тут многие приводили кучу непонятных формул, но мало кто попытался что-то объяснить. В таком виде формулы я и в учебниках читаю...

1. Прямые пересекаются -> tg(ф1) <> tg(ф2)

Что такое ф1 и ф2? Откуда они взялись?

max(X11, X12) >= min(X21, X22)
max(Y11, Y12) >= min(Y21, Y22)

Что такое X11, X12, X21, X22 и т.п. Откуда взялись эти уравнения?

Ну и далее по тексту сплошные ф1 и ф2.

[BDA]

Думаю, Sibedir не обидится, если поясню за него.
ф1 и ф2 - углы наклона 2 данных прямых, на которых лежат отрезки. Угол наклона считается от горизонтальной оси против часовой стрелки.
"Откуда они взялись?" - пока не откуда, это просто признак пересечения прямых.
x11 и x12 - координаты по x начала и конца первого отрезка (первый индекс - номер отрезка, второй индекс - номер вершины). Правда, на мой взгляд, условий на не пересечение из ремарки не хватает (грубо говоря, это проверка на пересечение двух прямоугольников, описывающих отрезки, а в ремарке рассматривается только частный случай такой проверки, или я как-то не так понял эту ремарку).

[Arigato]

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

Надеюсь, поможет:

struct point{ //  точка
	double x,y;
};

struct line{ // прямая a*x+b*y+c=0
	double a,b,c;
};

line getLine(point p1,point p2){ // из уравнения прямой по двум точкам перейти к общему уравнению прямой
	line res={p1.y-p2.y,p2.x-p1.x,p1.x*p2.y-p2.x*p1.y};
	return res;
}

double det(double a, double b, double c, double d){ // Нахождение определителя
	return a*d-b*c;
}

bool intersect(line m,line n,point &res){ // Определение точки пересечения двух прямых
	double zn=det(m.a,m.b,n.a,n.b);
	if(zn==0)
		return false;
	res.x=-det(m.c, m.b, n.c, n.b)/zn;
	res.y=-det(m.a,m.c,n.a,n.c)/zn;
	return true;
}

bool segmentsCross(point p1,point p2,point p3,point p4){ // Определение пересечения двух отрезков (p1,p2) и (p3,p4)
	double num1=(p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x); // тут можно через уравнение прямой и определитель, как сделано выше
	double num2=(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x);
	double den =(p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y);
	if (den==0) // отрезки совпадают или параллельны
		return false; // считаем их непересекающимися
	double a=num1/den;
	double b=num2/den;
	return (0<=a && a<=1) && (0<=b && b<=1); // определяем факт пересечения
}

bool pointInSegment(point p1,point p2,point p){ // Принадлежит ли точка p отрезку (p1,p2)
	double den1=p1.x-p2.x;
	if (den1==0){ // отрезок параллелен оси OY
		double len=abs(p1.y-p2.y);
		return (p.x==p1.x) && (abs(p.y-p1.y)<=len && abs(p.y-p2.y)<=len);
	}
	double den2=p1.y-p2.y;
	if (den2==0){ // отрезок параллелен оси OX
		double len=abs(p1.x-p2.x);
		return (p.y==p1.y) && (abs(p.x-p1.x)<=len && abs(p.x-p2.x)<=len);
	}
	double num1=p.x-p2.x;
	double num2=p.y-p2.y;
	double k1=num1/den1;
	double k2=num2/den2;
	return (k1==k2) && (0<=k1 && k1<=1);
}

С геометрией у меня тоже не очень, но вроде все работает, во всяком случае я эти функции использовал, проблем не было.

[ACE Valery]

Arigato, BDA, спасибо.