¿Cómo verifico de manera eficiente si un punto está dentro de un rectángulo girado?

11

Parte por el bien de la optimización, parte con fines de aprendizaje, me atreveré a preguntar: ¿Cómo puedo verificar de manera más eficiente si un punto 2D Pestá dentro de un rectángulo girado 2D XYZW, usando C # o C ++?

Actualmente, lo que estoy haciendo es usar un algoritmo de "punto en triángulo" que se encuentra en el libro Detección de colisión en tiempo real , y ejecutarlo dos veces (para los dos triángulos que forman el rectángulo, digamos XYZ y XZW):

bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
 // Compute vectors        
 Vector2 v0 = C - A;
 Vector2 v1 = B - A;
 Vector2 v2 = P - A;

 // Compute dot products
 float dot00 = Vector2.Dot(v0, v0);
 float dot01 = Vector2.Dot(v0, v1);
 float dot02 = Vector2.Dot(v0, v2);
 float dot11 = Vector2.Dot(v1, v1);
 float dot12 = Vector2.Dot(v1, v2);

 // Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

 // Check if point is in triangle
 if(u >= 0 && v >= 0 && (u + v) < 1)
    { return true; } else { return false; }
}


bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
 if(PointInTriangle(X,Y,Z,P)) return true;
 if(PointInTriangle(X,Z,W,P)) return true;
 return false;
}

Sin embargo, tengo la sensación de que podría haber una forma más limpia y rápida. Específicamente, para reducir el número de operaciones matemáticas.

Louis15
fuente
¿Tienes muchos puntos o tienes muchos rectángulos? Esa es la primera pregunta que debe hacerse antes de intentar optimizar una tarea tan pequeña.
sam hocevar
Buen punto. Tendré una cantidad muy alta de puntos, pero aún más rectángulos para verificar.
Louis15
Pregunta relacionada sobre cómo encontrar la distancia de un punto a un rectángulo girado . Este es un caso degenerado de eso (verificando solo cuando la distancia es 0). Por supuesto, habrá optimizaciones que se aplican aquí que no existen.
Anko
¿Has considerado rotar el punto en el marco de referencia del rectángulo?
Richard Tingle
@ RichardTingle En realidad no lo hice al principio. Más tarde lo hice, porque creo que se relaciona con una de las respuestas que se dan a continuación. Pero solo para aclarar: en lo que está sugiriendo, después de rotar el punto al marco de referencia de los rectángulos, entonces uno debe verificar la inclusión simplemente mediante comparaciones lógicas entre max.x, min.x, etc.
Louis15

Respuestas:

2

Una optimización fácil y directa sería cambiar la condición final en PointInTriangle:

bool PointInRectangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P) {
  ...
  if(u >= 0 && v >= 0 && u <= 1 && v <= 1)
      { return true; } else { return false; }
  }
}

el código ya estaba más o menos PointInRectangle, la condición (u + v) < 1estaba allí para verificar si no está en el "segundo" triángulo del rectángulo.

Alternativamente, también podría hacer una isLeftprueba (primer ejemplo de código en la página, también muy explicada) cuatro veces, y verificar que todos devuelvan resultados con el mismo signo (que depende de si los puntos se dieron en el sentido horario o antihorario) para El punto de estar adentro. Esto también funciona para cualquier otro polígono convexo.

float isLeft( Point P0, Point P1, Point P2 )
{
    return ( (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y) );
}
bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
    return (isLeft(X, Y, P) > 0 && isLeft(Y, Z, P) > 0 && isLeft(Z, W, P) > 0 && isLeft(W, X, p) > 0);
}
wondra
fuente
Soberbio. ¡No sé si me gusta más tu sugerencia, que es realmente más rápida y mucho más elegante que la mía, o si me gusta más que has notado que mi código PointInTri podría convertirse fácilmente en un PointInRec! Gracias
Louis15
+1 para el isLeftmétodo. No requiere funciones trigonométricas (como lo Vector2.Dothace), lo que acelera mucho las cosas.
Anko
Por cierto, ¿no podría modificarse el código (no se probó; no tengo cómo hacerlo en esta computadora), al incluir isLeft directamente dentro de la función principal, y al sustituir los operadores "&&" por "||" a través de la lógica inversa? public static bool PointInRectangle(Vector2 P, Vector2 X, Vector2 Y, Vector2 Z, Vector2 W) { return !(( (Y.x - X.x) * (P.y - X.y) - (P.x - X.x) * (Y.y - X.y) ) < 0 || ( (Z.x - Y.x) * (P.y - Y.y) - (P.x - Y.x) * (Z.y - Y.y) ) < 0 || ( (W.x - Z.x) * (P.y - Z.y) - (P.x - Z.x) * (W.y - Z.y) ) < 0 || ( (X.x - W.x) * (P.y - W.y) - (P.x - W.x) * (X.y - W.y) ) < 0 ); }
Louis15
1
@ Louis15 No creo que sea necesario, tanto && como || dejará de ejecutar más declaraciones si se encontró una negativa / positiva (¿o hubo alguna otra razón?). Declarar isLeftcomo en línea el compilador hará algo similar para usted (y probablemente mejor de lo que podría hacerlo, porque los ingenieros que escribieron el compilador conocían mejor las CPU, eligiendo la opción más rápida) haciendo que su código sea más legible con el mismo o mejor efecto.
wondra
8

Editar: El comentario de los OPs ha sido escéptico sobre la eficiencia de la verificación de límite circular negativa sugerida para mejorar el algoritmo para verificar si un punto 2D arbitrario se encuentra dentro de un rectángulo girado y / o en movimiento. Jugueteando un poco en mi motor de juego 2D (OpenGL / C ++), complemente mi respuesta al proporcionar un punto de referencia de rendimiento de mi algoritmo contra los algoritmos actuales de verificación de punto en rectángulo (y variaciones) de los OP.

Originalmente sugerí dejar el algoritmo en su lugar (ya que es casi óptimo), pero simplificar mediante la simple lógica del juego: (1) usar un círculo preprocesado alrededor del rectángulo original; (2) hacer una verificación de distancia y si el punto se encuentra dentro del círculo dado; (3) use los OP u otro algoritmo sencillo (recomiendo el algoritmo isLeft como se proporciona en otra respuesta). La lógica detrás de mi sugerencia es que verificar si un punto está dentro de un círculo es considerablemente más eficiente que una verificación de límites de un rectángulo girado o cualquier otro polígono.

Mi escenario inicial para una prueba de referencia es ejecutar una gran cantidad de puntos que aparecen y desaparecen (cuya posición cambia en cada bucle de juego) en un espacio restringido que se llenará con alrededor de 20 cuadrados giratorios / en movimiento. He publicado un video ( enlace de youtube ) con fines ilustrativos. Observe los parámetros: número de puntos, números o rectángulos que aparecen al azar. Voy a comparar con los siguientes parámetros:

APAGADO : Algoritmo directo proporcionado por el OP sin verificaciones negativas de límites circulares

EN : uso de círculos procesados ​​(límite) alrededor de los rectángulos como primera verificación de exclusión

ENCENDIDO + Pila : creación de límites de círculo en tiempo de ejecución dentro del bucle en la pila

ON + Distancia cuadrada : Usar distancias cuadradas como una optimización adicional para evitar tomar el algoritmo de raíz cuadrada más costoso (Pieter Geerkens).

Aquí hay un resumen de las diversas actuaciones de diferentes algoritmos mostrando el tiempo que lleva iterar a través del ciclo.

ingrese la descripción de la imagen aquí

El eje x muestra una mayor complejidad al agregar más puntos (y así desacelerar el ciclo). (Por ejemplo, en 1000 verificaciones de puntos que aparecen aleatoriamente en un espacio confiado con 20 rectángulos, el bucle itera y llama al algoritmo 20000 veces). El eje y muestra el tiempo que tarda (ms) en completar todo el bucle con una alta resolución temporizador de rendimiento. Más de 20 ms sería problemático para un juego decente, ya que no aprovecharía los altos fps para interpolar una animación fluida y el juego puede parecer así 'resistente' a veces.

Resultado 1 : un algoritmo de enlace circular preprocesado con una comprobación negativa rápida dentro del bucle mejora el rendimiento en un 1900% en comparación con el algoritmo normal (5% del tiempo del bucle original sin una comprobación). El resultado es aproximadamente proporcional al número de iteraciones dentro de un ciclo, por lo tanto, no importa si verificamos 10 o 10000 puntos que aparecen al azar. Por lo tanto, en esta ilustración se puede aumentar la cantidad de objetos de forma segura a 10k sin sentir una pérdida de rendimiento.

Resultado 2 : un comentario anterior sugirió que el algoritmo puede ser más rápido pero requiere mucha memoria. Sin embargo, tenga en cuenta que almacenar un flotante para el tamaño del círculo preprocesado solo requiere 4 bytes. Esto no debería plantear ningún problema real a menos que el OP planee ejecutar simultáneamente más de 100000 objetos. Un enfoque alternativo y eficiente en la memoria es calcular el tamaño máximo del círculo en la pila dentro del bucle y dejarlo fuera de alcance con cada iteración y, por lo tanto, prácticamente no usar memoria por un precio desconocido de velocidad. De hecho, el resultado muestra que este enfoque es realmente más lento que el uso de un tamaño de círculo preprocesado, pero aún muestra una mejora considerable del rendimiento de alrededor del 1150% (es decir, el 8% del tiempo de procesamiento original).

Resultado 3 : mejoré aún más el algoritmo del resultado 1 al usar distancias cuadradas en lugar de distancias reales y, por lo tanto, tomar una operación de raíz cuadrada computacionalmente costosa. Esto solo aumenta ligeramente el rendimiento (2400%). (Nota: también pruebo tablas hash para matrices preprocesadas para aproximaciones de raíces cuadradas con un resultado similar pero ligeramente peor)

Resultado 4 : compruebo además mover / colisionar los rectángulos; sin embargo, esto no cambia los resultados básicos (como se esperaba) ya que la verificación lógica sigue siendo esencialmente la misma.

Resultado 5 : Varío el número de rectángulos y encuentro que el algoritmo se vuelve aún más eficiente cuanto menos concurrido esté el espacio (no se muestra en la demostración). El resultado también es algo esperado, ya que la probabilidad disminuye para que aparezca un punto dentro de un espacio pequeño entre un círculo y los límites del objeto. En el otro extremo, trato de aumentar el número de rectángulos también 100 dentro del mismo pequeño espacio confinado Y variarlos dinámicamente en tamaño en el tiempo de ejecución dentro del bucle (sin (iterador)). Esto todavía funciona extremadamente bien con un aumento en el rendimiento del 570% (o 15% del tiempo de bucle original).

Resultado 6 : pruebo algoritmos alternativos sugeridos aquí y encuentro una diferencia muy leve pero no significativa en el rendimiento (2%). El algoritmo IsLeft, interesante y más simple, funciona muy bien con un aumento del rendimiento del 17% (85% del tiempo de cálculo original), pero ni mucho menos la eficiencia de un algoritmo de verificación negativa rápida.

Mi punto es considerar primero el diseño eficiente y la lógica del juego, especialmente cuando se trata de límites y eventos de colisión. El algoritmo actual de los OP ya es bastante eficiente y una optimización adicional no es tan crítica como la optimización del concepto subyacente en sí. Además, es bueno comunicar el alcance y el propósito del juego, ya que la eficiencia de un algoritmo depende de manera crítica de ellos.

Sugiero que siempre intente comparar cualquier algoritmo complejo durante la etapa de diseño del juego, ya que simplemente mirar el código simple puede no revelar la verdad sobre el rendimiento real en tiempo de ejecución. El algoritmo sugerido puede no ser necesario aquí, si, por ejemplo, se desea simplemente probar si el cursor del mouse se encuentra dentro de un rectángulo o no, o cuando la mayoría de los objetos ya se están tocando. Si la mayoría de los puntos de verificación están dentro del rectángulo, el algoritmo será menos eficiente. (Sin embargo, entonces sería posible establecer un límite de 'círculo interno' como una verificación negativa secundaria). Las verificaciones de límite de círculo / esfera son muy útiles para cualquier detección de colisión decente de una gran cantidad de objetos que naturalmente tienen algo de espacio entre ellos. .

Rec Points  Iter    OFF     ON     ON_Stack     ON_SqrDist  Ileft Algorithm (Wondra)
            (ms)    (ms)    (ms)    (ms)        (ms)        (ms)
20  10      200     0.29    0.02    0.04        0.02        0.17
20  100     2000    2.23    0.10    0.20        0.09        1.69
20  1000    20000   24.48   1.25    1.99        1.05        16.95
20  10000   200000  243.85  12.54   19.61       10.85       160.58
Majte
fuente
Aunque me gustó el enfoque inusual y me encantó la referencia de Da Vinci, no creo que tratar con círculos, y mucho menos con el radio, sea tan eficiente. Además, esa solución solo es razonable si todos los rectángulos son fijos y conocidos de antemano
Louis15
La posición del rectángulo no necesita ser reparada. Usa coordenadas relativas. Piénsalo también así. Ese radio sigue siendo el mismo, sin importar la rotación.
Majte
Esta es una respuesta genial; mejor aún porque no lo había pensado. Es posible que desee tener en cuenta que es suficiente usar las distancias al cuadrado en lugar de las distancias reales, ahorrando la necesidad de calcular una raíz cuadrada.
Pieter Geerkens
¡Algoritmo interesante para pruebas rápidas positivas / negativas! El problema podría ser la memoria extra para guardar círculos de límite preprocesados ​​(y anchos), podría ser una buena heurística, pero también tenga en cuenta que tiene un uso limitado, principalmente para casos en los que la memoria no importa mucho (rectángulos de tamaño estático en objetos más grandes = objetos de juegos de sprites) y tener tiempo para preprocesar.
wondra
Prueba de referencia editada + agregada.
Majte
2

La definición de un rectángulo con 4 puntos permite hacer un trapecio. Sin embargo, si lo definiría por x, y, ancho, alto y una rotación alrededor de su centro, simplemente podría rotar el punto que está verificando mediante la rotación inversa de su rectángulo (alrededor del mismo origen) y luego verificar si es en el rectángulo original

Peethor
fuente
Hmm, gracias por la sugerencia, pero girar y obtener la rotación inversa no parece tan eficiente. De hecho, será apenas tan eficiente como mi solución, sin mencionar a wondra
Louis15
Podrías notar que rotar un punto 3D con una matriz es 6 multiplicaciones y 3 sumas, y una llamada a la función. La solución de @wondra es, en el mejor de los casos, equivalente, pero mucho menos clara en su intención; y más susceptible a errores de mantenimiento al violar DRY
Pieter Geerkens
@Pieter Geerkens afirmación cruzada, ¿cómo alguna de mis soluciones viola DRY (y DRY es uno de los principios clave de programación? Nunca he oído hablar de él hasta ahora)? Y lo más importante, ¿qué errores tienen esas soluciones? Siempre listo para aprender.
wondra
@wondra: DRY = No te repitas. Su fragmento de código sugiere codificar los detalles de una matriz mediante la multiplicación de vectores en todas partes donde aparece la funcionalidad en el código en lugar de invocar un método estándar de aplicación de matriz a Vector.
Pieter Geerkens
@PieterGeerkens, por supuesto, sugiere solo una parte: 1) no tiene una matriz explícitamente (la asignación de una nueva matriz para cada consulta afectaría mucho el rendimiento) 2) Solo uso un caso específico de multiplicación, optimizado para este caso, eliminando la hinchazón de genéricos uno. Es una operación de bajo nivel y debe permanecer encapsulada para evitar un comportamiento inesperado.
wondra
1

No tuve tiempo para comparar esto, pero mi sugerencia sería almacenar la matriz de transformación que transforma el rectángulo en el cuadrado alineado del eje en el rango x e y de 0 a 1. En otras palabras, almacenar la matriz que transforma una esquina del rectángulo en (0,0) y la opuesta en (1,1).

Por supuesto, esto sería más costoso si el rectángulo se mueve mucho y la colisión se revisa con bastante poca frecuencia, pero si hay muchas más comprobaciones que actualizaciones del rectángulo, al menos sería más rápido que el enfoque original de probar contra dos triángulos, ya que los seis productos de punto serían reemplazados por una multiplicación de matriz.

Pero, como siempre, la velocidad de este algoritmo depende en gran medida del tipo de comprobaciones que se espera realizar. Si la mayoría de los puntos ni siquiera están cerca del rectángulo, realizar una simple verificación de distancia (p. Ej. (Point.x - firstCorner.x)> aLargeDistance) podría resultar en una gran aceleración, mientras que incluso podría ralentizar las cosas si casi todos Los puntos están dentro del rectángulo.

EDITAR: así es como se vería mi clase Rectangle:

class Rectangle
{
public:
    Matrix3x3 _transform;

    Rectangle()
    {}

    void setCorners(Vector2 p_a, Vector2 p_b, Vector2 p_c)
    {
        // create a matrix from the two edges of the rectangle
        Vector2 edgeX = p_b - p_a;
        Vector2 edgeY = p_c - p_a;

        // and then create the inverse of that matrix because we want to 
        // transform points from world coordinates into "rectangle coordinates".
        float scaling = 1/(edgeX._x*edgeY._y - edgeY._x*edgeX._y);

        _transform._columns[0]._x = scaling * edgeY._y;
        _transform._columns[0]._y = - scaling * edgeX._y;
        _transform._columns[1]._x = - scaling * edgeY._x;
        _transform._columns[1]._y = scaling * edgeX._x;

        // the third column is the translation, which also has to be transformed into "rectangle space"
        _transform._columns[2]._x = -p_a._x * _transform._columns[0]._x - p_a._y * _transform._columns[1]._x;
        _transform._columns[2]._y = -p_a._x * _transform._columns[0]._y - p_a._y * _transform._columns[1]._y;
    }

    bool isInside(Vector2 p_point)
    {
        Vector2 test = _transform.transform(p_point);
        return  (test._x>=0)
                && (test._x<=1)
                && (test._y>=0)
                && (test._y<=1);
    }
};

Esta es la lista completa de mi punto de referencia:

#include <cstdlib>
#include <math.h>
#include <iostream>

#include <sys/time.h>

using namespace std;

class Vector2
{
public:
    float _x;
    float _y;

    Vector2()
    :_x(0)
    ,_y(0)
    {}

    Vector2(float p_x, float p_y)
        : _x (p_x)
        , _y (p_y)
        {}

    Vector2 operator-(const Vector2& p_other) const
    {
        return Vector2(_x-p_other._x, _y-p_other._y);
    }

    Vector2 operator+(const Vector2& p_other) const
    {
        return Vector2(_x+p_other._x, _y+p_other._y);
    }

    Vector2 operator*(float p_factor) const
    {
        return Vector2(_x*p_factor, _y*p_factor);
    }

    static float Dot(Vector2 p_a, Vector2 p_b)
    {
        return (p_a._x*p_b._x + p_a._y*p_b._y);
    }
};

bool PointInTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
{
 // Compute vectors        
 Vector2 v0 = C - A;
 Vector2 v1 = B - A;
 Vector2 v2 = P - A;

 // Compute dot products
 float dot00 = Vector2::Dot(v0, v0);
 float dot01 = Vector2::Dot(v0, v1);
 float dot02 = Vector2::Dot(v0, v2);
 float dot11 = Vector2::Dot(v1, v1);
 float dot12 = Vector2::Dot(v1, v2);

 // Compute barycentric coordinates
 float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
 float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
 float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

 // Check if point is in triangle
 if(u >= 0 && v >= 0 && (u + v) < 1)
    { return true; } else { return false; }
}


bool PointInRectangle(Vector2 X, Vector2 Y, Vector2 Z, Vector2 W, Vector2 P)
{
 if(PointInTriangle(X,Y,Z,P)) return true;
 if(PointInTriangle(X,Z,W,P)) return true;
 return false;
}

class Matrix3x3
{
public:
    Vector2 _columns[3];

    Vector2 transform(Vector2 p_in)
    {
        return _columns[0] * p_in._x + _columns[1] * p_in._y + _columns[2];
    }
};

class Rectangle
{
public:
    Matrix3x3 _transform;

    Rectangle()
    {}

    void setCorners(Vector2 p_a, Vector2 p_b, Vector2 p_c)
    {
        // create a matrix from the two edges of the rectangle
        Vector2 edgeX = p_b - p_a;
        Vector2 edgeY = p_c - p_a;

        // and then create the inverse of that matrix because we want to 
        // transform points from world coordinates into "rectangle coordinates".
        float scaling = 1/(edgeX._x*edgeY._y - edgeY._x*edgeX._y);

        _transform._columns[0]._x = scaling * edgeY._y;
        _transform._columns[0]._y = - scaling * edgeX._y;
        _transform._columns[1]._x = - scaling * edgeY._x;
        _transform._columns[1]._y = scaling * edgeX._x;

        // the third column is the translation, which also has to be transformed into "rectangle space"
        _transform._columns[2]._x = -p_a._x * _transform._columns[0]._x - p_a._y * _transform._columns[1]._x;
        _transform._columns[2]._y = -p_a._x * _transform._columns[0]._y - p_a._y * _transform._columns[1]._y;
    }

    bool isInside(Vector2 p_point)
    {
        Vector2 test = _transform.transform(p_point);
        return  (test._x>=0)
                && (test._x<=1)
                && (test._y>=0)
                && (test._y<=1);
    }
};

void runTest(float& outA, float& outB)
{
    Rectangle r;
    r.setCorners(Vector2(0,0.5), Vector2(0.5,1), Vector2(0.5,0));

    int numTests = 10000;

    Vector2 points[numTests];

    Vector2 cornerA[numTests];
    Vector2 cornerB[numTests];
    Vector2 cornerC[numTests];
    Vector2 cornerD[numTests];

    bool results[numTests];
    bool resultsB[numTests];

    for (int i=0; i<numTests; ++i)
    {
        points[i]._x = rand() / ((float)RAND_MAX);
        points[i]._y = rand() / ((float)RAND_MAX);

        cornerA[i]._x = rand() / ((float)RAND_MAX);
        cornerA[i]._y = rand() / ((float)RAND_MAX);

        Vector2 edgeA;
        edgeA._x = rand() / ((float)RAND_MAX);
        edgeA._y = rand() / ((float)RAND_MAX);

        Vector2 edgeB;
        edgeB._x = rand() / ((float)RAND_MAX);
        edgeB._y = rand() / ((float)RAND_MAX);

        cornerB[i] = cornerA[i] + edgeA;
        cornerC[i] = cornerA[i] + edgeB;
        cornerD[i] = cornerA[i] + edgeA + edgeB;
    }

    struct timeval start, end;

    gettimeofday(&start, NULL);
    for (int i=0; i<numTests; ++i)
    {
        r.setCorners(cornerA[i], cornerB[i], cornerC[i]);
        results[i] = r.isInside(points[i]);
    }
    gettimeofday(&end, NULL);
    float elapsed = (end.tv_sec - start.tv_sec)*1000;
    elapsed += (end.tv_usec - start.tv_usec)*0.001;
    outA += elapsed;

    gettimeofday(&start, NULL);
    for (int i=0; i<numTests; ++i)
    {
        resultsB[i] = PointInRectangle(cornerA[i], cornerB[i], cornerC[i], cornerD[i], points[i]);
    }
    gettimeofday(&end, NULL);
    elapsed = (end.tv_sec - start.tv_sec)*1000;
    elapsed += (end.tv_usec - start.tv_usec)*0.001;
    outB += elapsed;
}

/*
 * 
 */
int main(int argc, char** argv) 
{
    float a = 0;
    float b = 0;

    for (int i=0; i<5000; i++)
    {
        runTest(a, b);
    }

    std::cout << "Result: " << a << " / " << b << std::endl;

    return 0;
}

El código ciertamente no es hermoso, pero no veo inmediatamente ningún error importante. Con ese código obtengo resultados que indican que mi solución es aproximadamente el doble de rápida si el rectángulo se mueve entre cada verificación. Si no se mueve, entonces mi código parece ser más de cinco veces más rápido.

Si sabe cómo se usará el código, incluso puede acelerarlo un poco más separando la transformación y los controles en las dos dimensiones. Por ejemplo, en un juego de carreras, probablemente sería más rápido verificar primero la coordenada que apunta en la dirección de conducción, porque muchos obstáculos estarán delante o detrás del automóvil, pero casi ninguno estará a la derecha o a la izquierda.

Lars Kokemohr
fuente
Interesante, pero no olvides que también debes aplicar la rotación de la matriz en los puntos. Tengo una operación de podredumbre matricial en mi motor de juego y puedo comparar tu algoritmo más adelante. Con respecto a tu último comentario. Entonces puede tener un 'círculo interno' definido también y hacer una doble verificación negativa si el punto se encuentra fuera del círculo interno y dentro del círculo externo como se describió anteriormente.
Majte
Sí, eso ayudaría si espera que la mayoría de los puntos estén cerca del centro del triángulo. Estaba imaginando una situación como una pista de carreras rectangular en la que, por ejemplo, define una ruta rectangular mediante el uso de un rectángulo exterior en el que el personaje debe permanecer dentro y un rectángulo interior más pequeño en el que debe mantenerse. En ese caso, cada verificación estaría cerca del borde del rectángulo y esas verificaciones circulares probablemente solo empeorarían el rendimiento. De acuerdo, ese es un ejemplo construido, pero yo diría que es algo que realmente podría suceder.
Lars Kokemohr
Cosas como esas pueden suceder, sí. Me pregunto cuál es el punto óptimo para oponerse al algoritmo. Al final se reduce a su propósito. Si tiene tiempo, ¿puede publicar su código, utilizando la publicación de OP y puedo comparar su algoritmo? Veamos si tu intuición es correcta. Tengo curiosidad sobre el rendimiento de su idea contra el algoritmo IsLeft.
Majte