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



Даны два отрезка
Необходимо найти их какую-либо общую точку или установить, что её нет

Алгоритм проверки:
    1) Создаём прямые проходящие через эти отрезки.
    2) Проверяем все вырожденные случаи.
    3) Находим точку пересечения прямых.
    4) Проверяем принадлежность точки пересечения прямых двум отрезкам.

Листинг C++

bool cross_segment (point p1, point p2, point p3, point p4, point &t)
{
    // Строим прямые проходящие через эти отрезки и пересекаем их
    line l1 = toline(p1, p2);
    line l2 = toline(p3, p4);

    int flag = cross_line(l1, l2, t);
    if (flag == 0) return false;
    
    // Если прямые совпадают, проверяем каждый конец отрезка на принадлежность другому отрезку
    if (flag == 2)
    {
        if (point_in_box (p1, p3, p4)) { t = p1; return true; }
        if (point_in_box (p2, p3, p4)) { t = p2; return true; }
        if (point_in_box (p3, p1, p2)) { t = p3; return true; }
        if (point_in_box (p4, p1, p2)) { t = p4; return true; }
        return false;
    }
    // Если прямые пересекаются, проверяем принадлежит ли точка пересечения обоим отрезкам
    return point_in_box (t, p1, p2) && point_in_box (t, p3, p4);
}

07.01.2008


По всем вопросам обращаться: rumterg@gmail.com