Как найти пересечение отрезков на числовой прямой

Оглавление

1. Расположение отрезков на плоскости
2. Параметрическое уравнение отрезка
3. Найти точку пересечения двух отрезков
4. Отрезки не пересекаются
5. Метод SegmentSegment(…)
6. Исходник приложения с классом Intersections

Расположение отрезков на плоскости

Два отрезка могут иметь различные положения на плоскости относительно друг друга. Поскольку отрезок ограниченная с двух сторон линия, данная геометрическая фигура предлагает больше вариантов расположения в сравнении с прямой и лучом.

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

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

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

Параметр может иметь ограничения или не иметь их.

система из параметрических уравнений:
| x = x0 + vt
| y = y0 + wt

где v и w координаты (x, y) вектора направления
v =  x1 - x0
w = y1 + y0

при  0 ≤ t ≤ 1 - уравнения описывают отрезок,
при  0 ≤ t < +∞ - уравнения описывают луч,
при -∞ < t < +∞ - уравнения описывают прямую

Найти точку пересечения двух отрезков

Система из 4-х параметрических уравнений позволяет найти точку пересечения двух отрезков. Нахождение точки пересечения отрезков аналогично описанному для двух лучей.

Дано: отрезок AB с координатами начальной и конечной точек – A(2;2) и B(7;3), отрезок CD с координатами – C(4;1) и D(5;6). Найти возможную точку пересечения отрезков AB и CD.

Отрезки имеют точку пересечения если оба параметра отрезков больше или равно нулю и меньше или равно единице.

| x = 2 + (7 - 2)tab    | x = 2 + 5tab
| y = 2 + (3 - 2)tab => | y = 2 + tab
| x = 4 + (5 - 4)tcd    | x = 4 + tcd
| y = 1 + (6 - 1)tcd    | y = 1 + 5tcd

Чтобы узнать есть ли точка пересечения отрезков AB и CD вычислим их параметры:

найдём соотношение параметров через возможно общую координату x
2 + 5tab = 4 + tcd =>  
5tab = 2 + tcd =>
tab = (2 + tcd)/5 (у.1)

вычислим параметр tcd через возможно общую координату y
2 + tab = 1 + 5tcd =>
2 + (2 + tcd)/5 = 1 + 5tcd =>
10 + 2 + tcd = 5 + 25cd =>
tcd = 7/24 ≈ 0.292

вычислим параметр tab использую полученное соотношение (у.1)
tab = (2 + 0.292)/5 ≈ 0.458 

Оба параметра положительные и меньше единицы – отрезки пересекаются. Найдем точку пересечения используя уравнения из системы для двух отрезков:

x = 2 + 5tab =>
x = 2 + 5 * 0.458 = 4.29
y = 2 + tab =>
y = 2 + 0.458 = 2.458

Точка пересечения отрезков AB и CD имеет координаты (4.29; 2.458).

Отрезки не пересекаются

Отсутствие точки пересечения двух отрезков, безусловно, также подтверждается вычислением.

Дано: отрезок AB с координатами начальной и конечной точек – A(5;4) и B(10;5), отрезок CD с координатами – C(3;3) и D(7;6). Определить: отрезки пересекаются или не пересекаются. Если отрезки не пересекаются, найти мнимую точку пересечения.

Отрезки не пересекаются если хотя бы один из параметров отрицательный или больше единицы. Для вычисления используем систему из параметрических уравнений.

| x = 5 + (10 - 5)tab   | x = 5 + 5tab
| y = 4 + (5 - 4)tab => | y = 4 + tab
| x = 3 + (7 - 3)tcd    | x = 3 + 4tcd
| y = 3 + (6 - 3)tcd    | y = 3 + 3tcd

Чтобы узнать пересекаются отрезки или нет вычислим их параметры, вычисление будет происходит аналогично случаю пересечения описанному выше.

3 + 4tcd = 5 + 5tab =>
4tcd = 2 + 5tab =>
tcd = (2 + 5tab)/4

3 + 3tcd = 4 + tab =>
3 + 3(2 + 5tab)/4 = 4 + tab =>
3 + (6 + 15tab)/4 = 4 + tab =>
2 + 11tab = 0 =>
tab = -2/11 ≈ -0.182
параметр tab меньше нуля, значит отрезки не пересекаются

tcd = (2 + 5tab)/4 =>
tcd = (2 + 5*-0.182)/4 ≈ 0.273
параметр tcd положительный и меньше единицы, 
значит мнимая точка лежит на отрезке CD

Найдем мнимую точку, расположенную на отрезке CD:

x = 5 + 5 * -0.182 = 4.09
y = 4 - 0.182 = 3.818

Метод SegmentSegment(…)

Метод вычисления точки пересечения отрезков инкапсулирован в классе Intersections. Метод статический, для вычисления точки пересечения не требуется создание экземпляра класса. Методы вычисляющие точки пересечения прямых и лучей описаны на страницах точка пересечения двух прямых на плоскости, пересечение луча и прямой, пересечение двух лучей.

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

class Intersections
{
    // Вычисление точки пересечения отрезков.
    public static bool SegmentSegment(Point r1, Point r2, Point p1, Point p2, out Point pCross, out Info info)
    {
        // Параметрическое уравнение отрезка
        // x = x0 + vt
        // y = y0 + wt
        // где v = x1 - x0
        //     w = y1 - y0
        // при 0 <= t <= 1
        

        // Оповещение о событиях пересечения или не пересечения.
        info = new Info();

        // Координаты направления вектора синего отрезка
        double v = r2.X - r1.X;
        double w = r2.Y - r1.Y;

        // Координаты направления вектора красного отрезка
        double v2 = p2.X - p1.X;
        double w2 = p2.Y - p1.Y;

        // ===== Частные случаи не пересечения =====

        // Отрезки должны быть определены
        if (v == 0 && w == 0 && v2 == 0 && w2 == 0)
        {
            info.Id = 10;
            info.Message = "Отрезки неопределённы";

            return false;
        }
        else if (v == 0 && w == 0)
        {
            info.Id = 11;
            info.Message = "Синий отрезка неопределён";

            return false;
        }
        else if (v2 == 0 && w2 == 0)
        {
            info.Id = 12;
            info.Message = "Красный отрезка неопределён";

            return false;
        }

        // Для вычисления параллельности отрезка 
        // необходимо сравнить направления их векторов.

        // Вычисляем длины векторов
        double lenBlue = Math.Sqrt(v * v + w * w);
        double lenRed = Math.Sqrt(v2 * v2 + w2 * w2);

        // Нормализация векторов - создание единичного вектора направления
        double x = v / lenBlue;
        double y = w / lenBlue;
        double x2 = v2 / lenRed;
        double y2 = w2 / lenRed;

        // Точность совпадения величин double
        double epsilon = 0.000001;

        // Проверка на совпадение
        if (r1.X == p1.X && r1.Y == p1.Y && r2.X == p2.X && r2.Y == p2.Y)
        {
            info.Id = 20;
            info.Message = "Отрезки совпадают";

            return false;
        }

        // Проверка на параллельность с определенной точностью.
        if (Math.Abs(x - x2) < epsilon && Math.Abs(y - y2) < epsilon)
        {
            info.Id = 21;
            info.Message = "Отрезки параллельны";
            return false;
        }

        // ===== /Частные случаи не пересечения =====


        // ===== Вычисление точки пересечения =====

        // Проверка факта пересечения
        // x = p1.X + v2t2
        // y = p1.Y + w2t2

        // r1.X + vt = p1.X + v2t2 => vt = p1.X - r1.X + v2t2 =>
        // t = (p1.X - r1.X + v2t2) / v - (у.1) соотношение t-параметров
        //
        // Вычисление одного параметра с заменой соотношением другого
        // r1.Y + wt = p1.Y + w2t2 => wt = p1.Y - r1.Y + w2t2 => t = (p1.Y - r1.Y + w2t2) / w
        // (p1.X - r1.X + v2t2) / v = (p1.Y - r1.Y + w2t2) / w =>
        // (p1.X - r1.X + v2t2) * w = (p1.Y - r1.Y + w2t2) * v =>
        // w * p1.X - w * r1.X + w * v2t2 = v * p1.Y - v * r1.Y + v * w2t2 =>
        // w * v2t2 - v * w2t2 = -w * p1.X + w * r1.X + v * p1.Y - v * r1.Y =>
        // (w * v2 - v * w2) * t2 = -w * p1.X + w * r1.X + v * p1.Y - v * r1.Y =>
        // t2 = (-w * p1.X + w * r1.X + v * p1.Y - v * r1.Y) / (w * v2 - v * w2) - (у.2)
        double t2 = (-w * p1.X + w * r1.X + v * p1.Y - v * r1.Y) / (w * v2 - v * w2);

        // t = (p1.X - r1.X + v2t2) / v - (у.1)
        double t = (p1.X - r1.X + v2 * t2) / v;

        // Если один из параметров меньше 0 и больше 1, значит пересечения нет.
        if (t < 0 || t > 1 || t2 < 0 || t2 > 1)
        {
            info.Id = 20;
            info.Message = "Пересечения нет";


            return false;
        }

        // Координаты точки пересечения
        pCross.X = p1.X + v2 * t2;
        pCross.Y = p1.Y + w2 * t2;


        info.Id = 0;
        info.Message = "Пересечение есть";

        return true;

        // ===== /Вычисление точки пересечения =====
    }
}

public class Info
{
    // Для визуального сообщения.
    public string Message;

    // Для автоматических действий.
    public int Id;
}

Исходник приложения с классом Intersections

К странице приложен исходник приложения на языке C#. Приложение демонстрирует вычисление точки пересечения двух отрезков. Графика приложения создает различные положения отрезков на плоскости окна. Управление начальными и конечными точками мышью и служебными клавишами.

Скачать исходник

• WpfAppCrossSegmentSegment-vs17.zip
• Размер: 205 Кбайт
• Загрузки: 185