Como determinar se um ponto está em um triângulo 2D? [fechadas]

258

Existe uma maneira fácil de determinar se um ponto está dentro de um triângulo? É 2D, não 3D.

ET 0.618
fonte
15
Eu escrevi um artigo completo sobre o ponto no teste do triângulo. Ele mostra os métodos baseados em produtos barricêntricos, paramétricos e de pontos. Em seguida, lida com o problema de precisão que ocorre quando um ponto está exatamente em uma extremidade (com exemplos). Finalmente, expõe um novo método completo com base na distância ponto a borda. totologic.blogspot.fr/2014/01/… Aproveite!
Logic
1
Vale ressaltar que quaisquer métodos discutidos aqui também são válidos no espaço 3D. Eles só precisam ser precedidos por uma transformação de coordenadas (e uma projeção apropriada do ponto no plano do triângulo). Um triângulo é um objeto bidimensional.
andreasdr
Para uma solução independente da ordem do enrolamento. Aqui está um violino de trabalho: jsfiddle.net/ibowankenobi/oex3pzq2
ibrahim tanyalcin
2
Estou votando para encerrar esta pergunta porque é mais sobre matemática do que sobre programação e é baseada em opiniões (o que é "fácil" para você?).
TylerH

Respostas:

264

Em geral, o algoritmo mais simples (e bastante ideal) é verificar em que lado do semiplano criado pelas arestas está o ponto.

Aqui estão algumas informações de alta qualidade neste tópico no GameDev , incluindo problemas de desempenho.

E aqui está um código para você começar:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}
Kornel Kisielewicz
fonte
12
É comumente usado em 2D. As coordenadas baricêntricas tendem a confundir as pessoas. Além disso, dados os cooridados do triângulo e o ponto cordado, não tenho certeza sobre a eficiência do uso de baricêntricos.
Kornel Kisielewicz
7
@Kornel A versão baricêntrica também é mais eficiente em 2D. Sua solução também tem o problema de informar um resultado diferente para pontos exatamente nas arestas do triângulo, dependendo de o triângulo estar especificado no sentido horário ou anti-horário.
Andreas Brinck
9
Para meus propósitos (a razão pela qual encontrei este site), a resposta original proposta por Kornel Kisielewicz é muito mais eficiente. Estou trabalhando com uma tela LCD com coordenadas de tamanho BYTE e um microprocessador muito típico, onde a multiplicação de números inteiros é uma instrução muito rápida e a divisão é muito, muito, mais lenta. Problemas numéricos também são muito menores, devido a nenhuma divisão! todos os cálculos são exatos. Obrigado, Rick
4
Portanto, a função sign () indica qual lado do semiplano (formado pela linha entre p2 e p3) p1 é?
David Doria
1
Observe que, se você assumir alguma ordem dos vértices (digamos no sentido anti-horário), não precisará calcular todos esses determinantes o tempo todo. De fato, na melhor das hipóteses, 1 determinante é suficiente para descobrir que o ponto não está dentro do triângulo.
Thash 9/09/16
176

Resolva o seguinte sistema de equações:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

O ponto pestá dentro do triângulo se 0 <= s <= 1e 0 <= t <= 1e s + t <= 1.

s, te 1 - s - tsão chamadas de coordenadas barricêntricas do ponto p.

Andreas Brinck
fonte
1
Isso é mais rápido que a verificação no meio plano, mas talvez seja um pouco mais difícil de entender se você é novo nas coordenadas baricêntricas.
precisa saber é o seguinte
8
Com saídas triviais (não implementadas) no método de Kornel, as dele podem ser muito mais eficientes que as suas. Se você realmente tentar calcular se você saberá o que quero dizer.
85
Eu queria testar esta por isso fiz um jsFiddle, contando com @andreasdr solução e coproc comentário: jsfiddle.net/PerroAZUL/zdaY8/1
urraka
5
Otimização: s + t <= 1implica s <= 1e t <= 1se s >= 0e t >= 0.
Thomas Eding
7
O artigo totologic.blogspot.fr/2014/01/... proposto por @Logic pós ajudou-me a compreender melhor esta solução
Flayn
112

Concordo com Andreas Brinck , as coordenadas baricêntricas são muito convenientes para esta tarefa. Observe que não há necessidade de resolver um sistema de equações sempre: basta avaliar a solução analítica. Usando a notação de Andreas , a solução é:

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

onde Areaé a área (assinada) do triângulo:

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

Apenas avalie s, te 1-s-t. O ponto pestá dentro do triângulo se e somente se todos forem positivos.

EDIT: Observe que a expressão acima para a área pressupõe que a numeração dos nós do triângulo esteja no sentido anti-horário. Se a numeração for no sentido horário, essa expressão retornará uma área negativa (mas com a magnitude correta). O teste em si ( s>0 && t>0 && 1-s-t>0) não depende da direção da numeração, no entanto, uma vez que as expressões acima que são multiplicadas por 1/(2*Area)também mudam de sinal se a orientação do nó do triângulo for alterada.

EDIT 2: Para uma eficiência computacional ainda melhor, consulte o comentário do coproc abaixo (que salienta que, se a orientação dos nós do triângulo (sentido horário ou anti-horário) é conhecida previamente, a divisão 2*Areanas expressões para se tpode ser evitado). Veja também o código jsfiddle de Perro Azul nos comentários na resposta de Andreas Brinck .

andreasdr
fonte
6
Isso é resolver o sistema de equações :)
Andreas Brinck
1
Sim, o que quero dizer é que qualquer crítica ao seu método com base no custo computacional da solução do sistema de equações é infundada, pois isso não precisa ser feito como parte do algoritmo.
andreasdr
13
A eficiência pode ser melhorada não se dividindo 2*Area, ou seja, calculando s´=2*|Area|*se t´=2*|Area|*t(se a orientação dos pontos - horário ou anti-horário - não for conhecida, é Areaclaro que o sinal de deve ser verificado, mas, caso contrário, talvez nem precisa ser calculado), pois para verificar s>0basta verificar s´>0. E, em vez de verificar 1-s-t>0, basta verificar s´+t´<2*|Area|.
Coproc
1
Posso acrescentar que, se p0->p1->p2for cartesiano no sentido anti-horário (que geralmente é no sentido horário nas coordenadas da tela ), o calculado por esse método será positivo. Area
Rhd
1
@ user2600366 Ao viajar ao longo do limite do triângulo na direção p0 -> p1 -> p2 -> p0 e assim por diante, você terá o interior do triângulo sempre à sua direita ou sempre à sua esquerda. No primeiro caso, a numeração é no sentido horário, no último caso, no sentido anti-horário.
precisa saber é o seguinte
47

Escrevi esse código antes de uma tentativa final com o Google e encontrei esta página, então pensei em compartilhá-lo. É basicamente uma versão otimizada da resposta Kisielewicz. Também examinei o método baricêntrico, mas, a julgar pelo artigo da Wikipedia, tenho dificuldade em ver como ele é mais eficiente (acho que há uma equivalência mais profunda). De qualquer forma, esse algoritmo tem a vantagem de não usar divisão; um problema em potencial é o comportamento da detecção de borda, dependendo da orientação.

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x-a.x;
    int as_y = s.y-a.y;

    bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

    if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;

    if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;

    return true;
}

Em palavras, a idéia é a seguinte: os pontos s à esquerda ou à direita das linhas AB e AC? Se for verdade, não pode estar lá dentro. Se falso, é pelo menos dentro dos "cones" que satisfazem a condição. Agora, como sabemos que um ponto dentro de um trigon (triângulo) deve estar do mesmo lado de AB que BC (e também CA), verificamos se eles diferem. Se o fizerem, s não pode estar dentro, senão s deve estar dentro.

Algumas palavras-chave nos cálculos são semiplanos de linha e o determinante (produto cruzado 2x2). Talvez uma maneira mais pedagógica seja provavelmente pensar nisso como um ponto dentro de si, se estiver do mesmo lado (esquerda ou direita) de cada uma das linhas AB, BC e CA. A maneira acima parecia melhor para algumas otimizações.

John Bananas
fonte
2
Este teste é cerca de 140-180% mais rápido que o primeiro fornecido (graças a vocês dois): Executei o código aqui: paste.ubuntu.com/p/k5w7ywH4p8 usando o mecanismo nodejs v8 com otimizações desativadas e obtive os seguintes resultados:: w! Node -p --minimal test1: 114.852ms test2: 64.330ms test1: 115.650ms test2: 63.491ms test1: 117.671ms test2: 65.353ms test1: 119.146ms test2: 63.871ms test1: 118.271ms test1: 118.670ms test2: 63.352ms
surgemcgee
@surgemcgee Por que você o executaria sem otimizações? Isso não é mais afastado da realidade, então?
xuiqzy
@xuiqzy Bem, meu programa contém as duas soluções diferentes. Ainda tenho que administrar o método mais rápido de fazê-lo. Talvez esse comentário deva ser removido e substituído pelos meus trabalhos concluídos sobre isso ..
surgemcgee
33

Versão em C # do método barcentric publicado por andreasdr e Perro Azul. Observe que o cálculo da área pode ser evitado se se ttiver sinais opostos. Eu verifiquei o comportamento correto com um teste de unidade bastante completo.

public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
    var s = p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * p.X + (p0.X - p2.X) * p.Y;
    var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * p.X + (p1.X - p0.X) * p.Y;

    if ((s < 0) != (t < 0))
        return false;

    var A = -p1.Y * p2.X + p0.Y * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y;

    return A < 0 ?
            (s <= 0 && s + t >= A) :
            (s >= 0 && s + t <= A);
}

[ edit ]
aceitou a modificação sugerida pelo @Pierre; Ver comentários

Glenn Slayden
fonte
A solução com a instrução if final funciona para os pontos do triângulo no sentido horário e anti-horário.
precisa
@LukeDupin Não sei se entendi o seu comentário. Esta resposta funciona conforme publicado para qualquer pedido fornecido dos 3 pontos.
Glenn Slayden
12

Versão Java do método barricêntrico:

class Triangle {
    Triangle(double x1, double y1, double x2, double y2, double x3,
            double y3) {
        this.x3 = x3;
        this.y3 = y3;
        y23 = y2 - y3;
        x32 = x3 - x2;
        y31 = y3 - y1;
        x13 = x1 - x3;
        det = y23 * x13 - x32 * y31;
        minD = Math.min(det, 0);
        maxD = Math.max(det, 0);
    }

    boolean contains(double x, double y) {
        double dx = x - x3;
        double dy = y - y3;
        double a = y23 * dx + x32 * dy;
        if (a < minD || a > maxD)
            return false;
        double b = y31 * dx + x13 * dy;
        if (b < minD || b > maxD)
            return false;
        double c = det - a - b;
        if (c < minD || c > maxD)
            return false;
        return true;
    }

    private final double x3, y3;
    private final double y23, x32, y31, x13;
    private final double det, minD, maxD;
}

O código acima funcionará corretamente com números inteiros, assumindo que não haja estouros. Também funcionará com triângulos no sentido horário e anti-horário. Não funcionará com triângulos colineares (mas você pode verificar isso testando det == 0).

A versão baricêntrica é mais rápida se você for testar pontos diferentes com o mesmo triângulo.

A versão baricêntrica não é simétrica nos 3 pontos do triângulo, portanto é provável que seja menos consistente que a versão de meio plano da aresta de Kornel Kisielewicz, devido a erros de arredondamento de ponto flutuante.

Crédito: Eu criei o código acima do artigo da Wikipedia sobre coordenadas baricêntricas.

Adam Gawne-Cain
fonte
Agradável ! Pode até ser aprimorado usar as tuplas Point3f / Point2f do javax.vecmath, para lidar melhor com a entrada de dados.
precisa saber é o seguinte
10

Uma maneira simples é:

encontre os vetores que conectam o ponto a cada um dos três vértices do triângulo e some os ângulos entre esses vetores. Se a soma dos ângulos é 2 * pi, então o ponto está dentro do triângulo.

Dois bons sites que explicam alternativas são:

blackpawn e wolfram

Simon P Stevens
fonte
3
Hum, esse método não é exatamente eficiente, e é muito propenso a erros numéricos ...
kornel kisielewicz
É exatamente o oposto, é muito ineficiente :-) É apenas uma maneira simples, fácil de implementar. Você pode dar um exemplo de erro numérico que isso causaria?
Simon P Stevens
Enquanto para mim isso parece ser a melhor de todas as respostas neste tópico, acho que os pontos nas bordas do triângulo são calculados para serem incluídos no triângulo e você não tem um controle sólido sobre isso.
Redu
verificar se é exatamente 2pi é numericamente impossível, dado o irracional de pi. No entanto, você só precisa verificar se os ângulos somam algo maior que pi.
lonewarrior556
10

Usando a solução analítica para as coordenadas barentêntricas (apontadas por Andreas Brinck ) e:

  • não distribuir a multiplicação pelos termos entre parênteses
  • evitando calcular várias vezes os mesmos termos, armazenando-os
  • reduzindo comparações (como apontado por coproc e Thomas Eding )

Pode-se minimizar o número de operações "caras":

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

O código pode ser colado no jsfiddle do Perro Azul ou tente-o clicando em "Executar trecho de código" abaixo

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    var sign = A < 0 ? -1 : 1;
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
    
    return s > 0 && t > 0 && (s + t) < 2 * A * sign;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Levando a:

  • variável "recalls": 30
  • armazenamento variável: 7
  • adições: 4
  • subtrações: 8
  • multiplicações: 6
  • divisões: nenhuma
  • comparações: 4

Isso se compara muito bem à solução Kornel Kisielewicz (25 recalls, 1 armazenamento, 15 subtrações, 6 multiplicações, 5 comparações) e pode ser ainda melhor se for necessária a detecção no sentido horário / anti-horário (que leva 6 recalls, 1 adição e 2 subtrações , 2 multiplicações e 1 comparação em si, usando o determinante da solução analítica, conforme apontado por rhgb ).

Cédric Dufour
fonte
Ótima solução. Eu acho que é é bastante equivalente a minha última abordagem aqui na MSE: math.stackexchange.com/questions/51326/...
Jack D'Aurizio
Acabei de testar o código como está e ele não funciona para mim (exemplo p -4.69317198, -6.99191951 p0 -7.05846786 0.596718192 p1 -6.8703599 -2.36565161 p2 -4.69317198, -6.99191951)
Giovanni Funchal
@GiovanniFunchal Strange, seu exemplo funciona para mim, tanto no jsfiddle (substitua as definições iniciais de "ponto" e "triângulo") quanto na minha implementação local do Python. Problemas de precisão numérica (tente extrair algumas casas decimais)?
Cédric Dufour
1
Você parece o mais rápido no meu teste: jsfiddle.net/eyal/gxw3632c/27 . A diferença entre todos os métodos é bem pequena, no entanto.
Eyal
Tente triângulo (-1, -1), (1, -1), (0,1) e ponto (0, -1). Retorna false quando deve retornar true porque s (2) + t (2)> d (2). Parece que algo está errado com a matemática nas arestas do triângulo, pois o ponto p está na fronteira entre p0 e p1 e não é uma simples questão de converter um <para um <= ou algo assim.
devnullicus 2/03
5

O que eu faço é pré-calcular as três faces normais,

  • em 3D por produto cruzado do vetor lateral e o vetor normal da face.

  • em 2D simplesmente trocando componentes e negando um,

então dentro / fora para qualquer lado é quando um produto pontual do lado normal e o vértice ao vetor pontual mudam de sinal. Repita para os outros dois (ou mais) lados.

Benefícios:

  • muito é pré-calculado, excelente para testes de múltiplos pontos no mesmo triângulo.

  • rejeição precoce de casos comuns de mais pontos externos do que internos. (também se a distribuição de pontos ponderada para um lado, pode testar esse lado primeiro.)

psiman
fonte
5

Aqui está uma implementação eficiente do Python :

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

e um exemplo de saída:

insira a descrição da imagem aqui

Desenvolvedor
fonte
Não consegui fazer isso funcionar, por exemplo, para o ponto no triângulo [(0,0), (3,0), (3,4)], nem os pontos (1,1) ou (0). , 0) teste positivo. Eu tentei com pontos triangulares no sentido horário e anti-horário.
ThorSummoner
3

Se você está procurando velocidade, aqui está um procedimento que pode ajudá-lo.

Classifique os vértices do triângulo em suas ordenadas. Isso leva no máximo três comparações. Seja Y0, Y1, Y2 os três valores classificados. Ao desenhar três horizontais através deles, você divide o plano em dois semiplanos e duas lajes. Seja Y a ordenada do ponto de consulta.

if Y < Y1
    if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done
    else Y > Y0 -> the point lies in the upper slab
else
    if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done
    else Y < Y2 -> the point lies in the lower slab

Custa mais duas comparações. Como você vê, a rejeição rápida é alcançada para pontos fora da "laje delimitadora".

Opcionalmente, você pode fornecer um teste nas abscissas para rejeição rápida à esquerda e à direita ( X <= X0' or X >= X2'). Isso implementará um teste rápido de caixa delimitadora ao mesmo tempo, mas você também precisará classificar as abscissas.

Eventualmente, você precisará calcular o sinal do ponto especificado em relação aos dois lados do triângulo que delimitam a laje relevante (superior ou inferior). O teste tem a forma:

((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))

A discussão completa das i, j, kcombinações (existem seis delas, com base no resultado do tipo) está fora do escopo desta resposta e "deixada como um exercício para o leitor"; para eficiência, eles devem ser codificados.

Se você acha que essa solução é complexa, observe que ela envolve principalmente comparações simples (algumas das quais podem ser pré-computadas), mais 6 subtrações e 4 multiplicações caso o teste da caixa delimitadora falhe. É difícil superar o último custo, pois, no pior dos casos, você não pode evitar comparar o ponto de teste com dois lados (nenhum método em outras respostas tem um custo menor, alguns pioram, como 15 subtrações e 6 multiplicações, às vezes divisões).

ATUALIZAÇÃO: Mais rápido com uma transformação de cisalhamento

Como explicado acima, você pode localizar rapidamente o ponto dentro de uma das quatro bandas horizontais delimitadas pelas três ordenadas de vértices, usando duas comparações.

Opcionalmente, você pode executar um ou dois testes X extras para verificar a falta de espaço na caixa delimitadora (linhas pontilhadas).

Em seguida, considere a transformação "cisalhamento" fornecida por X'= X - m Y, Y' = Y, onde mé a inclinação DX/DYda aresta mais alta. Essa transformação tornará esse lado do triângulo vertical. E como você sabe de que lado da horizontal central você é, basta testar o sinal em relação a um único lado do triângulo.

insira a descrição da imagem aqui

Supondo que você precomputou a inclinação m, bem como os X'vértices dos triângulos cortados e os coeficientes das equações dos lados X = m Y + p, você precisará, no pior dos casos,

  • duas comparações ordenadas para classificação vertical;
  • opcionalmente, uma ou duas comparações de abcissa para rejeição de caixa delimitadora;
  • computação de X' = X - m Y;
  • uma ou duas comparações com as abscissas do triângulo cisalhado;
  • teste de um sinal X >< m' Y + p'contra o lado relevante do triângulo cisalhado.
Yves Daoust
fonte
3

Se você conhece as coordenadas dos três vértices e as coordenadas do ponto específico, pode obter a área do triângulo completo. Depois, calcule a área dos três segmentos do triângulo (um ponto é o ponto dado e os outros dois são quaisquer dois vértices do triângulo). Assim, você obterá a área dos três segmentos de triângulo. Se a soma dessas áreas for igual à área total (que você obteve anteriormente), o ponto deverá estar dentro do triângulo. Caso contrário, o ponto não está dentro do triângulo. Isso deve funcionar. Se houver algum problema, me avise. Obrigado.

ihayet
fonte
3

Outra função em python , mais rápida que o método Developer (pelo menos para mim) e inspirada na solução Cédric Dufour :

def ptInTriang(p_test, p0, p1, p2):       
     dX = p_test[0] - p0[0]
     dY = p_test[1] - p0[1]
     dX20 = p2[0] - p0[0]
     dY20 = p2[1] - p0[1]
     dX10 = p1[0] - p0[0]
     dY10 = p1[1] - p0[1]

     s_p = (dY20*dX) - (dX20*dY)
     t_p = (dX10*dY) - (dY10*dX)
     D = (dX10*dY20) - (dY10*dX20)

     if D > 0:
         return (  (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D  )
     else:
         return (  (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D  )

Você pode testá-lo com:

X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8]) 
p1 = np.array([12 , 55]) 
p2 = np.array([7 , 19]) 
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
    p_test[0] = points_unif[0][i]
    p_test[1] = points_unif[1][i]
    if ptInTriang(p_test, p0, p1, p2):
        plt.plot(p_test[0], p_test[1], '.g')
    else:
        plt.plot(p_test[0], p_test[1], '.r')

Demora muito para plotar, mas essa grade é testada em 0,0195319652557 segundos contra 0,0844349861145 segundos do código do desenvolvedor .

Finalmente o comentário do código:

# Using barycentric coordintes, any point inside can be described as:
# X = p0.x * r + p1.x * s + p2.x * t
# Y = p0.y * r + p1.y * s + p2.y * t
# with:
# r + s + t = 1  and 0 < r,s,t < 1
# then: r = 1 - s - t
# and then:
# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t
# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t
#
# X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# we have to solve:
#
# [ X - p0.x ] = [(p1.x-p0.x)   (p2.x-p0.x)] * [ s ]
# [ Y - p0.Y ]   [(p1.y-p0.y)   (p2.y-p0.y)]   [ t ]
#
# ---> b = A*x ; ---> x = A^-1 * b
# 
# [ s ] =   A^-1  * [ X - p0.x ]
# [ t ]             [ Y - p0.Y ]
#
# A^-1 = 1/D * adj(A)
#
# The adjugate of A:
#
# adj(A)   =   [(p2.y-p0.y)   -(p2.x-p0.x)]
#              [-(p1.y-p0.y)   (p1.x-p0.x)]
#
# The determinant of A:
#
# D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)
#
# Then:
#
# s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }
# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }
#
# s = s_p / D
# t = t_p / D
#
# Recovering r:
#
# r = 1 - (s_p + t_p)/D
#
# Since we only want to know if it is insidem not the barycentric coordinate:
#
# 0 < 1 - (s_p + t_p)/D < 1
# 0 < (s_p + t_p)/D < 1
# 0 < (s_p + t_p) < D
#
# The condition is:
# if D > 0:
#     s_p > 0 and t_p > 0 and (s_p + t_p) < D
# else:
#     s_p < 0 and t_p < 0 and (s_p + t_p) > D
#
# s_p = { dY20*dX - dX20*dY }
# t_p = { dX10*dY - dY10*dX }
# D = dX10*dY20 - dY10*dX20
Ramiro RC
fonte
Esta função não está funcionando. Dê ptInTriang([11,45],[45, 45],[45, 45] ,[44, 45])e ele irá retornar trueembora seja falsa
Código Papa
3

Como não há resposta JS, a solução no
sentido horário e anti-horário:

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}

EDIT: houve um erro de digitação para a computação det (em cy - ayvez de cx - ax), isso é corrigido.

https://jsfiddle.net/jniac/rctb3gfL/

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
	
    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}






let width = 500, height = 500

// clockwise
let triangle1 = {

	A : { x: 10, y: -10 },
	C : { x: 20, y: 100 },
	B : { x: -90, y: 10 },
	
	color: '#f00',

}

// counter clockwise
let triangle2 = {

	A : { x: 20, y: -60 },
	B : { x: 90, y: 20 },
	C : { x: 20, y: 60 },

	color: '#00f',
	
}


let scale = 2
let mouse = { x: 0, y: 0 }






// DRAW >

let wrapper = document.querySelector('div.wrapper')

wrapper.onmousemove = ({ layerX:x, layerY:y }) => {
	
	x -= width / 2
	y -= height / 2
	x /= scale
	y /= scale
	
	mouse.x = x
	mouse.y = y
	
	drawInteractive()

}

function drawArrow(ctx, A, B) {

	let v = normalize(sub(B, A), 3)
	let I = center(A, B)
	
	let p
	
	p = add(I, rotate(v, 90), v)
	ctx.moveTo(p.x, p.y)
	ctx.lineTo(I.x, I .y)
	p = add(I, rotate(v, -90), v)
	ctx.lineTo(p.x, p.y)

}

function drawTriangle(ctx, { A, B, C, color }) {

	ctx.beginPath()
	ctx.moveTo(A.x, A.y)
	ctx.lineTo(B.x, B.y)
	ctx.lineTo(C.x, C.y)
	ctx.closePath()
	
	ctx.fillStyle = color + '6'
	ctx.strokeStyle = color
	ctx.fill()
	
	drawArrow(ctx, A, B)
	drawArrow(ctx, B, C)
	drawArrow(ctx, C, A)
	
	ctx.stroke()

}

function contains({ A, B, C }, P) {

	return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y)

}

function resetCanvas(canvas) {

	canvas.width = width
	canvas.height = height
	
	let ctx = canvas.getContext('2d')

	ctx.resetTransform()
	ctx.clearRect(0, 0, width, height)
	ctx.setTransform(scale, 0, 0, scale, width/2, height/2)
	
}

function drawDots() {

	let canvas = document.querySelector('canvas#dots')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	let count = 1000

	for (let i = 0; i < count; i++) {

		let x = width * (Math.random() - .5)
		let y = width * (Math.random() - .5)
		
		ctx.beginPath()
		ctx.ellipse(x, y, 1, 1, 0, 0, 2 * Math.PI)
		
		if (contains(triangle1, { x, y })) {
		
			ctx.fillStyle = '#f00'
		
		} else if (contains(triangle2, { x, y })) {
		
			ctx.fillStyle = '#00f'
		
		} else {
		
			ctx.fillStyle = '#0003'
		
		}

		
		ctx.fill()
		
	}
	
}

function drawInteractive() {

	let canvas = document.querySelector('canvas#interactive')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	ctx.beginPath()
	ctx.moveTo(0, -height/2)
	ctx.lineTo(0, height/2)
	ctx.moveTo(-width/2, 0)
	ctx.lineTo(width/2, 0)
	ctx.strokeStyle = '#0003'
	ctx.stroke()
	
	drawTriangle(ctx, triangle1)
	drawTriangle(ctx, triangle2)
	
	ctx.beginPath()
	ctx.ellipse(mouse.x, mouse.y, 4, 4, 0, 0, 2 * Math.PI)
	
	if (contains(triangle1, mouse)) {
	
		ctx.fillStyle = triangle1.color + 'a'
		ctx.fill()
		
	} else if (contains(triangle2, mouse)) {
	
		ctx.fillStyle = triangle2.color + 'a'
		ctx.fill()
		
	} else {
	
		ctx.strokeStyle = 'black'
		ctx.stroke()
		
	}
	
}

drawDots()
drawInteractive()










// trigo

function add(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	return { x, y }

}

function center(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	x /= points.length
	y /= points.length
	
	return { x, y }

}

function sub(A, B) {

	let x = A.x - B.x
	let y = A.y - B.y
	
	return { x, y }

}

function normalize({ x, y }, length = 10) {

	let r = length / Math.sqrt(x * x + y * y)
	
	x *= r
	y *= r
	
	return { x, y }

}

function rotate({ x, y }, angle = 90) {

	let length = Math.sqrt(x * x + y * y)
	
	angle *= Math.PI / 180
	angle += Math.atan2(y, x)
	
	x = length * Math.cos(angle)
	y = length * Math.sin(angle)
	
	return { x, y }

}
* {
	margin: 0;
}

html {
	font-family: monospace;
}

body {
	padding: 32px;
}

span.red {
	color: #f00;
}

span.blue {
	color: #00f;
}

canvas {
	position: absolute;
	border: solid 1px #ddd;
}
<p><span class="red">red triangle</span> is clockwise</p>
<p><span class="blue">blue triangle</span> is couter clockwise</p>
<br>
<div class="wrapper">
	<canvas id="dots"></canvas>
	<canvas id="interactive"></canvas>
</div>

insira a descrição da imagem aqui

Estou usando aqui o mesmo método descrito acima: um ponto está dentro do ABC, se estiver respectivamente no lado "igual" de cada linha AB, BC, CA.

exemplo de inclusão de triângulo

Joseph Merdrignac
fonte
Eu cansei esse código e ele não funciona. Sempre retorna Falso.
xApple
hmmm ... você provavelmente cometeu um erro. Aqui está um violino com essa função em execução: jsfiddle.net/jniac/rctb3gfL
Joseph Merdrignac
Eu vi sua resposta do Python, estamos usando o mesmo método, se eu usar mais uma linha ( let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)), isso é para determinar a ordem do enrolamento do triângulo, para que o método funcione com triângulos CW e CCW (consulte jsFiddle).
Joseph Merdrignac
1
hm eu cometi um erro, eu escrevi: let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)em vez de let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)modo que este é fixo, graças para relatar
Joseph Merdrignac
2

Eu só quero usar uma matemática vetorial simples para explicar a solução de coordenadas barentêntricas que Andreas havia dado, será bem mais fácil de entender.

  1. A área A é definida como qualquer vetor dado por s * v02 + t * v01, com as condições s> = 0 et> = 0. Se algum ponto dentro do triângulo v0, v1, v2, ele deve estar dentro da área A.

insira a descrição da imagem aqui

  1. Se mais restringir s, e t pertencer a [0, 1]. Obtemos a Área B, que contém todos os vetores de s * v02 + t * v01, com a condição s, t pertence a [0, 1]. Vale ressaltar que a parte baixa da área B é o espelho do triângulo v0, v1, v2. O problema ocorre se podemos dar certas condições de s, e, para excluir ainda mais a parte baixa da Área B.

insira a descrição da imagem aqui

  1. Suponha que damos um valor s, e t está mudando em [0, 1]. Na foto a seguir, o ponto p está na borda da v1v2. Todos os vetores de s * v02 + t * v01 que estão ao longo da linha do traço por soma vetorial simples. No ponto cruzado v1v2 e na linha de traço p, temos:

(1-s) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |

obtemos 1 - s = tp, então 1 = s + tp. Se qualquer t> tp, que 1 <s + t está na linha de traço duplo, o vetor está fora do triângulo, qualquer t <= tp, que 1> = s + t está na linha de traço único, o vetor é dentro do triângulo.

Então, se dermos algum s em [0, 1], o t correspondente deve atender 1> = s + t, para o vetor dentro do triângulo.

insira a descrição da imagem aqui

Então, finalmente, obtemos v = s * v02 + t * v01, v está dentro do triângulo com a condição s, t, s + t pertence a [0, 1]. Em seguida, traduza para o ponto, temos

p - p0 = s * (p1 - p0) + t * (p2 - p0), com s, t, s + t em [0, 1]

que é o mesmo que a solução de Andreas para resolver o sistema de equações p = p0 + s * (p1 - p0) + t * (p2 - p0), com s, t, s + t pertencem a [0, 1].

Orup
fonte
Você pode apenas dizer que usa o quadro local definido pelos três vértices para que os lados se tornem s = 0, t = 0 es + t = 1. A transformação de coordenadas afins é uma operação bem conhecida da álgebra linear.
Yves Daoust
2

Aqui está uma solução em python que é eficiente, documentada e contém três unittests. É de qualidade profissional e está pronta para ser inserida em seu projeto na forma de um módulo como está.

import unittest

###############################################################################
def point_in_triangle(point, triangle):
    """Returns True if the point is inside the triangle
    and returns False if it falls outside.
    - The argument *point* is a tuple with two elements
    containing the X,Y coordinates respectively.
    - The argument *triangle* is a tuple with three elements each
    element consisting of a tuple of X,Y coordinates.

    It works like this:
    Walk clockwise or counterclockwise around the triangle
    and project the point onto the segment we are crossing
    by using the dot product.
    Finally, check that the vector created is on the same side
    for each of the triangle's segments.
    """
    # Unpack arguments
    x, y = point
    ax, ay = triangle[0]
    bx, by = triangle[1]
    cx, cy = triangle[2]
    # Segment A to B
    side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
    # Segment B to C
    side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
    # Segment C to A
    side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
    # All the signs must be positive or all negative
    return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)

###############################################################################
class TestPointInTriangle(unittest.TestCase):

    triangle = ((22 , 8),
                (12 , 55),
                (7 , 19))

    def test_inside(self):
        point = (15, 20)
        self.assertTrue(point_in_triangle(point, self.triangle))

    def test_outside(self):
        point = (1, 7)
        self.assertFalse(point_in_triangle(point, self.triangle))

    def test_border_case(self):
        """If the point is exactly on one of the triangle's edges,
        we consider it is inside."""
        point = (7, 19)
        self.assertTrue(point_in_triangle(point, self.triangle))

###############################################################################
if __name__ == "__main__":
    suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
    unittest.TextTestRunner().run(suite)

Há um teste gráfico opcional adicional para o algoritmo acima para confirmar sua validade:

import random
from matplotlib import pyplot
from triangle_test import point_in_triangle

###############################################################################
# The area #
size_x = 64
size_y = 64

# The triangle #
triangle = ((22 , 8),
            (12 , 55),
            (7 , 19))

# Number of random points #
count_points = 10000

# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)

# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))

# Plot the points #
for i in range(count_points):
    x = random.uniform(0, size_x)
    y = random.uniform(0, size_y)
    if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
    else:                                  pyplot.plot(x, y, '.b')

# Save it #
figure.savefig("point_in_triangle.pdf")

Produzindo o seguinte gráfico:

Teste a função point_in_triangle

xApple
fonte
1

Existem condições de bordas traquinas em que um ponto está exatamente na borda comum de dois triângulos adjacentes. O ponto não pode estar em ambos ou em nenhum dos triângulos. Você precisa de uma maneira arbitrária, mas consistente, de atribuir o ponto. Por exemplo, desenhe uma linha horizontal através do ponto. Se a linha cruzar com o outro lado do triângulo à direita, o ponto será tratado como se estivesse dentro do triângulo. Se a interseção estiver à esquerda, o ponto estará do lado de fora.

Se a linha na qual o ponto se encontra for horizontal, use acima / abaixo.

Se o ponto estiver no vértice comum de vários triângulos, use o triângulo cujo centro o ponto forma o menor ângulo.

Mais divertido: três pontos podem estar em uma linha reta (zero graus), por exemplo (0,0) - (0,10) - (0,5). Em um algoritmo de triangulação, o "ouvido" (0,10) deve ser cortado, sendo o "triângulo" gerado o caso degenerado de uma linha reta.

Pierre
fonte
1

Este é o conceito mais simples para determinar se um ponto está dentro ou fora do triângulo ou em um braço de um triângulo.

A determinação de um ponto está dentro de um triângulo por determinantes:

A determinação de um ponto está dentro de um triângulo por determinantes

O código de trabalho mais simples:

#-*- coding: utf-8 -*-

import numpy as np

tri_points = [(1,1),(2,3),(3,1)]

def pisinTri(point,tri_points):
    Dx , Dy = point

    A,B,C = tri_points
    Ax, Ay = A
    Bx, By = B
    Cx, Cy = C

    M1 = np.array([ [Dx - Bx, Dy - By, 0],
                    [Ax - Bx, Ay - By, 0],
                    [1      , 1      , 1]
                  ])

    M2 = np.array([ [Dx - Ax, Dy - Ay, 0],
                    [Cx - Ax, Cy - Ay, 0],
                    [1      , 1      , 1]
                  ])

    M3 = np.array([ [Dx - Cx, Dy - Cy, 0],
                    [Bx - Cx, By - Cy, 0],
                    [1      , 1      , 1]
                  ])

    M1 = np.linalg.det(M1)
    M2 = np.linalg.det(M2)
    M3 = np.linalg.det(M3)
    print(M1,M2,M3)

    if(M1 == 0 or M2 == 0 or M3 ==0):
            print("Point: ",point," lies on the arms of Triangle")
    elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
            #if products is non 0 check if all of their sign is same
            print("Point: ",point," lies inside the Triangle")
    else:
            print("Point: ",point," lies outside the Triangle")

print("Vertices of Triangle: ",tri_points)
points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]
for c in points:
    pisinTri(c,tri_points)
Shaon Majumder
fonte
0

Honestamente, é tão simples quanto a resposta de Simon P Steven no entanto, com essa abordagem, você não tem um controle sólido sobre se deseja ou não incluir os pontos nas bordas do triângulo.

Minha abordagem é um pouco diferente, mas muito básica. Considere o seguinte triângulo;

insira a descrição da imagem aqui

Para ter o ponto no triângulo, temos que satisfazer 3 condições

  1. O ângulo ACE (verde) deve ser menor que o ângulo ACB (vermelho)
  2. O ângulo do BCE (azul) deve ser menor que o ângulo do ACB (vermelho)
  3. O ponto E e o ponto C devem ter o mesmo sinal quando seus valores x e y são aplicados à equação da | AB | linha.

Neste método, você tem controle total para incluir ou excluir o ponto nas arestas individualmente. Portanto, você pode verificar se um ponto está no triângulo, incluindo apenas o | AC | borda por exemplo.

Portanto, minha solução em JavaScript seria a seguinte;

function isInTriangle(t,p){

  function isInBorder(a,b,c,p){
    var m = (a.y - b.y) / (a.x - b.x);                     // calculate the slope
    return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y);
  }
  
  function findAngle(a,b,c){                               // calculate the C angle from 3 points.
    var ca = Math.hypot(c.x-a.x, c.y-a.y),                 // ca edge length
        cb = Math.hypot(c.x-b.x, c.y-b.y),                 // cb edge length
        ab = Math.hypot(a.x-b.x, a.y-b.y);                 // ab edge length
    return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle
  }

  var pas = t.slice(1)
             .map(tp => findAngle(p,tp,t[0])),             // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0])
       ta = findAngle(t[1],t[2],t[0]);
  return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p);
}

var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}],
      point1 = {x:3, y:9},
      point2 = {x:7, y:9};

console.log(isInTriangle(triangle,point1));
console.log(isInTriangle(triangle,point2));

Redu
fonte
0
bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
  float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), 
    l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), 
    l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
  return (l1>0 && l2>0  && l3>0) || (l1<0 && l2<0 && l3<0);
}

Não pode ser mais eficiente que isso! Cada lado de um triângulo pode ter posição e orientação independentes, portanto, três cálculos: l1, l2 e l3 são definitivamente necessários, envolvendo 2 multiplicações cada. Uma vez que l1, l2 e l3 são conhecidos, o resultado é apenas algumas comparações básicas e operações booleanas de distância.

Ajay Anand
fonte
0

Código supostamente de alto desempenho que adaptei em JavaScript (artigo abaixo):

function pointInTriangle (p, p0, p1, p2) {
  return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}
  • pointInTriangle(p, p0, p1, p2) - para triângulos no sentido anti-horário
  • pointInTriangle(p, p0, p1, p2) - para triângulos no sentido horário

Veja no jsFiddle (teste de desempenho incluído), também há verificação de enrolamento em uma função separada. Ou pressione "Executar snippet de código" abaixo

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

document.querySelector('#performance').addEventListener('click', _testPerformance);

test();

function test() {
    var result = checkClockwise(triangle.a, triangle.b, triangle.c) ? pointInTriangle(point, triangle.a, triangle.c, triangle.b) : pointInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function _testPerformance () {
	var px = [], py = [], p0x = [], p0y = [], p1x = [], p1y = [], p2x = [], p2y = [], p = [], p0 = [], p1 = [], p2 = [];
    
	for(var i = 0; i < 1000000; i++) {
    p[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p0[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p1[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p2[i] = {x: Math.random() * 100, y: Math.random() * 100};
  }
  console.time('optimal: pointInTriangle');
  for(var i = 0; i < 1000000; i++) {
    pointInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('optimal: pointInTriangle');

  console.time('original: ptInTriangle');
  for(var i = 0; i < 1000000; i++) {
  	ptInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('original: ptInTriangle');
}

function pointInTriangle (p, p0, p1, p2) {
	return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return (s + t) < A;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<button id="performance">Run performance test (open console)</button>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Inspirado por isso: http://www.phatcode.net/articles.php?id=459

Pawel
fonte
-1
bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

coordenadas cartesianas quase perfeitas convertidas de barricêntricas são exportadas entre * v (x) e * w (y) dobra. As duas duplas de exportação devem ter um * char antes em todos os casos, provavelmente: * ve * w O código também pode ser usado para o outro triângulo de um quadrilátero. Por este meio assinado escreveu apenas triângulo abc do quadrante abcd no sentido horário.

A---B
|..\\.o|  
|....\\.| 
D---C 

o ponto o está dentro do triângulo ABC para testar com o segundo triângulo, chame esta função de direção CDA, e os resultados devem estar corretos após *v=1-*v;e *w=1-*w;para o quadrilátero

QuestionFeed
fonte
-1

Eu precisava apontar a verificação do triângulo no "ambiente controlável" quando você tiver certeza absoluta de que os triângulos serão no sentido horário. Então, peguei o jsfiddle do Perro Azul e o modifiquei conforme sugerido pela coproc para esses casos; também removeu multiplicações redundantes de 0,5 e 2 porque elas apenas se cancelam.

http://jsfiddle.net/dog_funtom/H7D7g/

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = {
    x: W / 2,
    y: H / 2
};
var triangle = randomTriangle();

$("canvas").click(function (evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function (evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);

    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    while (true) {
        var result = {
            a: {
                x: rand(0, W),
                y: rand(0, H)
            },
            b: {
                x: rand(0, W),
                y: rand(0, H)
            },
            c: {
                x: rand(0, W),
                y: rand(0, H)
            }
        };
        if (checkClockwise(result.a, result.b, result.c)) return result;
    }
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>

<pre id="result"></pre>

<canvas width="500" height="500"></canvas>

Aqui está o código C # equivalente para o Unity:

public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2)
{
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0)
        return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}
Maxim Kamalov
fonte
-3

Uma das maneiras mais fáceis de verificar se a área formada pelos vértices do triângulo (x1, y1), (x2, y2), (x3, y3) é positiva ou não.

A área pode ser calculada pela fórmula:

1/2 [x1 (y2 – y3) + x2 (y3 – y1) + x3 (y1 – y2)]

ou código python pode ser escrito como:

def triangleornot(p1,p2,p3):
    return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]
Ravi Tanwar
fonte