Prerrequisitos: Ecuación del círculo cuando se dan tres puntos en el círculo , Casco convexo
Dada una array arr[][] que contiene N puntos en un plano 2-D con coordenadas enteras. La tarea es encontrar el centro y el radio del círculo envolvente mínimo (MEC). Un círculo envolvente mínimo es un círculo en el que todos los puntos se encuentran dentro del círculo o en sus límites.
Ejemplos:
Entrada: arr[][] = {{0, 0}, {0, 1}, {1, 0}} Salida
: Centro = {0.5, 0.5}, Radio = 0.7071
Explicación:
Al trazar el círculo anterior con radio 0.707 y centro (0.5, 0.5), se puede observar claramente que todos los puntos mencionados se encuentran dentro o sobre el círculo.
Entrada: arr[][] = {{5, -2}, {-3, -2}, {-2, 5}, {1, 6}, {0, 2}} Salida: Centro = {
1.0 , 1.0}, Radio = 5.000
Enfoque ingenuo: este problema se puede resolver haciendo algunas observaciones.
- La primera observación que se puede hacer es que el MEC corta al menos un punto. Esto se debe a que si el MEC no se interseca en ningún punto, el círculo podría reducirse aún más hasta que se interseque en uno de los puntos.
- La segunda observación que se puede hacer es que, dado un círculo que encierra todos los puntos y se interseca en un solo punto, el círculo se puede reducir aún más moviendo el centro hacia ese punto mientras se mantiene el punto en el límite del círculo hasta que el círculo se interseca con uno. o más puntos adicionales.
- Si el círculo se interseca en dos puntos (A y B) y la distancia AB es igual al diámetro del círculo, entonces el círculo no se puede encoger más. De lo contrario, el centro del círculo se puede mover hacia el punto medio de AB hasta que el círculo se cruza con un tercer punto (en el que el círculo ya no se puede contraer).
De las observaciones anteriores, se puede concluir que el MEC:
- Intersecta 2 puntos A y B, donde AB = diámetro del círculo. Para este caso, el centro del círculo sería el punto medio de A y B y el radio sería la mitad de la distancia AB .
- Intersecta 3 o más puntos. El enfoque para encontrar el centro y el radio se ha discutido en este artículo .
Por lo tanto, la solución a este problema es trivial para N <= 3. Para otros casos, se puede formar una idea simple para resolver este problema. La idea es usar todos los pares y triples de puntos para obtener el círculo definido por esos puntos. Después de obtener el círculo, prueba para ver si los otros puntos están encerrados por ese círculo y devuelve el círculo válido más pequeño encontrado.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the minimum enclosing
// circle for N integer points in a 2-D plane
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
// Defining infinity
const double INF = 1e18;
// Structure to represent a 2D point
struct Point {
double X, Y;
};
// Structure to represent a 2D circle
struct Circle {
Point C;
double R;
};
// Function to return the euclidean distance
// between two points
double dist(const Point& a, const Point& b)
{
return sqrt(pow(a.X - b.X, 2) + pow(a.Y - b.Y, 2));
}
// Function to check whether a point lies inside
// or on the boundaries of the circle
bool is_inside(const Circle& c, const Point& p)
{
return dist(c.C, p) <= c.R;
}
// The following two functions are the functions used
// To find the equation of the circle when three
// points are given.
// Helper method to get a circle defined by 3 points
Point get_circle_center(double bx, double by,
double cx, double cy)
{
double B = bx * bx + by * by;
double C = cx * cx + cy * cy;
double D = bx * cy - by * cx;
return { (cy * B - by * C) / (2 * D),
(bx * C - cx * B) / (2 * D) };
}
// Function to return a unique circle that intersects
// three points
Circle circle_from(const Point& A, const Point& B,
const Point& C)
{
Point I = get_circle_center(B.X - A.X, B.Y - A.Y,
C.X - A.X, C.Y - A.Y);
I.X += A.X;
I.Y += A.Y;
return { I, dist(I, A) };
}
// Function to return the smallest circle
// that intersects 2 points
Circle circle_from(const Point& A, const Point& B)
{
// Set the center to be the midpoint of A and B
Point C = { (A.X + B.X) / 2.0, (A.Y + B.Y) / 2.0 };
// Set the radius to be half the distance AB
return { C, dist(A, B) / 2.0 };
}
// Function to check whether a circle encloses the given points
bool is_valid_circle(const Circle& c, const vector<Point>& P)
{
// Iterating through all the points to check
// whether the points lie inside the circle or not
for (const Point& p : P)
if (!is_inside(c, p))
return false;
return true;
}
// Function to return find the minimum enclosing
// circle from the given set of points
Circle minimum_enclosing_circle(const vector<Point>& P)
{
// To find the number of points
int n = (int)P.size();
if (n == 0)
return { { 0, 0 }, 0 };
if (n == 1)
return { P[0], 0 };
// Set initial MEC to have infinity radius
Circle mec = { { 0, 0 }, INF };
// Go over all pair of points
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Get the smallest circle that
// intersects P[i] and P[j]
Circle tmp = circle_from(P[i], P[j]);
// Update MEC if tmp encloses all points
// and has a smaller radius
if (tmp.R < mec.R && is_valid_circle(tmp, P))
mec = tmp;
}
}
// Go over all triples of points
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// Get the circle that intersects P[i], P[j], P[k]
Circle tmp = circle_from(P[i], P[j], P[k]);
// Update MEC if tmp encloses all points
// and has smaller radius
if (tmp.R < mec.R && is_valid_circle(tmp, P))
mec = tmp;
}
}
}
return mec;
}
// Driver code
int main()
{
Circle mec = minimum_enclosing_circle({ { 0, 0 },
{ 0, 1 },
{ 1, 0 } });
cout << "Center = { " << mec.C.X << ", " << mec.C.Y
<< " } Radius = " << mec.R << endl;
Circle mec2 = minimum_enclosing_circle({ { 5, -2 },
{ -3, -2 },
{ -2, 5 },
{ 1, 6 },
{ 0, 2 } });
cout << "Center = { " << mec2.C.X << ", " << mec2.C.Y
<< " } Radius = " << mec2.R << endl;
return 0;
}
Python3
# Python3 program to find the minimum enclosing
# circle for N integer points in a 2-D plane
from math import sqrt
# Defining infinity
INF = 10**18
# Function to return the euclidean distance
# between two points
def dist(a, b):
return sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2))
# Function to check whether a point lies inside
# or on the boundaries of the circle
def is_inside(c, p):
return dist(c[0], p) <= c[1]
# The following two functions are the functions used
# To find the equation of the circle when three
# points are given.
# Helper method to get a circle defined by 3 points
def get_circle_center(bx, by, cx, cy):
B = bx * bx + by * by
C = cx * cx + cy * cy
D = bx * cy - by * cx
return [(cy * B - by * C) // (2 * D),
(bx * C - cx * B) // (2 * D) ]
# Function to return a unique circle that intersects
# three points
def circle_frOm(A, B,C):
I = get_circle_center(B[0] - A[0], B[1] - A[1],
C[0] - A[0], C[1] - A[1])
I[0] += A[0]
I[1] += A[1]
return [I, dist(I, A)]
# Function to return the smallest circle
# that intersects 2 points
def circle_from(A, B):
# Set the center to be the midpoint of A and B
C = [ (A[0] + B[0]) / 2.0, (A[1] + B[1]) / 2.0]
# Set the radius to be half the distance AB
return [C, dist(A, B) / 2.0]
# Function to check whether a circle encloses the given points
def is_valid_circle(c, P):
# Iterating through all the points to check
# whether the points lie inside the circle or not
for p in P:
if (is_inside(c, p) == False):
return False
return True
# Function to return find the minimum enclosing
# circle from the given set of points
def minimum_enclosing_circle(P):
# To find the number of points
n = len(P)
if (n == 0):
return [[0, 0], 0]
if (n == 1):
return [P[0], 0]
# Set initial MEC to have infinity radius
mec = [[0, 0], INF]
# Go over all pair of points
for i in range(n):
for j in range(i + 1, n):
# Get the smallest circle that
# intersects P[i] and P[j]
tmp = circle_from(P[i], P[j])
# Update MEC if tmp encloses all points
# and has a smaller radius
if (tmp[1] < mec[1] and is_valid_circle(tmp, P)):
mec = tmp
# Go over all triples of points
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
# Get the circle that intersects P[i], P[j], P[k]
tmp = circle_frOm(P[i], P[j], P[k])
# Update MEC if tmp encloses all points
# and has smaller radius
if (tmp[1] < mec[1] and is_valid_circle(tmp, P)):
mec = tmp
return mec
# Driver code
mec = minimum_enclosing_circle([ [ 0, 0 ],
[ 0, 1 ],
[ 1, 0 ] ])
print("Center = { ",mec[0][1],",",mec[0][1],
"} Radius = ",round(mec[1],6))
mec2 = minimum_enclosing_circle([ [ 5, -2 ],
[ -3, -2 ],
[ -2, 5 ],
[ 1, 6 ],
[ 0, 2 ] ])
print("Center = {",mec2[0][0],",",mec2[0][1],
"} Radius = ",mec2[1])
# This code is contributed by mohit kumar 29
Center = { 0.5, 0.5 } Radius = 0.707107
Center = { 1, 1 } Radius = 5
Complejidad de tiempo: La complejidad de tiempo para esta solución sería de O(N 4 ) . Eso es porque hay N 3 triples de puntos. Y para cada triple, verificamos si todos los puntos están encerrados por el círculo.
Enfoque 2: También se puede utilizar una solución con la aplicación del concepto de casco convexo para este problema. La idea es formar primero un casco convexo en el conjunto de puntos dado. Una vez que se realiza el casco convexo y se devuelve el nuevo conjunto de puntos, la solución mencionada anteriormente se puede usar en el nuevo conjunto de puntos para encontrar el MEC.
El código para este enfoque sería el mismo que el anterior, excepto que también necesitaríamos obtener primero el casco convexo. Por favor, consulte este artículopara un algoritmo eficiente para obtener el casco convexo.
Complejidad de tiempo: una observación que debe hacerse es que si la entrada ya representa algunos vértices de un polígono convexo, entonces esta solución tendría la misma complejidad de tiempo que el enfoque ingenuo anterior.
Por lo tanto, la complejidad del caso más desfavorable de este enfoque sigue siendo O(N 4 ) .
Sin embargo, si el número de vértices del casco convexo es considerablemente menor que N, entonces la complejidad sería O(H 4 + NLog(N)) donde H representa el número de vértices del casco convexo, y NLog(N) El factor es para encontrar el casco convexo asumiendo que se usa el algoritmo Graham Scan .
Finalmente, si el número de vértices, H , del casco convexo es muy pequeño, entonces puede considerarse como un factor constante y, por lo tanto, la complejidad temporal sería O(NLog(N)) .
Publicación traducida automáticamente
Artículo escrito por marwan tammam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA