algorithm - triangulo - determina las coordenadas del centro y del radio de las circunferencias
Ecuación para probar si un punto está dentro de un círculo (14)
Si tiene un círculo con centro (center_x, center_y) y radio de radius , ¿cómo comprueba si un punto dado con coordenadas (x, y) está dentro del círculo?
Calcula la distancia
D = Math.Sqrt(Math.Pow(center_x - x, 2) + Math.Pow(center_y - y, 2))
return D <= radius
eso está en C # ... convertir para usar en python ...
Como se dijo anteriormente - usa la distancia euclidiana.
from math import hypot
def in_radius(c_x, c_y, r, x, y):
return math.hypot(c_x-x, c_y-y) <= r
Como se indicó anteriormente, para mostrar si el punto está en el círculo podemos usar lo siguiente
if ((x-center_x)^2 + (y - center_y)^2 < radius^2) {
in.circle <- "True"
} else {
in.circle <- "False"
}
Para representarlo gráficamente podemos utilizar:
plot(x, y, asp = 1, xlim = c(-1, 1), ylim = c(-1, 1), col = ifelse((x-center_x)^2 + (y - center_y)^2 < radius^2,''green'',''red''))
draw.circle(0, 0, 1, nv = 1000, border = NULL, col = NA, lty = 1, lwd = 1)
Debe comprobar si la distancia desde el centro del círculo hasta el punto es menor que el radio, es decir,
if (x-center_x)**2 + (y-center_y)**2 <= radius**2:
# inside circle
En general, x e y deben satisfacer (x - center_x)^2 + (y - center_y)^2 < radius^2 .
Tenga en cuenta que los puntos que satisfacen la ecuación anterior con < reemplazado por == se consideran los puntos en el círculo, y los puntos que satisfacen la ecuación anterior con < reemplazado por > se consideran fuera del círculo.
Encuentra la distancia entre el centro del círculo y los puntos dados. Si la distancia entre ellos es menor que el radio, entonces el punto está dentro del círculo. si la distancia entre ellos es igual al radio del círculo, entonces el punto está en la circunferencia del círculo. Si la distancia es mayor que el radio, entonces el punto está fuera del círculo.
int d = r^2 - (center_x-x)^2 + (center_y-y)^2;
if(d>0)
print("inside");
else if(d==0)
print("on the circumference");
else
print("outside");
Matemáticamente, Pitágoras es probablemente un método simple como muchos ya han mencionado.
(x-center_x)^2 + (y - center_y)^2 < radius^2
Computacionalmente, hay formas más rápidas. Definir:
dx = abs(x-center_x)
dy = abs(y-center_y)
R = radius
Si es más probable que un punto esté fuera de este círculo , imagina un cuadrado dibujado alrededor de él, de modo que sus lados sean tangentes a este círculo:
if dx>R then
return false.
if dy>R then
return false.
Ahora imagina un diamante cuadrado dibujado dentro de este círculo de modo que sus vértices toquen este círculo:
if dx + dy <= R then
return true.
Ahora hemos cubierto la mayor parte de nuestro espacio y solo queda una pequeña área de este círculo entre nuestro cuadrado y el diamante que se va a probar. Aquí volvemos a Pitágoras como arriba.
if dx^2 + dy^2 <= R^2 then
return true
else
return false.
Si es más probable que un punto esté dentro de este círculo , invierta el orden de los primeros 3 pasos:
if dx + dy <= R then
return true.
if dx > R then
return false.
if dy > R
then return false.
if dx^2 + dy^2 <= R^2 then
return true
else
return false.
Los métodos alternativos imaginan un cuadrado dentro de este círculo en lugar de un diamante, pero esto requiere un poco más de pruebas y cálculos sin ninguna ventaja computacional (el cuadrado interior y los diamantes tienen áreas idénticas):
k = R/sqrt(2)
if dx <= k and dy <= k then
return true.
Actualizar:
Para aquellos interesados en el rendimiento, implementé este método en c y compilé con -O3.
time ./a.out tiempos de ejecución por time ./a.out
Implementé este método, un método normal y un método ficticio para determinar la sobrecarga de tiempo.
Normal: 21.3s This: 19.1s Overhead: 16.5s
Entonces, parece que este método es más eficiente en esta implementación.
// compile gcc -O3 <filename>.c
// run: time ./a.out
#include <stdio.h>
#include <stdlib.h>
#define TRUE (0==0)
#define FALSE (0==1)
#define ABS(x) (((x)<0)?(0-(x)):(x))
int xo, yo, R;
int inline inCircle( int x, int y ){ // 19.1, 19.1, 19.1
int dx = ABS(x-xo);
if ( dx > R ) return FALSE;
int dy = ABS(y-yo);
if ( dy > R ) return FALSE;
if ( dx+dy <= R ) return TRUE;
return ( dx*dx + dy*dy <= R*R );
}
int inline inCircleN( int x, int y ){ // 21.3, 21.1, 21.5
int dx = ABS(x-xo);
int dy = ABS(y-yo);
return ( dx*dx + dy*dy <= R*R );
}
int inline dummy( int x, int y ){ // 16.6, 16.5, 16.4
int dx = ABS(x-xo);
int dy = ABS(y-yo);
return FALSE;
}
#define N 1000000000
int main(){
int x, y;
xo = rand()%1000; yo = rand()%1000; R = 1;
int n = 0;
int c;
for (c=0; c<N; c++){
x = rand()%1000; y = rand()%1000;
// if ( inCircle(x,y) ){
if ( inCircleN(x,y) ){
// if ( dummy(x,y) ){
n++;
}
}
printf( "%d of %d inside circle/n", n, N);
}
Mi respuesta en C # como una solución completa de cortar y pegar (no optimizada):
public static bool PointIsWithinCircle(double circleRadius, double circleCenterPointX, double circleCenterPointY, double pointToCheckX, double pointToCheckY)
{
return (Math.Pow(pointToCheckX - circleCenterPointX, 2) + Math.Pow(pointToCheckY - circleCenterPointY, 2)) < (Math.Pow(circleRadius, 2));
}
Uso:
if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }
Pasando al mundo de 3D, si quieres comprobar si un punto 3D está en una esfera de unidad, terminas haciendo algo similar. Todo lo que se necesita para trabajar en 2D es usar operaciones vectoriales 2D.
public static bool Intersects(Vector3 point, Vector3 center, float radius)
{
Vector3 displacementToCenter = point - center;
float radiusSqr = radius * radius;
bool intersects = displacementToCenter.magnitude < radiusSqr;
return intersects;
}
Puedes usar Pitágoras para medir la distancia entre tu punto y el centro y ver si es más bajo que el radio:
def in_circle(center_x, center_y, radius, x, y):
dist = math.sqrt((center_x - x) ** 2 + (center_y - y) ** 2)
return dist <= radius
EDITAR (punta de sombrero a Paul)
En la práctica, la cuadratura a menudo es mucho más económica que sacar la raíz cuadrada y, como solo nos interesa realizar un pedido, podemos, por supuesto, evitar la raíz cuadrada:
def in_circle(center_x, center_y, radius, x, y):
square_dist = (center_x - x) ** 2 + (center_y - y) ** 2
return square_dist <= radius ** 2
Además, Jason señaló que <= debe reemplazarse por < y, dependiendo del uso, esto puede tener sentido. aunque creo que no es cierto en el sentido matemático estricto . Me quedo corregido.
Sé que está a pocos años de la respuesta mejor votada, pero he logrado reducir el tiempo de cálculo en 4.
Solo necesitas calcular los píxeles de 1/4 del círculo, luego multiplicar por 4.
Esta es la solución que he alcanzado:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int x, y, r;
int mx, c, t;
int dx, dy;
int p;
int main() {
for (r = 1; r < 128; r++){
clock_t t;
t = clock();
p = calculatePixels(r);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
printf( "%d of pixels inside circle with radius %d, took %f seconds to execute /n", p, r, time_taken);
}
}
int calculatePixels(int r){
mx = 2 * r;
c = (mx+1)*(mx+1);
t = r * r;
int a = 0;
for (x = 0; x < r; x++){
for (y = 0; y < r; y++){
dx = x-r;
dy = y-r;
if ((dx*dx + dy*dy) > t)
a++;
else
y = r;
}
}
return (c - (a * 4));
}
Utilicé el siguiente código para principiantes como yo :).
clase pública incirkel {
public static void main(String[] args) {
int x;
int y;
int middelx;
int middely;
int straal; {
// Adjust the coordinates of x and y
x = -1;
y = -2;
// Adjust the coordinates of the circle
middelx = 9;
middely = 9;
straal = 10;
{
//When x,y is within the circle the message below will be printed
if ((((middelx - x) * (middelx - x))
+ ((middely - y) * (middely - y)))
< (straal * straal)) {
System.out.println("coordinaten x,y vallen binnen cirkel");
//When x,y is NOT within the circle the error message below will be printed
} else {
System.err.println("x,y coordinaten vallen helaas buiten de cirkel");
}
}
}
}}
Esta es la misma solución mencionada por Jason Punyon , pero contiene un ejemplo de pseudocódigo y algunos detalles más. Vi su respuesta después de escribir esto, pero no quería eliminar la mía.
Creo que la forma más fácil de entender es calcular primero la distancia entre el centro del círculo y el punto. Yo usaría esta fórmula:
d = sqrt((circle_x - x)^2 + (circle_y - y)^2)
Luego, simplemente compare el resultado de esa fórmula, la distancia ( d ), con el radius . Si la distancia ( d ) es menor o igual que el radio ( r ), el punto está dentro del círculo (en el borde del círculo si d y r son iguales).
Aquí hay un ejemplo de pseudocódigo que se puede convertir fácilmente a cualquier lenguaje de programación:
function is_in_circle(circle_x, circle_y, r, x, y)
{
d = sqrt((circle_x - x)^2 + (circle_y - y)^2);
return d <= r;
}
Donde circle_x y circle_y son las coordenadas del centro del círculo, r es el radio del círculo, y x e y son las coordenadas del punto.
boolean isInRectangle(double centerX, double centerY, double radius,
double x, double y)
{
return x >= centerX - radius && x <= centerX + radius &&
y >= centerY - radius && y <= centerY + radius;
}
//test if coordinate (x, y) is within a radius from coordinate (center_x, center_y)
public boolean isPointInCircle(double centerX, double centerY,
double radius, double x, double y)
{
if(isInRectangle(centerX, centerY, radius, x, y))
{
double dx = centerX - x;
double dy = centerY - y;
dx *= dx;
dy *= dy;
double distanceSquared = dx + dy;
double radiusSquared = radius * radius;
return distanceSquared <= radiusSquared;
}
return false;
}
Esto es más eficiente y legible. Evita la costosa operación de la raíz cuadrada. También agregué una verificación para determinar si el punto está dentro del rectángulo delimitador del círculo.
La verificación del rectángulo es innecesaria excepto con muchos puntos o muchos círculos. Si la mayoría de los puntos están dentro de círculos, ¡la verificación del rectángulo delimitador hará que las cosas sean más lentas!
Como siempre, asegúrese de considerar su caso de uso.