Рубрики

Как проверить, пересекаются ли два заданных отрезка?

По заданным двум отрезкам (p1, q1) и (p2, q2) найдите, пересекаются ли заданные отрезки.

Прежде чем мы обсудим решение, давайте определим понятие ориентации . Ориентация упорядоченного триплета точек на плоскости может быть
-против часовой стрелки
-clockwise
-colinear
Следующая диаграмма показывает различные возможные ориентации ( a , b , c )

Чем полезна ориентация?
Два отрезка (p1, q1) и (p2, q2) пересекаются тогда и только тогда, когда выполняется одно из следующих двух условий

1. Общий случай:
— ( p1 , q1 , p2 ) и ( p1 , q1 , q2 ) имеют разные ориентации и
— ( p2 , q2 , p1 ) и ( p2 , q2 , q1 ) имеют разные ориентации.

Примеры:

2. Особый случай
— ( p1 , q1 , p2 ), ( p1 , q1 , q2 ), ( p2 , q2 , p1 ) и ( p2 , q2 , q1 ) все коллинеарны и
— x-проекции ( p1 , q1 ) и ( p2 , q2 ) пересекаются
— y-проекции ( p1 , q1 ) и ( p2 , q2 ) пересекаются

Примеры:

Ниже приведена реализация, основанная на представленной выше идее.

C ++

// Программа на C ++ для проверки, пересекаются ли два заданных отрезка
#include <iostream>

using namespace std;

  

struct Point

{

    int x;

    int y;

};

  
// Учитывая три коллинеарных точки p, q, r, функция проверяет,
// точка q лежит на отрезке прямой 'pr'

bool onSegment(Point p, Point q, Point r)

{

    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&

        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))

       return true;

  

    return false;

}

  
// Найти ориентацию упорядоченного триплета (p, q, r).
// Функция возвращает следующие значения
// 0 -> p, q и r являются коллинеарными
// 1 -> по часовой стрелке
// 2 -> против часовой стрелки

int orientation(Point p, Point q, Point r)

{

    // см. Https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/

    // для деталей нижеприведенной формулы.

    int val = (q.y - p.y) * (r.x - q.x) -

              (q.x - p.x) * (r.y - q.y);

  

    if (val == 0) return 0;  // коллинеар

  

    return (val > 0)? 1: 2; // часы или против часовой стрелки

}

  
// Основная функция, которая возвращает true, если отрезок линии 'p1q1'
// и 'p2q2' пересекаются.

bool doIntersect(Point p1, Point q1, Point p2, Point q2)

{

    // Находим четыре ориентации, необходимые для общего и

    // Особые случаи

    int o1 = orientation(p1, q1, p2);

    int o2 = orientation(p1, q1, q2);

    int o3 = orientation(p2, q2, p1);

    int o4 = orientation(p2, q2, q1);

  

    // Общий случай

    if (o1 != o2 && o3 != o4)

        return true;

  

    // Особые случаи

    // p1, q1 и p2 коллинеарны, а p2 лежит на отрезке p1q1

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

  

    // p1, q1 и q2 коллинеарны, а q2 лежит на отрезке p1q1

    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

  

    // p2, q2 и p1 коллинеарны, а p1 лежит на отрезке p2q2

    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

  

     // p2, q2 и q1 коллинеарны, а q1 лежит на отрезке p2q2

    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

  

    return false; // Не попадает ни в один из вышеперечисленных случаев

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Point p1 = {1, 1}, q1 = {10, 1};

    struct Point p2 = {1, 2}, q2 = {10, 2};

  

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

  

    p1 = {10, 0}, q1 = {0, 10};

    p2 = {0, 0}, q2 = {10, 10};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

  

    p1 = {-5, -5}, q1 = {0, 0};

    p2 = {1, 1}, q2 = {10, 10};

    doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";

  

    return 0;

}

Джава

// Java-программа для проверки, пересекаются ли два заданных отрезка

class GFG 

{

  

static class Point

{

    int x;

    int y;

  

        public Point(int x, int y) 

        {

            this.x = x;

            this.y = y;

        }

      
};

  
// Учитывая три коллинеарных точки p, q, r, функция проверяет,
// точка q лежит на отрезке прямой 'pr'

static boolean onSegment(Point p, Point q, Point r)

{

    if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) &&

        q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y))

    return true;

  

    return false;

}

  
// Найти ориентацию упорядоченного триплета (p, q, r).
// Функция возвращает следующие значения
// 0 -> p, q и r являются коллинеарными
// 1 -> по часовой стрелке
// 2 -> против часовой стрелки

static int orientation(Point p, Point q, Point r)

{

    // см. Https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/

    // для деталей нижеприведенной формулы.

    int val = (q.y - p.y) * (r.x - q.x) -

            (q.x - p.x) * (r.y - q.y);

  

    if (val == 0) return 0; // коллинеар

  

    return (val > 0)? 1: 2; // часы или против часовой стрелки

}

  
// Основная функция, которая возвращает true, если отрезок линии 'p1q1'
// и 'p2q2' пересекаются.

static boolean doIntersect(Point p1, Point q1, Point p2, Point q2)

{

    // Находим четыре ориентации, необходимые для общего и

    // Особые случаи

    int o1 = orientation(p1, q1, p2);

    int o2 = orientation(p1, q1, q2);

    int o3 = orientation(p2, q2, p1);

    int o4 = orientation(p2, q2, q1);

  

    // Общий случай

    if (o1 != o2 && o3 != o4)

        return true;

  

    // Особые случаи

    // p1, q1 и p2 коллинеарны, а p2 лежит на отрезке p1q1

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

  

    // p1, q1 и q2 коллинеарны, а q2 лежит на отрезке p1q1

    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

  

    // p2, q2 и p1 коллинеарны, а p1 лежит на отрезке p2q2

    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

  

    // p2, q2 и q1 коллинеарны, а q1 лежит на отрезке p2q2

    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

  

    return false; // Не попадает ни в один из вышеперечисленных случаев

}

  
// Код драйвера

public static void main(String[] args) 

{

    Point p1 = new Point(1, 1);

    Point q1 = new Point(10, 1);

    Point p2 = new Point(1, 2);

    Point q2 = new Point(10, 2);

  

    if(doIntersect(p1, q1, p2, q2))

        System.out.println("Yes");

    else

        System.out.println("No");

  

    p1 = new Point(10, 1); q1 = new Point(0, 10);

    p2 = new Point(0, 0); q2 = new Point(10, 10);

    if(doIntersect(p1, q1, p2, q2))

            System.out.println("Yes");

    else

        System.out.println("No");

  

    p1 = new Point(-5, -5); q1 = new Point(0, 0);

    p2 = new Point(1, 1); q2 = new Point(10, 10);;

    if(doIntersect(p1, q1, p2, q2))

        System.out.println("Yes");

    else

        System.out.println("No");

}
}

  
// Этот код предоставлен Принчи Сингхом

C #

// C # программа для проверки пересечения двух заданных отрезков

using System;

using System.Collections.Generic; 

  

class GFG 

{

  

public class Point

{

    public int x;

    public int y;

  

    public Point(int x, int y) 

    {

        this.x = x;

        this.y = y;

    }

      
};

  
// Учитывая три коллинеарных точки p, q, r, функция проверяет,
// точка q лежит на отрезке прямой 'pr'

static Boolean onSegment(Point p, Point q, Point r)

{

    if (q.x <= Math.Max(p.x, r.x) && q.x >= Math.Min(p.x, r.x) &&

        q.y <= Math.Max(p.y, r.y) && q.y >= Math.Min(p.y, r.y))

    return true;

  

    return false;

}

  
// Найти ориентацию упорядоченного триплета (p, q, r).
// Функция возвращает следующие значения
// 0 -> p, q и r являются коллинеарными
// 1 -> по часовой стрелке
// 2 -> против часовой стрелки

static int orientation(Point p, Point q, Point r)

{

    // см. Https://www.geeksforgeeks.org/orientation-3-ordered-points/amp/

    // для деталей нижеприведенной формулы.

    int val = (q.y - p.y) * (r.x - q.x) -

            (q.x - p.x) * (r.y - q.y);

  

    if (val == 0) return 0; // коллинеар

  

    return (val > 0)? 1: 2; // часы или против часовой стрелки

}

  
// Основная функция, которая возвращает true, если отрезок линии 'p1q1'
// и 'p2q2' пересекаются.

static Boolean doIntersect(Point p1, Point q1, Point p2, Point q2)

{

    // Находим четыре ориентации, необходимые для общего и

    // Особые случаи

    int o1 = orientation(p1, q1, p2);

    int o2 = orientation(p1, q1, q2);

    int o3 = orientation(p2, q2, p1);

    int o4 = orientation(p2, q2, q1);

  

    // Общий случай

    if (o1 != o2 && o3 != o4)

        return true;

  

    // Особые случаи

    // p1, q1 и p2 коллинеарны, а p2 лежит на отрезке p1q1

    if (o1 == 0 && onSegment(p1, p2, q1)) return true;

  

    // p1, q1 и q2 коллинеарны, а q2 лежит на отрезке p1q1

    if (o2 == 0 && onSegment(p1, q2, q1)) return true;

  

    // p2, q2 и p1 коллинеарны, а p1 лежит на отрезке p2q2

    if (o3 == 0 && onSegment(p2, p1, q2)) return true;

  

    // p2, q2 и q1 коллинеарны, а q1 лежит на отрезке p2q2

    if (o4 == 0 && onSegment(p2, q1, q2)) return true;

  

    return false; // Не попадает ни в один из вышеперечисленных случаев

}

  
// Код драйвера

public static void Main(String[] args) 

{

    Point p1 = new Point(1, 1);

    Point q1 = new Point(10, 1);

    Point p2 = new Point(1, 2);

    Point q2 = new Point(10, 2);

  

    if(doIntersect(p1, q1, p2, q2))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No");

  

    p1 = new Point(10, 1); q1 = new Point(0, 10);

    p2 = new Point(0, 0); q2 = new Point(10, 10);

    if(doIntersect(p1, q1, p2, q2))

            Console.WriteLine("Yes");

    else

        Console.WriteLine("No");

  

    p1 = new Point(-5, -5); q1 = new Point(0, 0);

    p2 = new Point(1, 1); q2 = new Point(10, 10);;

    if(doIntersect(p1, q1, p2, q2))

        Console.WriteLine("Yes");

    else

        Console.WriteLine("No");

}
}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

No
Yes
No

Источники:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

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

Рекомендуемые посты:

Как проверить, пересекаются ли два заданных отрезка?

0.00 (0%) 0 votes