Prueba de posición de punto y elipse (girada): algoritmo

Question

Cómo comprobar si un punto P = [xp, yp] está dentro/fuera de una elipse girada dada por el centro C = [x, y], a, b, y phi (ángulo de rotación)?

En este momento estoy usando la siguiente solución: rotar elipse y señalar por el ángulo -phi y luego la prueba común para una posición del punto y elipse "no girado".

Pero hay muchos puntos probados (miles) y considero que esta solución es lenta. ¿Hay alguna manera directa y más eficiente de obtener una posición de la elipse y el punto girados?

No necesito un código, pero el algoritmo. Gracias por tu ayuda.

Answer 1

Otra opción es solo echar todo a la ecuación para una elipse girada en 2D y ver si el resultado es menor que uno.

Así que es un punto dentro de la elipse si la siguiente desigualdad es cierta

Dónde (xp, yp) son las coordenadas del punto y (x0, y0) es el centro de la elipse.

implementé un pequeño programa Mathematica que demuestra que este hecho funciona:

Aquí está en acción:

Y aquí está el código:

ellipse[x_, y_, a_, b_, \[Alpha]_, x0_: 0, y0_: 0] := 
    (((x - x0)*Cos[\[Alpha]] + (y - y0)*Sin[\[Alpha]])/a)^2 
    + (((x - x0)*Sin[\[Alpha]] - (y - y0)*Cos[\[Alpha]])/b)^2; 

Manipulate[ 
RegionPlot[ 
    ellipse[x, y, a, b, \[Alpha] \[Degree], Sequence @@ pos] < 1, {x, -5, 5}, {y, -5, 5}, 
    PlotStyle -> If[ellipse[Sequence @@ p, a, b, \[Alpha] \[Degree], Sequence @@ pos] <= 1, Orange, LightBlue], 
    PlotPoints -> 25] 
, {{a, 2}, 1, 5, Appearance -> "Labeled"} 
, {{b, 4}, 2, 5, Appearance -> "Labeled"} 
, {\[Alpha], 0, 180, Appearance -> "Labeled"} 
, {{p, {3, 1}}, Automatic, ControlType -> Locator} 
, {{pos, {0, 0}}, Automatic, ControlType -> Locator}] 

Answer 2

Para manejar las elipses, prefiero transformarlas en otro sistema de coordenadas donde la elipse es un círculo unitario centrado en el origen.

Si ve la elipse como un círculo unitario (radio 1), escalado por (a, b), rotado por phi y transformado por (x, y), entonces la vida se vuelve mucho más fácil. Si tiene esa matriz de transformación, puede usarla para hacer una consulta de contención más fácil. Si transforma el punto para que esté en el sistema de coordenadas donde la elipse es un círculo unitario, todo lo que tiene que hacer es una prueba de círculo punto a unidad que es trivial. Si "transformar" es una matriz que transforma un círculo unidad en su elipse como se describe, a continuación,

transformedPoint = transform.Invert().Transform(point); 
pointInEllipse = transformedPoint.DistanceTo(0,0) < 1.0; 

Answer 3

Aquí está el algoritmo, dejo a desarrollar el código:

1. Determine el vector v1 entre el centro de la elipse y su punto de
2. Determinar el ángulo entre el vector v1 A1 y el eje x en coordenadas
3. phi Restar de A1 a A2 conseguir, nuestro ángulo del vector en coordenadas locales
4. Determinar punto P2 en elipse en a2 ángulo en coordenadas locales, no compensado por (x, y)
5. Compute L1 y L2, la longitud del vector de a1 y a2

Evaluación:

1. Si L1 < L2 el punto está dentro
2. Si L1 = L2 (más/menos una pequeña tolerancia) el punto está en la elipse
3. Si L2> L2 el punto está fuera

Elipse fórmula paramétrica:

x = a * cos (u)
y = b * sin (u)

válido para u entre -pi y + pi. Agrega phi a ti para rotar tu elipse.

El algoritmo anterior se puede simplificar y optimizar a partir de ecuaciones de elipse.

¡Buena suerte!

Answer 4

Simplemente puede alimentar sus datos en la fórmula indicada arriba. Aquí es una implementación de Python que hice en las recomendaciones del Ajasja:

def pointInEllipse(x,y,xp,yp,d,D,angle): 
    #tests if a point[xp,yp] is within 
    #boundaries defined by the ellipse 
    #of center[x,y], diameter d D, and tilted at angle 

    cosa=math.cos(angle) 
    sina=math.sin(angle) 
    dd=d/2*d/2 
    DD=D/2*D/2 

    a =math.pow(cosa*(xp-x)+sina*(yp-y),2) 
    b =math.pow(sina*(xp-x)-cosa*(yp-y),2) 
    ellipse=(a/dd)+(b/DD) 

    if ellipse <= 1: 
     return True 
    else: 
     return False 

Answer 5

Matplotlib tiene un método Elipse parches dentro de la clase, que le permite hacer la pregunta si un punto está dentro o fuera del parche. Compruebe here y busque el método contains_point(). Tendrá que crear la elipse con la clase Elipse, y luego como si hubiera un punto adentro. BTW, matplotlib es un paquete para python.