ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Vadim Ajuev                          2:5023/39.10   06 Jul 2001  01:19:29
 To : Eugene Yadrikhinsky
 Subject : RE:Отрезки
 -------------------------------------------------------------------------------- 
 

 
 EY> Два отрезка заданы координатами начала и конца. Как определить 
 EY> пересекаются ли они, и если пересекаются, то найти координаты точки 
 EY> пересечения? 
 EY> 
 EY> Вывел формулы для пересечения двух линейных функций, а вот с отрезками
 EY> что-то не соображу...
 
 Имеем отрезки АВ и СD. Hаправленные отрезки АВ ми CD задаются так:
 P = A + r*(B - A) и 
 Q = C + s*(D - C)
 Для пересекающихся отрезков, очевидно, имеет место равенство
 A + r*(B - A) = C + s*(D - C), 
 или в координатной форме (*):
 Ax + r*(Bx - Ax) = Cx + s*(Dx - Cx) и
 Ay + r*(By - Ay) = Cy + s*(Dy - Cy)
 
 Система имеет единственное решение:
 
     (Ay - Cy)*(Dx - Cx) - (Ax - Cx)*(Dy - Cy)
 r = -----------------------------------------
     (Bx - Ax)*(Dy - Cy) - (By - Ay)*(Dx - Cx)
 
     (Ay - Cy)*(Bx - Ax) - (Ax - Cx)*(By - Ay)
 s = -----------------------------------------
     (Bx - Ax)*(Dy - Cy) - (By - Ay)*(Dx - Cx)
 
 ... если, конечно, (Bx - Ax)*(Dy - Cy) != (By - Ay)*(Dx - Cx) (в противном
 случае АВ и СD параллельны)
 
 Если 0 <= r <= 1 и 0 <= s <= 1, то отрезки АВ и СD пересекаются. Точки
 пересечения определяются из (*).
 
 Если ничего не перепутал и ветер будет дуть в нужную сторону, то, может быть,
 что-то будет работать (при соответствующем наборе данных) ;-))
 
    With best regards                [C++] [Galaxy Plus] [Quake] 
 Vadim Ajuev aka cre@tor              [Scouderia Ferrari] [RTS]
  * Origin: ... если не скончалась, она ещё жива. (с) Ч. Доджсон (2:5023/39.10)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Отрезки   Eugene Yadrikhinsky   04 Jul 2001 21:00:00   Re: Отрезки   Andrew Ezhguroff   05 Jul 2001 02:14:08   Отрезки   Nick Gorinov   05 Jul 2001 09:02:21   Re: Отрезки   Serge Kanilo   06 Jul 2001 03:01:14   Re: Отрезки   Andrew Ezhguroff   06 Jul 2001 03:09:17   Отрезки   Egorov Pavel   12 Jul 2001 20:32:28   Re: Отрезки   Serge Kanilo   13 Jul 2001 01:52:24   Отрезки   Egorov Pavel   14 Jul 2001 00:38:56   Отpезки   Alexander Hritonenkov   05 Jul 2001 03:18:12   Отpезки   Roman Vorobets   06 Jul 2001 11:56:40   Отpезки   Pavel Girnov   05 Jul 2001 01:40:57   Отрезки   Maxim Plaksin   05 Jul 2001 01:12:12   RE:Отрезки   Vadim Ajuev   06 Jul 2001 01:19:29