Como verifico com eficiência se um ponto está dentro de um retângulo girado?

11

Parte para fins de otimização, parte para fins de aprendizado, ousarei perguntar: Como posso verificar com mais eficiência se um ponto 2D Pestá dentro de um retângulo girado em 2D XYZW, usando C # ou C ++?

Atualmente, o que estou fazendo é usar o algoritmo "ponto no triângulo" encontrado no livro Detecção de colisão em tempo real e executá-lo duas vezes (para os dois triângulos que compõem o retângulo, digamos XYZ e 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;
}

No entanto, tenho a sensação de que pode haver uma maneira mais limpa e rápida. Especificamente, para reduzir o número de operações matemáticas.

Louis15
fonte
Você tem muitos pontos ou muitos retângulos? Essa é a primeira pergunta que você deve se perguntar antes de tentar otimizar uma tarefa tão pequena.
Sam Hocevar
Bom ponto. Vou ter um número muito alto de pontos, mas ainda mais retângulos para verificar.
Louis15
Pergunta relacionada sobre como encontrar a distância de um ponto em um retângulo girado . Este é um caso degenerado disso (verificando apenas quando a distância é 0). Obviamente, haverá otimizações que se aplicam aqui que não existem.
Anko 24/10
Você já pensou em girar o ponto no quadro de referência do retângulo?
Richard Tingle
@RichardTingle Na verdade eu não fiz isso no começo. Mais tarde eu fiz, porque acho que isso se relaciona com uma das respostas dadas abaixo. Mas apenas para esclarecer: no que você está sugerindo, depois de girar o ponto para o quadro de referência dos retângulos, deve-se verificar a inclusão apenas por comparações lógicas entre max.x, min.x, etc.?
Louis15

Respostas:

2

Uma otimização fácil e direta seria alterar a condição final em 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; }
  }
}

o código PointInRectanglejá estava praticamente , a condição (u + v) < 1estava lá para verificar se não está no "segundo" triângulo do retângulo.

Como alternativa, você também pode fazer uma isLeft (primeiro exemplo de código na página, também explicado em detalhes) quatro vezes e verificar se todos retornam resultados com o mesmo sinal (que depende de se os pontos foram dados no sentido horário ou anti-horário) para o ponto para estar dentro. Isso funciona para qualquer outro polígono convexo também.

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
fonte
Soberbo. Não sei se gosto mais da sua sugestão, que é realmente mais rápida e muito mais elegante que a minha, ou se gosto mais do que você notou que meu código PointInTri poderia facilmente se tornar um PointInRec! Graças
Louis15
+1 para o isLeftmétodo. Não requer funções trigonométricas (como Vector2.Dotfaz), o que acelera bastante as coisas.
Anko 24/10
Aliás, não foi possível ajustar o código (não testou; não há como neste computador), incluindo o isLeft diretamente na função principal e substituindo os operadores "&&" por "||" através da 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
11
@ Louis15 Eu não acho que você precisa - ambos && e || interromperá a execução de outras instruções se um negativo / positivo for encontrado (ou houve outro motivo?). Declarar isLeftcomo inline o compilador fará algo semelhante para você (e provavelmente melhor do que você poderia, porque os engenheiros que escreviam o compilador conheciam melhor as CPUs, escolhendo qualquer opção mais rápida), tornando seu código mais legível com o mesmo ou melhor efeito.
Wondra
8

Edit: O comentário dos OPs tem sido cético sobre a eficiência da verificação do limite circular negativo sugerido para melhorar o algoritmo, a fim de verificar se um ponto 2D arbitrário se encontra dentro de um retângulo girado e / ou em movimento. Brincando um pouco no meu mecanismo de jogo em 2D (OpenGL / C ++), suplemento minha resposta fornecendo uma referência de desempenho do meu algoritmo com relação aos algoritmos (e variações) atuais dos pontos de verificação do retângulo no OP (e variações).

Originalmente, sugeri deixar o algoritmo no lugar (como é quase ideal), mas simplificá-lo através da mera lógica do jogo: (1) usando um círculo pré-processado em torno do retângulo original; (2) faça uma verificação de distância e se o ponto estiver dentro do círculo especificado; (3) use os OPs ou qualquer outro algoritmo direto (eu recomendo o algoritmo isLeft, conforme fornecido em outra resposta). A lógica por trás da minha sugestão é que verificar se um ponto está dentro de um círculo é consideravelmente mais eficiente do que uma verificação de limites de um retângulo girado ou qualquer outro polígono.

Meu cenário inicial para um teste de benchmark é executar um grande número de pontos que aparecem e desaparecem (cuja posição muda em cada ciclo do jogo) em um espaço restrito que será preenchido com cerca de 20 quadrados rotativos / móveis. Publiquei um vídeo ( link do youtube ) para fins ilustrativos. Observe os parâmetros: número de pontos que aparecem aleatoriamente, número ou retângulos. Vou comparar com os seguintes parâmetros:

OFF : Algoritmo simples, conforme fornecido pelo OP, sem verificações negativas nos limites do círculo

ATIVADO : usando círculos por processo (limite) em volta dos retângulos como uma primeira verificação de exclusão

ON + Stack : Criando limites de círculo em tempo de execução dentro do loop na pilha

ON + Distância quadrada : Usar distâncias quadradas como uma otimização adicional para evitar o algoritmo de raiz quadrada mais caro (Pieter Geerkens).

Aqui está um resumo dos vários desempenhos de diferentes algoritmos, mostrando o tempo necessário para percorrer o loop.

insira a descrição da imagem aqui

O eixo x mostra uma complexidade aumentada adicionando mais pontos (e diminuindo a velocidade do loop). (Por exemplo, em 1000 pontos de verificação aleatória em um espaço confidencial com 20 retângulos, o loop itera e chama o algoritmo 20000 vezes.) O eixo y mostra o tempo necessário (ms) para concluir o loop inteiro usando uma alta resolução temporizador de desempenho. Mais de 20 ms seriam problemáticos para um jogo decente, pois não tiraria proveito dos altos fps para interpolar uma animação suave e o jogo pode parecer assim 'áspero' às vezes.

Resultado 1 : um algoritmo de limite circular pré-processado com uma verificação negativa rápida dentro do loop melhora o desempenho em 1900% em comparação com o algoritmo regular (5% do tempo original do loop sem uma verificação). O resultado é aproximadamente proporcional ao número de iterações dentro de um loop, portanto, não importa se verificamos 10 ou 10000 pontos que aparecem aleatoriamente. Assim, nesta ilustração, é possível aumentar o número de objetos com segurança para 10k sem sentir uma perda de desempenho.

Resultado 2 : Foi sugerido por um comentário anterior que o algoritmo pode ser mais rápido, mas com muita memória. No entanto, observe que o armazenamento de um flutuador para o tamanho do círculo pré-processado leva apenas 4 bytes. Isso não deve representar problema real, a menos que o OP planeje executar simultaneamente mais de 100000 objetos. Uma abordagem alternativa e eficiente em termos de memória é calcular o tamanho máximo do círculo na pilha dentro do loop e deixá-lo fora do escopo a cada iteração e, portanto, praticamente não usa memória para um preço desconhecido da velocidade. De fato, o resultado mostra que essa abordagem é realmente mais lenta do que usar um tamanho de círculo pré-processado, mas ainda mostra uma melhoria considerável no desempenho em torno de 1150% (ou seja, 8% do tempo de processamento original).

Resultado 3 : eu melhoro ainda mais o algoritmo do resultado 1 usando distâncias quadradas em vez de distâncias reais e, assim, executando uma operação de raiz quadrada computacionalmente cara. Isso apenas aumenta levemente o desempenho (2400%). (Nota: eu também tento tabelas de hash para matrizes pré-processadas para aproximações de raízes quadradas com um resultado semelhante, mas um pouco pior)

Resultado 4 : Verifico mais a movimentação / colisão dos retângulos; no entanto, isso não altera os resultados básicos (conforme o esperado), pois a verificação lógica permanece essencialmente a mesma.

Resultado 5 : eu vario o número de retângulos e acho que o algoritmo se torna ainda mais eficiente quanto menos ocupado o espaço é preenchido (não mostrado na demonstração). O resultado também é algo esperado, pois a probabilidade diminui para que um ponto apareça dentro de um espaço minúsculo entre um círculo e os limites do objeto. Por outro lado, tento aumentar demais o número de retângulos em 100 dentro do mesmo espaço minúsculo confinado E variar dinamicamente em tamanho no tempo de execução no loop (sin (iterador)). Isso ainda apresenta um desempenho extremamente bom, com aumento no desempenho em 570% (ou 15% do tempo do loop original).

Resultado 6 : testei algoritmos alternativos sugeridos aqui e encontro uma diferença muito pequena, mas não significativa, no desempenho (2%). O interessante e mais simples algoritmo IsLeft funciona muito bem com um aumento de desempenho de 17% (85% do tempo de cálculo original), mas nem de longe com a eficiência de um algoritmo rápido de verificação negativa.

Meu objetivo é considerar primeiro o design enxuto e a lógica do jogo, especialmente ao lidar com limites e eventos de colisão. O algoritmo atual dos OPs já é bastante eficiente e uma otimização adicional não é tão crítica quanto otimizar o próprio conceito subjacente. Além disso, é bom comunicar o escopo e o objetivo do jogo, pois a eficiência de um algoritmo depende muito deles.

Sugiro sempre tentar fazer benchmark de qualquer algoritmo complexo durante o estágio de design do jogo, pois apenas olhar o código simples pode não revelar a verdade sobre o desempenho real do tempo de execução. O algoritmo sugerido pode não ser aqui necessário, se, por exemplo, se desejar apenas testar se o cursor do mouse está dentro de um retângulo ou não, ou quando a maioria dos objetos já está se tocando. Se a maioria das verificações de pontos estiver dentro do retângulo, o algoritmo será menos eficiente. (No entanto, seria possível estabelecer um limite de 'círculo interno' como uma verificação negativa secundária.) As verificações de limite de círculo / esfera são muito úteis para qualquer detecção de colisão decente de um grande número de objetos que naturalmente possuem algum espaço entre eles. .

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
fonte
Embora gostei da abordagem incomum e amei a referência de Da Vinci, não acho que lidar com círculos, muito menos com o raio, seria tão eficiente. Além disso, essa solução só é razoável se todos os retângulos são fixos e conhecidos de antemão
Louis15
A posição do retângulo não precisa ser corrigida. Use coordenadas relativas. Pense nisso também assim. Esse raio permanece o mesmo, independentemente da rotação.
Majte 24/10/2015
Esta é uma ótima resposta; melhor ainda, porque eu não tinha pensado nisso. Você pode observar que é suficiente usar as distâncias quadradas no lugar das distâncias reais, economizando a necessidade de calcular sempre uma raiz quadrada.
Pieter Geerkens
Algoritmo interessante para testes positivos / negativos rápidos! O problema pode ser memória extra para salvar círculos delimitadores (e larguras) pré-processados, pode ser uma boa heurística, mas também tem um uso limitado - principalmente nos casos em que a memória não importa muito (retângulos de tamanho estático em objetos maiores = objetos de jogos de sprites) e ter tempo para pré-processar.
Wondra
Editado + adicionado teste de benchmark.
Majte
2

Definir um retângulo com 4 pontos torna possível fazer um trapézio. Se, no entanto, você o definiria por x, y, largura, altura e uma rotação em torno do meio, basta girar o ponto que está verificando pela rotação inversa do seu retângulo (em torno da mesma origem) e depois verificar se está no retângulo original.

Peethor
fonte
Hmm, obrigado pela sugestão, mas girar e obter a rotação inversa não parece tão eficiente. Na verdade, dificilmente será tão eficiente quanto a minha solução - para não mencionar Wondra de
Louis15
Você pode observar que girar um ponto 3D com uma matriz é de 6 multiplicações e 3 adições e uma chamada de função. A solução da @ wondra é, na melhor das hipóteses, equivalente, mas muito menos clara na intenção; e mais suscetível a erros de manutenção através de violar DRY
Pieter Geerkens
@Pieter Geerkens afirmação interminável, como algumas de minhas soluções violam o DRY (e o DRY é um dos principais princípios de programação? Nunca ouvi falar dele até agora)? E o mais importante, que erros essas soluções têm? Sempre pronto para aprender.
Wondra
@wondra: DRY = Não se repita. Seu snippet de código sugere a codificação dos detalhes de uma matriz pela multiplicação de vetores em todos os lugares em que a funcionalidade aparecer no código, em vez de chamar um método padrão de aplicativo de matriz para vetor.
Pieter Geerkens
@PieterGeerkens, é claro, sugere apenas parte dela - 1) você não tem matriz explicitamente (a alocação de nova matriz para cada consulta prejudicaria o desempenho) 2) Eu só uso casos específicos de multiplicação, otimizados para esse caso, descartando o inchaço dos genéricos 1. É uma operação de baixo nível e deve permanecer encapsulado para evitar comportamentos inesperados.
Wondra
1

Não tive tempo de avaliar isso, mas minha sugestão seria armazenar a matriz de transformação que transforma o retângulo no quadrado alinhado ao eixo no intervalo x e y de 0 a 1. Em outras palavras, armazene a matriz que transforma um canto do retângulo em (0,0) e o oposto em (1,1).

Obviamente, isso seria mais caro se o retângulo for movido muito e a colisão for verificada raramente, mas se houver muito mais verificações do que atualizações no retângulo, isso seria pelo menos mais rápido que a abordagem original de testar contra dois triângulos, como os produtos de seis pontos seriam substituídos por uma multiplicação de matrizes.

Mas como sempre, a velocidade desse algoritmo depende muito do tipo de verificação que você espera que seja realizada. Se a maioria dos pontos não estiver nem perto do retângulo, executando uma verificação simples da distância (por exemplo, (point.x - firstCorner.x)> aLargeDistance) pode resultar em uma grande aceleração, enquanto pode até diminuir a velocidade, se quase todos os pontos estão dentro do retângulo.

EDIT: É assim que minha classe Rectangle seria:

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 é a lista completa do meu benchmark:

#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;
}

O código certamente não é bonito, mas não vejo imediatamente nenhum erro grave. Com esse código, obtenho resultados que indicam que minha solução é duas vezes mais rápida se o retângulo for movido entre cada verificação. Se não se mover, meu código parece ser mais de cinco vezes mais rápido.

Se você souber como o código será usado, poderá até acelerar um pouco mais, separando a transformação e as verificações nas duas dimensões. Por exemplo, em um jogo de corrida, provavelmente seria mais rápido verificar primeiro as coordenadas que apontam na direção de direção, porque muitos obstáculos estarão na frente ou atrás do carro, mas dificilmente algum estará à direita ou à esquerda.

Lars Kokemohr
fonte
Interessante, mas não esqueça que você também precisa aplicar a rotação da matriz nos pontos. Eu tenho uma operação de podridão de matriz no meu mecanismo de jogo e posso comparar seu algoritmo posteriormente. Com relação ao seu último comentário. Então você também pode definir um 'círculo interno' e fazer uma verificação dupla negativa se o ponto estiver fora do círculo interno e dentro do círculo externo, conforme descrito acima.
Majte 26/10/2015
Sim, isso ajudaria se você esperasse que a maioria dos pontos ficasse perto do meio do triângulo. Eu estava imaginando uma situação como uma pista de corrida retangular em que você define um caminho retangular usando um retângulo externo no qual o personagem precisa ficar dentro e um retângulo interno menor do qual ele precisa ficar fora. Nesse caso, todas as verificações estariam próximas à borda do retângulo e essas verificações de círculo provavelmente apenas piorariam o desempenho. É verdade que esse é um exemplo construído, mas eu diria que é algo que realmente pode acontecer.
Lars Kokemohr
Coisas assim podem acontecer, sim. Gostaria de saber qual é o ponto ideal para se voltar contra o algoritmo. No final, tudo se resume ao seu objetivo. Se você tiver tempo, poderá postar seu código, usando a postagem dos OPs e eu posso comparar seu algoritmo? Vamos ver se sua intuição está certa. Estou curioso sobre o desempenho da sua ideia contra o algoritmo IsLeft.
Majte 27/10/2015