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

Ноябрь 5, 2007

Пересечение двух отрезков

Уравнения линий имеют вид

Уравнения линий

Решение относительно точки Pa = Pb дает два уравнения на координаты (ua и ub)

Уравнения линий

Решая относительно ua и ub имеем

Уравнения линий

Подстановка любого из этих значений в соответствующее уравнение прямой даст точку пересечения. Пусть, например, точка пересечения (x,y):

Уравнения линий

Замечания

  • Знаменатели одинаковы.
  • Если знаменатель равен нулю, то прямые параллельны.
  • Если и числитель и знаменатель равны нулю, то прямые совпадают.
  • Если нужно найти пересечение отрезков, то нужно лишь проверить, лежат ли ua и ub на промежутке [0,1]. Если какая-нибудь из этих двух переменных 0 <= ui <= 1, то соответствующий отрезок содержит точку пересечения. Если обе переменные приняли значения из [0,1], то точка пересечения прямых лежит внутри обоих отрезков.

Пример реализации

inline bool isLinesHasIntersection(Vector4 p1, Vector4 p2, Vector4 p3, Vector4 p4, Vector4& pos)
{
	// (y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)
	float denominator = (p4.y - p3.y)*(p2.x - p1.x) - (p4.x - p3.x)*(p2.y - p1.y);
	if(denominator == 0)
		// прямые паралельны
		// Если и числитель и знаменатель равны нулю, то прямые совпадают.
		return false;
	else
	{
		float u12 = ((p4.x - p3.x)*(p1.y - p3.y) - (p4.y - p3.y)*(p1.x - p3.x))/denominator;
		float u34 = ((p2.x - p1.x)*(p1.y - p3.y) - (p2.y - p1.y)*(p1.x - p3.x))/denominator;
		//x = x1 + ua (x2 - x1)
		pos = p1 + (p2 - p1)*u12;

		// Если u12 и u34 на промежутке [0,1], значит отрезки имеют точку пересечения
		if(u12 < 0 || u12 > 1)
			// точка пересечения не на отрезке p1, p2
			return false;
		if(u34 < 0 || u34 > 1)
			// точка пересечения не на отрезке p3, p4
			return false;
	}
	return true;
}
			

Реализацию класса Vector4 смотрите тут.

Обсудить в форуме.


Раз вы уже дочитали до сюда, то вам ничего не будет стоить кликнуть на рекламу

All content copyright (c) 2012 Vladislav Litunovskiy. All Rights Reserved.