algorithm - rectas - Algoritmo matemático eficiente para calcular intersecciones

punto de interseccion de una funcion

Question

Para un juego que estoy desarrollando necesito un algoritmo que pueda calcular intersecciones. He resuelto el problema, pero la forma en que lo hice es realmente desagradable y espero que alguien aquí tenga una solución más elegante.

Un par de puntos representan los puntos finales de una línea dibujada entre ellos. Dado dos pares de puntos, ¿las líneas trazadas se cruzan, y si es así, en qué punto?

Entonces, por ejemplo, llame a las líneas (Axe, Ay) - (Bx, By) y (Cx, Cy) - (Dx, Dy)

¿Alguien puede pensar en una solución? Una solución en cualquier idioma servirá.

Editar: Un punto que debería haber aclarado, el algoritmo debe devolver falso si el punto de intersección está más allá de las longitudes de los segmentos de línea.

Answer 1

(Dejaría esto como un comentario, excepto que aún no he descubierto cómo hacerlo).

Me gustaría agregar que, como alternativa / complemento a una prueba de cuadro delimitador, también podría probar para ver si la distancia entre los puntos medios de las líneas es mayor que la mitad de la longitud combinada de las líneas. Si es así, las líneas no pueden cruzarse.

Imagine un círculo delimitador mínimo para cada línea, luego pruebe la intersección del círculo. Esto permite precomputar (al menos para líneas estáticas y líneas que conservan su longitud) y una forma eficiente de excluir muchas intersecciones potenciales.

Answer 2

Bueno, las matemáticas y los productos escalares pueden ayudar allí.
- Digamos que quiere intersectar segmentos [AB] y [CD]
- Supongamos que la línea de intersección de las líneas es M

M está dentro del segmento [ÅB] si y solo si
Vector (AB). Vector (AM)> = 0
y
Vector (AB). Vector (MB)> = 0

Donde el punto "." denota un producto escalar: u. v = ux * vx + uy * vy

Entonces, tu algo es:
- encuentra M
- M está dentro de ambos segmentos si y solo si las 4 eq siguientes son verdaderas
Vector (AB). Vector (AM)> = 0
Vector (AB). Vector (MB)> = 0
Vector (CD). Vector (CM)> = 0
Vector (CD). Vector (MD)> = 0

Espero que esto ayude

Answer 3

Debajo está mi intersección línea-línea como se describe en MathWorld . Para la detección / intersección general de colisiones, puede consultar el Teorema del Eje Separativo . Encontré este tutorial en SAT muy informativo.

    /// <summary>
    /// Returns the intersection point of the given lines. 
    /// Returns Empty if the lines do not intersect.
    /// Source: http://mathworld.wolfram.com/Line-LineIntersection.html
    /// </summary>
    public static PointF LineIntersection(PointF v1, PointF v2, PointF v3, PointF v4)
    {
        float tolerance = 0.000001f;

        float a = Det2(v1.X - v2.X, v1.Y - v2.Y, v3.X - v4.X, v3.Y - v4.Y);
        if (Math.Abs(a) < float.Epsilon) return PointF.Empty; // Lines are parallel

        float d1 = Det2(v1.X, v1.Y, v2.X, v2.Y);
        float d2 = Det2(v3.X, v3.Y, v4.X, v4.Y);
        float x = Det2(d1, v1.X - v2.X, d2, v3.X - v4.X) / a;
        float y = Det2(d1, v1.Y - v2.Y, d2, v3.Y - v4.Y) / a;

        if (x < Math.Min(v1.X, v2.X) - tolerance || x > Math.Max(v1.X, v2.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v1.Y, v2.Y) - tolerance || y > Math.Max(v1.Y, v2.Y) + tolerance) return PointF.Empty;
        if (x < Math.Min(v3.X, v4.X) - tolerance || x > Math.Max(v3.X, v4.X) + tolerance) return PointF.Empty;
        if (y < Math.Min(v3.Y, v4.Y) - tolerance || y > Math.Max(v3.Y, v4.Y) + tolerance) return PointF.Empty;

        return new PointF(x, y);
    }

    /// <summary>
    /// Returns the determinant of the 2x2 matrix defined as
    /// <list>
    /// <item>| x1 x2 |</item>
    /// <item>| y1 y2 |</item>
    /// </list>
    /// </summary>
    public static float Det2(float x1, float x2, float y1, float y2)
    {
        return (x1 * y2 - y1 * x2);
    }

Answer 4

La mayoría de las respuestas que ya están aquí parecen seguir la idea general de que:

1. encuentra la intersección de dos líneas rectas que pasan los puntos dados.
2. determinar si la intersección pertenece a ambos segmentos de línea.

Pero cuando la intersección no ocurre a menudo, una mejor manera es invertir estos pasos:

1. expresar las líneas rectas en la forma de y = ax + b (línea que pasa A, B) y y = cx + d (línea que pasa C, D)
2. mira si C y D están en el mismo lado de y = ax + b
3. ver si A y B están en el mismo lado de y = cx + d
4. si la respuesta a lo anterior es ambas no , entonces hay una intersección. de lo contrario, no hay intersección.
5. encuentra la intersección si hay una.

Nota: para hacer el paso 2, simplemente verifique si (Cy - a (Cx) - b) y (Dy - a (Dx) - b) tienen el mismo signo. El paso 3 es similar. El paso 5 es solo matemática estándar de las dos ecuaciones.

Además, si necesita comparar cada segmento de línea con (n-1) otros segmentos de línea, el paso de precomputación 1 para todas las líneas le ahorra tiempo.

Answer 5

Si tienes la oportunidad, deberías echar un vistazo a la Biblia Detección de colisión, "Detección de colisiones en tiempo real" si planeas hacer algo que no sea trivial. No soy un programador de juegos profesional y entendí y podría aplicar los conceptos en él sin problemas.

Amazon - Detección de colisiones en tiempo real

Básicamente, hacer un conjunto de pruebas de intersección de líneas es costoso sin importar qué. Lo que debes hacer es usar cosas como Cajas de delimitación (alineadas u orientadas) sobre tus polígonos complejos. Esto le permitirá hacer rápidamente una prueba en el peor de los casos O (N ^ 2) de colisión entre cada "objeto". A continuación, puede acelerar las cosas aún más utilizando árboles espaciales (Particiones Binarias o Cuadretas) al solo verificar intersecciones de objetos cercanos entre sí.

Esto le permite podar muchas, muchas pruebas de colisión. La mejor optimización no es hacer algo en absoluto. Solo cuando tienes una colisión entre cajas delimitadoras, haces tus costosas intersecciones de líneas para determinar si los objetos realmente se cruzan o no. Esto le permite escalar el número de objetos manteniendo la velocidad razonable.

Answer 6

Una optimización simple que puede ahorrarle mucho tiempo es verificar los cuadros delimitadores alineados con el eje de las líneas antes de entrar en el cálculo de intersección.
Si los cuadros delimitadores son completamente disjuntos, entonces puede estar seguro de que no hay intersección.
Por supuesto, esto depende de los datos que tenga. Si es muy probable que haya una intersección en cada control que realice, es posible que pierda el tiempo en un control que siempre es cierto.

Answer 7

public struct PointD
{
    public double X { get; set; }
    public double Y { get; set; }
}

/// <summary>
/// Find the intersection point between two lines.
/// </summary>
/// <param name="IntersectPoint">The intersection point. A <see cref="Esteem.Geometry.PointD">PointD</see> structure.</param>
/// <param name="L1StartPoint">The starting point of first line. A PointD structure.</param>
/// <param name="L1EndPoint">The end point of first line. A PointD structure.</param>
/// <param name="L2StartPoint">The starting point of second line. A PointD structure.</param>
/// <param name="L2EndPoint">The end point of second line. A PointD structure.</param>
/// <param name="L1IntersectPos">The intersection position at first line.</param>
/// <param name="L2IntersectPos">The intersection position at second line.</param>
/// <returns>Returns a boolean. True if there is intersection, false otherwise.</returns>
/// <remarks>The formula is taken from comp.graphics.algorithms Frequently Asked Questions.</remarks>
public static bool LineIntersect(out PointD IntersectPoint, PointD L1StartPoint, PointD L1EndPoint, PointD L2StartPoint, PointD L2EndPoint, out double L1IntersectPos, out double L2IntersectPos) 
{
    IntersectPoint = new PointD();
    double ay_cy, ax_cx, px, py;
    double dx_cx = L2EndPoint.X - L2StartPoint.X,
        dy_cy = L2EndPoint.Y - L2StartPoint.Y,
        bx_ax = L1EndPoint.X - L1StartPoint.X,
        by_ay = L1EndPoint.Y - L1StartPoint.Y;

    double de = (bx_ax) * (dy_cy) - (by_ay) * (dx_cx);
    //double tor = 1.0E-10;     //tolerance


    L1IntersectPos = 0;      L2IntersectPos = 0;
    if (Math.Abs(de)<0.01)
        return false;
    //if (de > -tor && de < tor) return false; //line is in parallel

    ax_cx = L1StartPoint.X - L2StartPoint.X;
    ay_cy = L1StartPoint.Y - L2StartPoint.Y;
    double r = ((ay_cy) * (dx_cx) - (ax_cx) * (dy_cy)) / de;
    double s = ((ay_cy) * (bx_ax) - (ax_cx) * (by_ay)) / de;
    px = L1StartPoint.X + r * (bx_ax);
    py = L1StartPoint.Y + r * (by_ay);

    IntersectPoint.X = px;  //return the intersection point
    IntersectPoint.Y = py;  //return the intersection position
    L1IntersectPos = r;      L2IntersectPos = s;

    return true; //indicate there is intersection
}

Para verificar si el punto de intersección no está más allá de la longitud original de la línea, solo asegúrese de que 0<r<1 y 0<s<1

Answer 8

float x12 = x1 - x2;
float x34 = x3 - x4;
float y12 = y1 - y2;
float y34 = y3 - y4;

float c = x12 * y34 - y12 * x34;

if (fabs(c) < 0.01)
{
  // No intersection
  return false;
}
else
{
  // Intersection
  float a = x1 * y2 - y1 * x2;
  float b = x3 * y4 - y3 * x4;

  float x = (a * x34 - b * x12) / c;
  float y = (a * y34 - b * y12) / c;

  return true;
}

Fórmulas tomadas de:
Intersección línea de línea - Wikipedia

Answer 9

private function Loop(e:Event):void
{
    var x12:Number = Ball1.x - Ball2.x;
    var x34:Number = Ball3.x - Ball4.x;
    var y12:Number = Ball1.y - Ball2.y;
    var y34:Number = Ball3.y - Ball4.y;

    // Det
    var c:Number = x12 * y34 - y12 * x34;

    if (Math.abs(c) < 0.01)
    {
        Circle.visible = false;
    }
    else
    {
        var a:Number = Ball1.x * Ball2.y - Ball1.y * Ball2.x;
        var b:Number = Ball3.x * Ball4.y - Ball3.y * Ball4.x;
        var px:Number = (a * x34 - b * x12) / c;
        var py:Number = (a * y34 - b * y12) / c;

        var Btwn12x:Boolean = (px >= Math.min(Ball1.x, Ball2.x)) && (px <= Math.max(Ball1.x, Ball2.x));
        var Btwn12y:Boolean = (py >= Math.min(Ball1.y, Ball2.y)) && (py <= Math.max(Ball1.y, Ball2.y));
        var Btwn34x:Boolean = (px >= Math.min(Ball3.x, Ball4.x)) && (px <= Math.max(Ball3.x, Ball4.x));
        var Btwn34y:Boolean = (py >= Math.min(Ball3.y, Ball4.y)) && (py <= Math.max(Ball3.y, Ball4.y));

        var Btwn12:Boolean = Btwn12x && Btwn12y;
        var Btwn34:Boolean = Btwn34x && Btwn34y;

        if(Btwn12 && Btwn34)
        {
            Circle.visible = true;
            Circle.x = px;
            Circle.y = py;
        }
        else
        {
            Circle.visible = false;
        }
    }
}