Puntos de intersección entre la línea y la elipse

Question

Intento averiguar si una línea interseca una elipse.

Al principio intenté hacerlo sin encontrar los puntos de intersección, pero no funcionó bien. Así que ahora estoy tratando de encontrar los dos puntos de intersección y luego comprobar si están en el segmento de línea.

Primero intenté implementar un algoritmo para encontrar una línea, perpendicular al segmento de línea, desde el centro de la elipse hasta el segmento de línea. Si cualquiera de los dos puntos finales estaba en la elipse o el punto de intersección estaba tanto en el segmento de línea como en la elipse, entonces se intersectaban. Sin embargo, en algunas situaciones, esto fallaba alrededor del perímetro de la elipse.

Así que a continuación traté de implementar un algoritmo discutido en: Coordenadas de los puntos de intersección entre una elipse y una línea de cuerda

He utilizado la respuesta de Hamed. Sin embargo, parece que no me funciona. Esperaba que alguien pudiera decirme qué estoy haciendo mal. El $x$ Los valores salen mucho más altos de lo que deberían, y a menudo determina que no hay raíces reales cuando sí las hay. No veo la diferencia entre mi implementación y la solución. Tengo curiosidad por saber si lo he implementado mal, si la ecuación está mal o si hay algo más que se me escapa.

Gracias de antemano, agradezco cualquier ayuda que pueda recibir ya que me he encontrado con un bloqueo en este punto.

Editar : $a$ y $b$ son de tamaño arbitrario, $a$ puede ser mayor que $b$ y viceversa. la elipse está en el origen $(0,0)$ y la línea es un segmento de línea que se define por los puntos finales. también te darás cuenta de que he multiplicado las cosas por sí mismas en lugar de utilizar la función incorporada para elevar algo al cuadrado, ya que he leído que es caro en términos de potencia de cálculo.

Editar Aquí hay un ejemplo

public function lineTest( test_ellipse:Geometry_Ellipse, test_line:Geometry_Line ):Object {
        // get the variables that define the line and ellipse
        var m:Number = test_line.getSlope();
        var c:Number = test_line.getY_Intercept();
        var a:Number = test_ellipse.getRadius_X();
        var b:Number = test_ellipse.getRadius_Y();

        // check for division by 0 and sqrt of negative values
        if( (b*b)+(m*a)*(m*a)-(c*c) >= 0 && (b*b)+(m*a)*(m*a) != 0 ) {
            // get intersection points
            var point_1:Geometry_Coordinate = new Geometry_Coordinate(
                ( (m*c*a)*(m*c*a) + (a*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                ( (c*b)*(c*b) - ((m*a)*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                0
            );
            var point_2:Geometry_Coordinate = new Geometry_Coordinate(
                ( (m*c*a)*(m*c*a) - (a*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                ( (c*b)*(c*b) + ((m*a)*b)*Math.sqrt((b*b)+(m*a)*(m*a)-(c*c)) ) / ( (b*b)+(m*a)*(m*a) ),
                0
            );

            // check if points are on line segment
            // ...

            return { "result":true, "points":new Array(point_1, point_2) };
        } else {
            trace("no real values");
        }

        return { "result":false, "points":new Array() };
    }

Answer 1

Para saber si una determinada línea $r$ intersecta una elipse, yo sugeriría el siguiente método. En primer lugar, es necesario conocer las posiciones $F_1$ y $F_2$ de los focos de la elipse, y su semieje mayor $a$ .

1) Encuentre la simétrica $F_1'$ de enfoque $F_1$ con respecto a $r$ .

2) Encontrar la intersección $P$ entre $r$ y la línea $F_2F_1'$ .

3) Calcular $PF_1+PF_2$ : si $PF_1+PF_2<2a$ entonces $r$ interseca la elipse; si $PF_1+PF_2>2a$ entonces $r$ no interseca la elipse; si $PF_1+PF_2=2a$ entonces $r$ es tangente a la elipse.

EDITAR.

Si queremos encontrar si un segmento $AB$ interseca la elipse, podemos seguir los pasos 1) y 2) anteriores para encontrar $P$ (donde $r$ es, por supuesto, la línea que contiene $AB$ ). Segmento $AB$ interseca la elipse si y sólo si se da uno de los siguientes casos:

a) $AF_1+AF_2\ge2a$ Y $BF_1+BF_2\le2a$ ;

b) $AF_1+AF_2\le2a$ Y $BF_1+BF_2\ge2a$ ;

c) $AF_1+AF_2>2a$ Y $BF_1+BF_2>2a$ Y $PF_1+PF_2<2a$ Y $P$ está dentro $AB$ .

Answer 2

No pude determinar qué era lo que estaba mal en la implementación anterior... sin embargo, pude encontrar los puntos de intersección usando una ecuación diferente.

utilizando la ecuación cuadrática proporcionada en: http://www.analyzemath.com/Calculators/ellipse_line_calc.html Pude reducir la ecuación que me proporcionaron a la siguiente ecuación cuadrática:

elipse: x^2/A^2 + y^2/B^2 = 1 recta: mx + b = y

(B^2+A^2*m^2)x^2+(2*m*A^2*b)x+(A^2*b^2-A^2*B^2) = 0

después de obtener esta ecuación cuadrática y una solución general para ecuaciones cuadráticas ( proporcionada por: http://pages.mtu.edu/~shene/COURSES/cs201/NOTES/chap03/quad-2.html ) Pude encontrar 2 valores de X y luego insertarlos en la ecuación de la línea para encontrar los 2 valores de Y.

    // find x values of a quadratic function defined by
    // Ax^2 + Bx + C = 0
    public function solveQuadratic( A:Number, B:Number, C:Number ):Array {
        var sqrt_val:Number = (B*B) - (4*A*C);
        if( sqrt_val >= 0 ) {
            return new Array(
                (1/(2*A))*(-B + Math.sqrt(sqrt_val)),
                (1/(2*A))*(-B - Math.sqrt(sqrt_val))
            );
        } else {
            throw new Error("No real roots.");
        }
    }

    public function lineTest( test_line:Geometry_Line, test_ellipse:Geometry_Ellipse ):Object {
        // get the variables that define the line and ellipse
        var m:Number = test_line.getSlope();
        var b:Number = test_line.getY_Intercept();
        var A:Number = test_ellipse.getRadius_X();
        var B:Number = test_ellipse.getRadius_Y();

        // ellipse = x^2/A^2 + y^2/B^2 = 1, line = mx + b = y
        // (B^2+A^2*m^2)x^2+(2*m*A^2*b)x+(A^2*b^2-A^2*B^2) = 0
        var val_1:Number = (B*B)+((A*A)*(m*m));
        var val_2:Number = (2*m*(A*A)*b);
        var val_3:Number = ((A*A)*(b*b)-(A*A)*(B*B));

        try {
            var points:Array = solveQuadratic(val_1, val_2, val_3);
            var point_1:Geometry_Coordinate = new Geometry_Coordinate(points[0], (m*points[0]+b), 0);
            var point_2:Geometry_Coordinate = new Geometry_Coordinate(points[1], (m*points[1]+b), 0);

            // check if points are on line segment
            // ...

            return { "result":true, "points":new Array(point_1, point_2) };
        } catch( e:Error ) {
            return { "result":false, "points":new Array() };
        }
    }