Программирование > Теория, алгоритмы и стандарты

определение пересеченности прямых...

(1/1)

xnx:
есть координаты начала и конца двух отрезков, очень сильно хочется определить пересекаются они или нет.

ThE0ReTiC:
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) не удовлетворяет этому условию, то пересечением отрезков будет пустой множество.

Mog.:
Яндекс рулит :)

Навигация

[0] Главная страница сообщений