Forum Webscript.Ru
Программирование => Теория, алгоритмы и стандарты => Тема начата: xnx от 08 Февраля 2003, 10:44:12
-
есть координаты начала и конца двух отрезков, очень сильно хочется определить пересекаются они или нет.
-
http://alglib.chat.ru/
Формально:
Первый отрезок: (x1(1),y1(1));(x2(1),y2(1)). Второй отрезок: (x1(2),y1(2));(x1(2),y1(2)). В результате может получится три варианта пересечения: точка, отрезок, пустое множество.
Прямая содержащая i-й отрезок задается при помощи уравнений:
x=x1(i)+t(i)(x2(i)-x1(i))
y=y1(i)+t(i)(y2(i)-y1(i))
при этом точка на прямой принадлежит отрезку, если t лежит внутри отрезка [0,1]. Следовательно, пересечением отрезков будет точка если существует решение (t(1),t(2)) системы:
t(1)(x2(1)-x1(1))+t(2)(x1(2)-x2(2))=x1(2)-x1(1)
t(1)(y2(1)-y1(1))+t(2)(y1(2)-y2(2))=y1(2)-y1(1)
и при этом и t(1) и t(2) лежат в отрезке [0,1]. Если хотя бы одно из t(i) не удовлетворяет этому условию, то пересечением отрезков будет пустой множество.
-
Яндекс рулит :)