Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Пересекаются ли отрезки?

Даны два отрезка
Необходимо проверить, пересекаются ли они

Если два конца первого отрезка имеют разные знаки положения относительно прямой, проходящей через второй отрезок, и аналогичное условие выполняется для второго отрезка, то отрезки пересекаются.
Если оба отрезка лежат на одной прямой, то отрезки будут пересекаться, если граница одного отрезка принадлежит другому.


Листинг C++

bool is_cross_segment (point p1, point p2, point p3, point p4)
{
    line l1 = toline(p1, p2);
    line l2 = toline(p3, p4);
    int sign1 = point_in_line(l1, p3) * point_in_line(l1, p4);
    int sign2 = point_in_line(l2, p1) * point_in_line(l2, p2);

    if (abs(sign1) <= eps && abs(sign2) <= eps)
        return point_in_box(p1, p3, p4) || point_in_box(p2, p3, p4) ||
               point_in_box(p3, p1, p2) || point_in_box(p4, p1, p2);
    return sign1 <= eps && sign2 <= eps;
}

25.06.2007, 16:49