Рубрики

Найти, если два прямоугольника перекрываются

Учитывая два прямоугольника, найдите, перекрываются ли эти два прямоугольника или нет.

Обратите внимание, что прямоугольник может быть представлен двумя координатами, вверху слева и внизу справа. Так что в основном нам дают следующие четыре координаты.
l1 : верхняя левая координата первого прямоугольника.
r1 : нижняя правая координата первого прямоугольника.
l2 : верхняя левая координата второго прямоугольника.
r2 : нижняя правая координата второго прямоугольника.

Нам нужно написать функцию bool doOverlap (l1, r1, l2, r2), которая возвращает true, если два заданных прямоугольника перекрываются.

Примечание. Можно предположить, что прямоугольники параллельны координатной оси.

Одно решение состоит в том, чтобы один за другим выбрать все точки одного прямоугольника и посмотреть, находится ли точка внутри другого прямоугольника или нет . Это можно сделать с помощью алгоритма, рассмотренного здесь .
Ниже приведен более простой подход. Два прямоугольника не перекрываются, если выполняется одно из следующих условий.
1) Один прямоугольник выше верхнего края другого прямоугольника.
2) Один прямоугольник находится слева от левого края другого прямоугольника.

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

C ++

#include<bits/stdc++.h>

  

struct Point

{

    int x, y;

};

  
// Возвращает true, если два прямоугольника (l1, r1) и (l2, r2) перекрываются

bool doOverlap(Point l1, Point r1, Point l2, Point r2)

{

    // Если один прямоугольник находится слева от другого

    if (l1.x > r2.x || l2.x > r1.x)

        return false;

  

    // Если один прямоугольник выше другого

    if (l1.y < r2.y || l2.y < r1.y)

        return false;

  

    return true;

}

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

int main()

{

    Point l1 = {0, 10}, r1 = {10, 0};

    Point l2 = {5, 5}, r2 = {15, 0};

    if (doOverlap(l1, r1, l2, r2))

        printf("Rectangles Overlap");

    else

        printf("Rectangles Don't Overlap");

    return 0;

}

Джава

// Java-программа для проверки перекрытия прямоугольников

class GFG {

  

   static class Point {

  

        int x, y;

    }

  
// Возвращает true, если два прямоугольника (l1, r1) и (l2, r2) перекрываются

 static  boolean doOverlap(Point l1, Point r1, Point l2, Point r2) {

        // Если один прямоугольник находится слева от другого

        if (l1.x > r2.x || l2.x > r1.x) {

            return false;

        }

  

        // Если один прямоугольник выше другого

        if (l1.y < r2.y || l2.y < r1.y) {

            return false;

        }

  

        return true;

    }

  

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

    public static void main(String[] args) {

        Point l1 = new Point(),r1 = new Point(),

                l2 = new Point(),r2 = new Point();

        l1.x=0;l1.y=10; r1.x=10;r1.y=0;

         l2.x=5;l2.y=5; r2.x=15;r2.y=0;

  

        if (doOverlap(l1, r1, l2, r2)) {

            System.out.println("Rectangles Overlap");

        } else {

            System.out.println("Rectangles Don't Overlap");

        }

    }

}
// этот код предоставлен PrinciRaj1992

python3

# Программа Python для проверки перекрытия прямоугольников

class Point:

    def __init__(self, x, y):

        self.x = x

        self.y = y

  
# Возвращает true, если два прямоугольника (l1, r1)
# и (l2, r2) перекрываются

def doOverlap(l1, r1, l2, r2):

      

    # Если один прямоугольник находится слева от другого

    if(l1.x > r2.x or l2.x > r1.x):

        return False

  

    # Если один прямоугольник выше другого

    if(l1.y < r2.y or l2.y < r1.y):

        return False

  

    return True

  
Код водителя

if __name__ == "__main__":

    l1 = Point(0, 10)

    r1 = Point(10, 0)

    l2 = Point(5, 5)

    r2 = Point(15, 0)

  

    if(doOverlap(l1, r1, l2, r2)):

        print("Rectangles Overlap")

    else:

        print("Rectangles Don't Overlap")

  
# Этот код предоставлен Вивеком Кумаром Сингхом

C #

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

using System;

      

class GFG 

{

    class Point 

    {

        public int x, y;

    }

  

    // Возвращает true, если два прямоугольника (l1, r1)

    // и (l2, r2) перекрываются

    static bool doOverlap(Point l1, Point r1,

                          Point l2, Point r2) 

    {

        // Если один прямоугольник находится слева от другого

        if (l1.x > r2.x || l2.x > r1.x)

        {

            return false;

        }

  

        // Если один прямоугольник выше другого

        if (l1.y < r2.y || l2.y < r1.y) 

        {

            return false;

        }

        return true;

    }

  

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

    public static void Main() 

    {

        Point l1 = new Point(), r1 = new Point(),

                l2 = new Point(), r2 = new Point();

        l1.x = 0;l1.y = 10; r1.x = 10;r1.y = 0;

        l2. = 5;l2.y = 5; r2.x = 15;r2.y = 0;

        if (doOverlap(l1, r1, l2, r2))

        {

            Console.WriteLine("Rectangles Overlap");

        } else

        {

            Console.WriteLine("Rectangles Don't Overlap");

        }

    }

}

  
// Этот код предоставлен
// Раджпут-Джи


Выход:

Rectangles Overlap

Сложность по времени вышеприведенного кода равна O (1), так как в коде нет цикла или рекурсии.

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

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

Найти, если два прямоугольника перекрываются

0.00 (0%) 0 votes