Точка пересечения отрезков

[Witaliy]

Даны координаты начала и конца двух отрезков. Нужно кзнать точку пересечения естих отрезков. Pascal. Спасибо.

[PAWLO1993]

Можно перейти к уравнениям прямых и найти точку пересечения прямых, что сделать очень просто и если точка пересечения будет принадлежать двум отрезкам, то это будет искомая точка, а если нет, то отрезки не пересекаются.
Уравнение прямой на плоскости, проходящей через две заданные точки (x1,y1) и (x2,y2) можно найти так:
a=y1-y2
b=x2-x1
c=-(a*x1+b*y1)
Для нахождения точки пересечения двух прямых нужно розвязати простую систему уравнений: A1x+B1y+C1=0 и A2x+B2y+C2=0

[nestr]

Все очень просто!
х1, у1 и х2,у2 - координаты вершин первого отрезка;
х3, у3 и х4,у4 - координаты вершин второго отрезка;

для нахождения пересечения составляем уравнения прямых:
первое уравнение:
(x-x1)/(x2-x1)=(y-y1)/(y2-y1);
второе уравнение
(x-x3)/(x4-x3)=(y-y3)/(y4-y3);
эти уравнения определяют прямую проходящую через две точки, то, что нам и надо.
Из этих уравнений находим х и у по следующим формулам:
x:=((x1*y2-x2*y1)*(x4-x3)-(x3*y4-x4*y3)*(x2-x1))/((y1-y2)*(x4-x3)-(y3-y4)*(x2-x1));
y:=((y3-y4)*x-(x3*y4-x4*y3))/(x4-x3);
так как наши прямые пересекаются, то у них есть общая точка пересечения с координатами (х,у), которую нам и надо найти.
для того, чтоб пересечение принадлежало нашим отрезкам, нужно его ограничить, т. е проверить условие:
если
(((x1<=x)and(x2>=x)and(x3<=x)and(x4 >=x))or((y1<=y)and(y2>=y)and(y3<=y) and(y4>=y)))
то существует точка пересечения данных отрезков, а нет – то нет и точки пересечения.
Еще следует проверить параллельность этих отрезков при помощи угловых коэффициентов:
k1:=(x2-x1)/(y2-y1);
k2:=(x4-x3)/(y4-y3);
где k1 и k2 – тангенсы угла наклона отрезков к положительному направлению оси ОХ, если k1=k2, то отрезки параллельны, а значит, не имеют точек пересечения.

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

если остались вопросы или нужны исходники программ, пишите на мыло alexander.nestr@mail.ru или в icq 558213677.

[juliaaaa]

.....очень интересно,

[serpoverst]

Готовая функция.

POINT Point_X(POINT a1,POINT a2,POINT a3,POINT a4){
	POINT T;
	if(((a1.x<=T.x)&&(a2.x>=T.x)&&(a3.x<=T.x)&&(a4.x >=T.x))||((a1.y<=T.y)&&(a2.y>=T.y)&&(a3.y<=T.y)&&(a4.y>=T.y))){
		float x1=a1.x,x2=a2.x,x3=a3.x,x4=a4.x,y1=a1.y,y2=a2.y,y3=a3.y,y4=a4.y;
		float k1,k2;
		if(y2-y1!=0){
			k1=(x2-x1)/(y2-y1);
			if(y4-y3!=0){
				k2=(x4-x3)/(y4-y3);
				if(k1!=k2){
					T.x=((a1.x*a2.y-a2.x*a1.y)*(a4.x-a3.x)-(a3.x*a4.y-a4.x*a3.y)*(a2.x-a1.x))/((a1.y-a2.y)*(a4.x-a3.x)-(a3.y-a4.y)*(a2.x-a1.x));
					T.y=((a3.y-a4.y)*T.x-(a3.x*a4.y-a4.x*a3.y))/(a4.x-a3.x);
					T.x*=-1;
					return T;
				}else{
					T.x=969; T.y=969;
					//text2("Паралельны");
				}
			}else{
				T.x=969; T.y=969;
				//text2("Паралельны");
			}
		}else{
			T.x=969; T.y=969;
			//text2("Паралельны");
		}
	}else{
		//text2("Пересечение вне отрезка");
		T.x=979; T.y=979;
		return T;
	}

}

[Painy]

Сообщение от serpoverst

Готовая функция.

POINT Point_X(POINT a1,POINT a2,POINT a3,POINT a4){
	POINT T;
	if(((a1.x<=T.x)&&(a2.x>=T.x)&&(a3.x<=T.x)&&(a4.x >=T.x))||((a1.y<=T.y)&&(a2.y>=T.y)&&(a3.y<=T.y)&&(a4.y>=T.y))){
		float x1=a1.x,x2=a2.x,x3=a3.x,x4=a4.x,y1=a1.y,y2=a2.y,y3=a3.y,y4=a4.y;
		float k1,k2;
		if(y2-y1!=0){
			k1=(x2-x1)/(y2-y1);
			if(y4-y3!=0){
				k2=(x4-x3)/(y4-y3);
				if(k1!=k2){
					T.x=((a1.x*a2.y-a2.x*a1.y)*(a4.x-a3.x)-(a3.x*a4.y-a4.x*a3.y)*(a2.x-a1.x))/((a1.y-a2.y)*(a4.x-a3.x)-(a3.y-a4.y)*(a2.x-a1.x));
					T.y=((a3.y-a4.y)*T.x-(a3.x*a4.y-a4.x*a3.y))/(a4.x-a3.x);
					T.x*=-1;
					return T;
				}else{
					T.x=969; T.y=969;
					//text2("Паралельны");
				}
			}else{
				T.x=969; T.y=969;
				//text2("Паралельны");
			}
		}else{
			T.x=969; T.y=969;
			//text2("Паралельны");
		}
	}else{
		//text2("Пересечение вне отрезка");
		T.x=979; T.y=979;
		return T;
	}

}

Вот тут поподробнее пожалуйста!
Как быть с делением на 0? Поставьте второй отрезок вертикально и и пересчитайте точку - получите DivideByZeroException
На C# не катит деление на 0, неужели в С++ подругому?
Вопрос 2, как вы входите в первый if, если значения Т неизвестны?
Вопрос 3, что за значения Т в esle, нахаляву?