Compruebe si algún punto se superpone al círculo y al rectángulo dados

Posted on by Rudeus Greyrat

Dados dos puntos diagonales opuestos de un rectángulo (X1, Y1), (X2, Y2) y el centro, radio del círculo R, (Xc, Yc) , la tarea es verificar si existe algún punto P que pertenezca a ambos el círculo como el rectángulo. 
Ejemplos: 
 

Entrada: R = 2, Xc = 0, Yc = 0, X1 = 1, Y1 = 0, X2 = 3, Y2 = 3 
Salida: verdadero 
Explicación: 
Claramente, de la siguiente ilustración, el círculo y el rectángulo se intersecan. 
 

Entrada: R = 1, Xc = 1, Yc = 1, X1 = 3, Y1 = 3, X2 = 5, Y2 = 6 
Salida: falso 
 

Enfoque: La idea es simplemente verificar si el círculo y el rectángulo se cruzan o no. Hay esencialmente 2 casos posibles cuando ocurre la intersección. 
 

  1. Caso 1: El lado del rectángulo toca o se cruza con el círculo. Para verificar si las formas se intersecan, necesitamos encontrar un punto en o dentro del rectángulo que esté más cerca del centro del círculo. Si este punto se encuentra sobre o dentro del círculo, se garantiza que ambas formas se cruzan. Denote el punto más cercano por (Xn, Yn) . Luego, la distancia entre el punto más cercano y el centro del círculo se puede encontrar usando sqrt((Xc- Xn) 2 + (Yc- Yn) 2 ) . Si esta distancia ≤ el radio del círculo, las dos formas se intersecan.
  2. Caso 2: El centro del círculo se encuentra dentro del rectángulo. Como el centro del círculo se encuentra dentro del rectángulo, el punto más cercano será (Xc, Yc).

En una observación cercana, se puede observar que el punto de interés solo depende de las ubicaciones de (X1, Y1) y (X2, Y2) en relación con (Xc, Yc). Por lo tanto, el punto más cercano en los dos casos anteriores se puede calcular como:
 

  1. Xn= máx(X1, mín(Xc, X2))
  2. Yn= máx(Y1, mín(Yc, Y2))

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation to check if any
// point overlaps the given circle
// and rectangle
#include<bits/stdc++.h>
using namespace std;
 
// Function to check if any point
// overlaps the given circle
// and rectangle
bool checkOverlap(int R, int Xc, int Yc,
                         int X1, int Y1,
                         int X2, int Y2)
{
 
    // Find the nearest point on the
    // rectangle to the center of
    // the circle
    int Xn = max(X1, min(Xc, X2));
    int Yn = max(Y1, min(Yc, Y2));
     
    // Find the distance between the
    // nearest point and the center
    // of the circle
    // Distance between 2 points,
    // (x1, y1) & (x2, y2) in
    // 2D Euclidean space is
    // ((x1-x2)**2 + (y1-y2)**2)**0.5
    int Dx = Xn - Xc;
    int Dy = Yn - Yc;
    return (Dx * Dx + Dy * Dy) <= R * R;
}
 
// Driver code
int main()
{
    int R = 1;
    int Xc = 0, Yc = 0;
    int X1 = 1, Y1 = -1;
    int X2 = 3, Y2 = 1;
     
    if(checkOverlap(R, Xc, Yc,
                       X1, Y1,
                       X2, Y2))
    {
        cout << "True" << endl;
    }
    else
    {
        cout << "False";
    }
}
 
// This code is contributed by BhupendraSingh

Java

// Java implementation to check if any
// point overlaps the given circle
// and rectangle
class GFG{
 
// Function to check if any point
// overlaps the given circle
// and rectangle
static boolean checkOverlap(int R, int Xc, int Yc,
                                   int X1, int Y1,
                                   int X2, int Y2)
{
 
    // Find the nearest point on the
    // rectangle to the center of
    // the circle
    int Xn = Math.max(X1, Math.min(Xc, X2));
    int Yn = Math.max(Y1, Math.min(Yc, Y2));
     
    // Find the distance between the
    // nearest point and the center
    // of the circle
    // Distance between 2 points,
    // (x1, y1) & (x2, y2) in
    // 2D Euclidean space is
    // ((x1-x2)**2 + (y1-y2)**2)**0.5
    int Dx = Xn - Xc;
    int Dy = Yn - Yc;
    return (Dx * Dx + Dy * Dy) <= R * R;
}
 
// Driver code
public static void main(String[] args)
{
    int R = 1;
    int Xc = 0, Yc = 0;
    int X1 = 1, Y1 = -1;
    int X2 = 3, Y2 = 1;
     
    if(checkOverlap(R, Xc, Yc,
                       X1, Y1,
                       X2, Y2))
    {
        System.out.print("True" + "\n");
    }
    else
    {
        System.out.print("False");
    }
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation to check if any
# point overlaps the given Circle
# and Rectangle
 
# Function to check if any point
# overlaps the given Circle
# and Rectangle
def checkOverlap(R, Xc, Yc, X1, Y1, X2, Y2):
 
    # Find the nearest point on the
    # rectangle to the center of
    # the circle
    Xn = max(X1, min(Xc, X2))
    Yn = max(Y1, min(Yc, Y2))
     
    # Find the distance between the
    # nearest point and the center
    # of the circle
    # Distance between 2 points,
    # (x1, y1) & (x2, y2) in
    # 2D Euclidean space is
    # ((x1-x2)**2 + (y1-y2)**2)**0.5
    Dx = Xn - Xc
    Dy = Yn - Yc
    return (Dx**2 + Dy**2) <= R**2
 
# Driver code
if(__name__ == "__main__"):
    R = 1
    Xc, Yc = 0, 0
    X1, Y1 = 1, -1
    X2, Y2 = 3, 1
     
    print(checkOverlap(R, Xc, Yc, X1, Y1, X2, Y2))

C#

// C# implementation to check if any
// point overlaps the given circle
// and rectangle
using System;
class GFG{
 
// Function to check if any point
// overlaps the given circle
// and rectangle
static bool checkOverlap(int R, int Xc, int Yc,
                                int X1, int Y1,
                                int X2, int Y2)
{
 
    // Find the nearest point on the
    // rectangle to the center of
    // the circle
    int Xn = Math.Max(X1,
             Math.Min(Xc, X2));
    int Yn = Math.Max(Y1,
             Math.Min(Yc, Y2));
     
    // Find the distance between the
    // nearest point and the center
    // of the circle
    // Distance between 2 points,
    // (x1, y1) & (x2, y2) in
    // 2D Euclidean space is
    // ((x1-x2)**2 + (y1-y2)**2)**0.5
    int Dx = Xn - Xc;
    int Dy = Yn - Yc;
    return (Dx * Dx + Dy * Dy) <= R * R;
}
 
// Driver code
public static void Main()
{
    int R = 1;
    int Xc = 0, Yc = 0;
    int X1 = 1, Y1 = -1;
    int X2 = 3, Y2 = 1;
     
    if(checkOverlap(R, Xc, Yc,
                       X1, Y1,
                       X2, Y2))
    {
        Console.Write("True" + "\n");
    }
    else
    {
        Console.Write("False");
    }
}
}
 
// This code is contributed by Nidhi_biet

Javascript

<script>
 
// Javascript implementation to check if any
// point overlaps the given circle
// and rectangle
 
// Function to check if any point
// overlaps the given circle
// and rectangle
function checkOverlap(R, Xc, Yc, X1, Y1, X2, Y2)
{
   
    // Find the nearest point on the
    // rectangle to the center of
    // the circle
    let Xn = Math.max(X1, Math.min(Xc, X2));
    let Yn = Math.max(Y1, Math.min(Yc, Y2));
       
    // Find the distance between the
    // nearest point and the center
    // of the circle
    // Distance between 2 points,
    // (x1, y1) & (x2, y2) in
    // 2D Euclidean space is
    // ((x1-x2)**2 + (y1-y2)**2)**0.5
    let Dx = Xn - Xc;
    let Dy = Yn - Yc;
    return (Dx * Dx + Dy * Dy) <= R * R;
}
   
 
// Driver Code
     
    let R = 1;
    let Xc = 0, Yc = 0;
    let X1 = 1, Y1 = -1;
    let X2 = 3, Y2 = 1;
       
    if(checkOverlap(R, Xc, Yc,
                       X1, Y1,
                       X2, Y2))
    {
        document.write("True" + "\n");
    }
    else
    {
        document.write("False");
    }
       
</script>
Producción: 

True

 

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por coder001 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *