Jak ustalić, czy punkt znajduje się w trójkącie 2D? [Zamknięte]

Czy istnieje prosty sposób ustalenia, czy punkt znajduje się w trójkącie? Jest 2D, a nie 3D.

Zasadniczo najprostszym (i dość optymalnym) algorytmem jest sprawdzenie, po której stronie półpłaszczyzny utworzonej przez krawędzie znajduje się punkt.

Oto informacje o wysokiej jakości w tym temacie na GameDev , w tym problemy z wydajnością.

Oto kod na początek:

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

Rozwiąż następujący układ równań:

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

Punkt pznajduje się wewnątrz trójkąta jeśli 0 <= s <= 1i 0 <= t <= 1i s + t <= 1.

s, tI 1 - s - tnazywane są barycentryczne współrzędne tego punktu p.

Zgadzam się z Andreasem Brinckiem , współrzędne barycentryczne są bardzo wygodne do tego zadania. Zauważ, że nie ma potrzeby rozwiązywania układu równań za każdym razem: wystarczy ocenić rozwiązanie analityczne. Korzystając z notacji Andreasa , rozwiązaniem jest:

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);

gdzie Areajest (podpisany) obszar trójkąta:

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

Wystarczy ocenić s, ta 1-s-t. Punkt pznajduje się w trójkącie tylko wtedy, gdy wszystkie są dodatnie.

EDYCJA: Zauważ, że powyższe wyrażenie dla obszaru zakłada, że ​​numeracja węzłów trójkąta jest przeciwna do ruchu wskazówek zegara. Jeśli numeracja jest zgodna z ruchem wskazówek zegara, to wyrażenie zwróci obszar ujemny (ale z poprawną wielkością). Sam test ( s>0 && t>0 && 1-s-t>0) nie zależy jednak od kierunku numeracji, ponieważ powyższe wyrażenia są mnożone przez 1/(2*Area)znak zmiany również w przypadku zmiany orientacji węzła trójkąta.

EDYCJA 2: Aby uzyskać jeszcze lepszą wydajność obliczeniową, zobacz komentarz Coproc poniżej (który wskazuje, że jeśli orientacja węzłów trójkąta (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara) jest wcześniej znana, podział według 2*Areawyrażeń dla si tmoże być unikane). Zobacz także kod jsfiddle Perro Azula w komentarzach pod odpowiedzią Andreasa Brincka .

Napisałem ten kod przed ostatnią próbą znalezienia tej strony w Google, więc pomyślałem, że go podzielę. Jest to w zasadzie zoptymalizowana wersja odpowiedzi Kisielewicza. Przyjrzałem się również metodzie barycentrycznej, ale sądząc z artykułu z Wikipedii, trudno mi się przekonać, w jaki sposób jest bardziej wydajna (domyślam się, że istnieje głębsza równoważność). W każdym razie ten algorytm ma tę zaletę, że nie używa dzielenia; potencjalnym problemem jest zachowanie detekcji krawędzi w zależności od orientacji.

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

Innymi słowy, idea jest następująca: czy punkt jest na lewo, czy na prawo od linii AB i AC? Jeśli to prawda, nie może być w środku. Jeśli false, to przynajmniej w „stożkach”, które spełniają ten warunek. Ponieważ wiemy, że punkt w trygonie (trójkącie) musi znajdować się po tej samej stronie AB co BC (a także CA), sprawdzamy, czy się różnią. Jeśli tak, to nie może być w środku, w przeciwnym razie musi być w środku.

Niektóre słowa kluczowe w obliczeniach to półpłaszczyzny linii i wyznacznik (iloczyn krzyżowy 2x2). Być może bardziej pedagogicznym sposobem jest prawdopodobnie myślenie o tym jako o punkcie znajdującym się wewnątrz, jeśli jest po tej samej stronie (lewej lub prawej) każdej linii AB, BC i CA. Powyższy sposób wydawał się jednak bardziej odpowiedni do optymalizacji.

Wersja C # metody barycentrycznej opublikowana przez andreasdr i Perro Azul. Należy pamiętać, że kalkulacja obszar można uniknąć, jeśli si tmają przeciwne znaki. Sprawdziłem prawidłowe zachowanie za pomocą dość dokładnego testu jednostkowego.

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

_{[ edytuj ]}
^{zaakceptował sugerowaną modyfikację @Pierre; Zobacz komentarze}

Wersja barycentryczna metody Java:

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

Powyższy kod będzie działał dokładnie z liczbami całkowitymi, przy założeniu braku przepełnienia. Działa również z trójkątami zgodnymi z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara. Nie będzie działać z trójkątami współliniowymi (ale możesz to sprawdzić, testując det == 0).

Wersja barycentryczna jest najszybsza, jeśli zamierzasz przetestować różne punkty za pomocą tego samego trójkąta.

Wersja barycentryczna nie jest symetryczna w 3 punktach trójkąta, więc prawdopodobnie będzie mniej spójna niż wersja półpłaszczyznowa Kornela Kisielewicza z powodu błędów zaokrąglania zmiennoprzecinkowego.

Credit: Powyższy kod zrobiłem z artykułu Wikipedii na temat współrzędnych barycentrycznych.

Prostym sposobem jest:

znajdź wektory łączące punkt z każdym z trzech wierzchołków trójkąta i zsumuj kąty między tymi wektorami. Jeśli suma kątów wynosi 2 * pi, to punkt znajduje się w trójkącie.

Dwie dobre strony wyjaśniające alternatywy to:

blackpawn i wolfram

Stosując rozwiązanie analityczne do współrzędnych barycentrycznych (wskazane przez Andreasa Brincka ) i:

• nie dystrybuuje mnożenia w nawiasach
• unikając wielokrotnego obliczania tych samych terminów przez ich przechowywanie
• redukowanie porównań (jak wskazali Coproc i Thomas Eding )

Można zminimalizować liczbę „kosztownych” operacji:

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

Kod można wkleić w jsfiddle Perro Azul lub wypróbować go, klikając „Uruchom fragment kodu” poniżej

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>

Prowadzący do:

• zmienna „przypomina”: 30
• przechowywanie zmiennych: 7
• dodatki: 4
• odejmowanie: 8
• mnożenia: 6
• podziały: brak
• porównania: 4

Porównuje się to całkiem dobrze z rozwiązaniem Kornela Kisielewicza (25 odwołań, 1 pamięć, 15 odejmowań, 6 mnożeń, 5 porównań), a może być jeszcze lepsze, jeśli konieczne jest wykrywanie zgodnie z ruchem wskazówek zegara / przeciwnie do ruchu wskazówek zegara (co wymaga 6 odwołań, 1 dodania, 2 odejmowań , 2 multiplikacje i 1 porównanie samo w sobie, przy użyciu analitycznego wyznacznika rozwiązania, jak wskazał rhgb ).

To, co robię, polega na wstępnym obliczeniu trzech normalnych twarzy,

• w 3D przez iloczyn wektorowy wektora bocznego i normalnego wektora twarzy.

• w 2D po prostu zamieniając komponenty i negując jeden,

wtedy wewnątrz / na zewnątrz dla jednej strony występuje iloczyn punktowy strony normalnej i wierzchołka do wektora punktowego, zmiana znaku. Powtórz dla pozostałych dwóch (lub więcej) stron.

Korzyści:

• wiele jest wstępnie obliczonych, więc świetnie nadaje się do testowania wielu punktów na tym samym trójkącie.

• wczesne odrzucenie częstego przypadku większej liczby punktów zewnętrznych niż wewnętrznych. (również jeśli rozkład punktów jest ważony z jednej strony, można najpierw przetestować tę stronę).

Oto wydajna implementacja Pythona :

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))

i przykładowy wynik:

Jeśli szukasz prędkości, oto procedura, która może ci pomóc.

Posortuj wierzchołki trójkąta według ich rzędnych. To zajmuje w najgorszym przypadku trzy porównania. Niech Y0, Y1, Y2 będą trzema posortowanymi wartościami. Rysując przez nie trzy poziomy, dzielisz płaszczyznę na dwie półpłaszczyzny i dwie płyty. Niech Y będzie rzędną punktu zapytania.

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

Kosztuje dwa kolejne porównania. Jak widać, szybkie odrzucenie jest osiągane dla punktów poza „płytą ograniczającą”.

Opcjonalnie możesz dostarczyć test na odciętych w celu szybkiego odrzucenia po lewej i po prawej stronie ( X <= X0' or X >= X2'). To wdroży jednocześnie szybki test ramki granicznej, ale musisz też posortować wyniki na odciętych.

W końcu będziesz musiał obliczyć znak danego punktu w odniesieniu do dwóch boków trójkąta, które wyznaczają odpowiednią płytę (górną lub dolną). Test ma postać:

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

Pełna dyskusja na temat i, j, kkombinacji (jest ich sześć, w zależności od wyniku tego rodzaju) jest poza zakresem tej odpowiedzi i „pozostawiona czytelnikowi jako ćwiczenie”; dla wydajności powinny być zakodowane na stałe.

Jeśli uważasz, że to rozwiązanie jest złożone, zauważ, że obejmuje ono głównie proste porównania (niektóre z nich można wstępnie obliczyć), a także 6 odejmowań i 4 mnożeń w przypadku niepowodzenia testu ramki granicznej. Ten ostatni koszt jest trudny do pokonania, ponieważ w najgorszym przypadku nie można uniknąć porównania punktu testowego z dwiema stronami (żadna metoda w innych odpowiedziach nie ma niższego kosztu, niektóre pogarszają, na przykład 15 odejmowań i 6 mnożeń, czasem podziałów).

AKTUALIZACJA: Szybsza dzięki transformacji ścinającej

Jak wyjaśniono powyżej, możesz szybko zlokalizować punkt w jednym z czterech poziomych pasm wyznaczonych przez trzy rzędne wierzchołków, używając dwóch porównań.

Opcjonalnie możesz wykonać jeden lub dwa dodatkowe testy X, aby sprawdzić nieświadomość obwiedni (linie przerywane).

Następnie rozważ transformację „ścinania” podaną przez X'= X - m Y, Y' = Y, gdzie mjest nachylenie DX/DYdla najwyższej krawędzi. Ta transformacja sprawi, że ta strona trójkąta będzie pionowa. A ponieważ wiesz, po której stronie środkowego poziomu jesteś, wystarczy przetestować znak w odniesieniu do pojedynczej strony trójkąta.

Zakładając, że wstępnie obliczyłeś nachylenie m, a także X'ścinane wierzchołki trójkąta i współczynniki równań boków, ponieważ X = m Y + pw najgorszym przypadku będziesz potrzebować

• dwa rzędne porównania do klasyfikacji pionowej;
• opcjonalnie jedno lub dwa porównania odciętych dla odrzucenia ramki granicznej;
• obliczanie X' = X - m Y;
• jedno lub dwa porównania z odciętymi ściętego trójkąta;
• test jednego znaku X >< m' Y + p'na odpowiedniej stronie ściętego trójkąta.

Jeśli znasz współrzędne trzech wierzchołków i współrzędne określonego punktu, możesz uzyskać obszar pełnego trójkąta. Następnie obliczyć powierzchnię trzech segmentów trójkąta (jeden punkt jest podanym punktem, a pozostałe dwa to dowolne dwa wierzchołki trójkąta). W ten sposób otrzymasz obszar trzech segmentów trójkąta. Jeśli suma tych obszarów jest równa całkowitej powierzchni (którą otrzymałeś wcześniej), to punkt powinien znajdować się wewnątrz trójkąta. W przeciwnym razie punkt nie znajduje się w trójkącie. To powinno działać. Jeśli są jakieś problemy, daj mi znać. Dziękuję Ci.

Inne funkcje w pythonie , szybsze niż metoda programisty (przynajmniej dla mnie) i zainspirowane rozwiązaniem 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  )

Możesz to przetestować za pomocą:

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')

Wydrukowanie zajmuje dużo czasu, ale ta siatka jest testowana w 0,0195319652557 sekundach wobec 0,0844349861145 sekund kodu programisty .

Na koniec komentarz do kodu:

# 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

Ponieważ nie ma odpowiedzi JS, rozwiązanie
zgodne z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara:

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 

}

EDYCJA: literówka do obliczeń det ( cy - ayzamiast cx - ax), to jest naprawione.

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>

Używam tutaj tej samej metody, jak opisano powyżej: punkt znajduje się wewnątrz ABC, jeśli jest odpowiednio po „tej samej” stronie każdej linii AB, BC, CA.

Chcę tylko użyć prostej matematyki wektorowej, aby wyjaśnić rozwiązanie współrzędnych barycentrycznych, które podał Andreas, będzie o wiele łatwiejsze do zrozumienia.

1. Obszar A jest definiowany jako dowolny wektor podany przez s * v02 + t * v01, z warunkiem s> = 0 it> 0. Jeśli dowolny punkt wewnątrz trójkąta v0, v1, v2, musi znajdować się w obszarze A.

2. Jeśli dodatkowo ograniczysz s, i t należy do [0, 1]. Otrzymujemy Obszar B, który zawiera wszystkie wektory s * v02 + t * v01, z warunkiem s, t należy do [0, 1]. Warto zauważyć, że dolna część obszaru B to lustro trójkąta v0, v1, v2. Problem pojawia się, jeśli możemy podać pewne warunki s, i t, w celu dalszego wykluczenia niskiej części obszaru B.

3. Załóżmy, że podajemy wartość s, a t zmienia się w [0, 1]. Na poniższym zdjęciu punkt p znajduje się na krawędzi v1v2. Wszystkie wektory s * v02 + t * v01, które są wzdłuż linii myślnika za pomocą prostej sumy wektorów. W punkcie v1v2 i punkcie przecięcia linii przerywanej p mamy:

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

otrzymujemy 1 - s = tp, a następnie 1 = s + tp. Jeśli dowolny t> tp, którego 1 <s + t jest na linii podwójnej kreski, wektor znajduje się poza trójkątem, dowolny t <= tp, który 1> = s + t gdzie jest na linii pojedynczej kreski, wektor jest wewnątrz trójkąta.

Zatem jeśli podamy dowolne s w [0, 1], odpowiadające t musi spełniać 1> = s + t, dla wektora wewnątrz trójkąta.

W końcu otrzymujemy v = s * v02 + t * v01, v znajduje się w trójkącie z warunkiem s, t, s + t należy do [0, 1]. Następnie przetłumacz na punkt, mamy

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

który jest taki sam jak rozwiązanie Andreasa do rozwiązania układu równań p = p0 + s * (p1 - p0) + t * (p2 - p0), przy czym s, t, s + t należą do [0, 1].

Oto rozwiązanie w Pythonie, które jest wydajne, udokumentowane i zawiera trzy unittests. Jest to profesjonalna jakość i jest gotowy do wprowadzenia do projektu w postaci modułu w obecnej postaci.

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)

Istnieje dodatkowy opcjonalny test graficzny dla powyższego algorytmu w celu potwierdzenia jego ważności:

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")

Produkcja następującej grafiki:

Są nieznośne warunki krawędziowe, w których punkt znajduje się dokładnie na wspólnej krawędzi dwóch sąsiadujących trójkątów. Punkt nie może znajdować się w obu, ani w żadnym z trójkątów. Potrzebujesz arbitralnego, ale spójnego sposobu przypisywania punktu. Na przykład narysuj poziomą linię przez punkt. Jeśli linia przecina się z drugą stroną trójkąta po prawej stronie, punkt jest traktowany tak, jakby znajdował się w trójkącie. Jeśli skrzyżowanie znajduje się po lewej stronie, punkt znajduje się na zewnątrz.

Jeśli linia, na której leży punkt, jest pozioma, użyj powyżej / poniżej.

Jeśli punkt znajduje się na wspólnym wierzchołku wielu trójkątów, użyj trójkąta, którego środkiem punkt tworzy najmniejszy kąt.

Więcej zabawy: trzy punkty mogą znajdować się w linii prostej (zero stopni), na przykład (0,0) - (0,10) - (0,5). W algorytmie triangulacyjnym „ucho” (0,10) należy odciąć, przy czym wygenerowany „trójkąt” jest zdegenerowanym przypadkiem linii prostej.

Jest to najprostsza koncepcja pozwalająca ustalić, czy punkt znajduje się wewnątrz trójkąta, czy też na ramieniu trójkąta.

Określenie punktu znajduje się wewnątrz trójkąta za pomocą determinantów:

Najprostszy działający kod:

#-*- 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)

Najłatwiejszym sposobem i działa ze wszystkimi typami trójkątów jest po prostu określenie kątów punktów P punktów A, B, C punktów. Jeśli którykolwiek z kątów jest większy niż 180,0 stopnia, to jest na zewnątrz, jeśli 180,0, to jest na obwodzie, a jeśli oszukuje cię acos i mniej niż 180,0, to jest w środku. Spójrz na zrozumienie http: // matematyka-fizyka -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Szczerze mówiąc, jest to tak proste, jak odpowiedź Simona P. Stevena, jednak przy takim podejściu nie masz pewności, czy chcesz uwzględnić punkty na krawędziach trójkąta, czy nie.

Moje podejście jest trochę inne, ale bardzo podstawowe. Rozważ następujący trójkąt;

Aby mieć punkt w trójkącie, musimy spełnić 3 warunki

1. Kąt ACE (zielony) powinien być mniejszy niż kąt ACB (czerwony)
2. Kąt EBC (niebieski) powinien być mniejszy niż kąt ACB (czerwony)
3. Punkt E i punkt C powinny mieć ten sam znak, gdy ich wartości xiy zostaną zastosowane do równania | AB | linia.

W tej metodzie masz pełną kontrolę, aby osobno uwzględnić lub wykluczyć punkt na krawędziach. Możesz więc sprawdzić, czy punkt znajduje się w trójkącie, w tym tylko | AC | na przykład krawędź.

Tak więc moje rozwiązanie w JavaScript byłoby następujące;

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));

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

To nie może być bardziej wydajne! Każda strona trójkąta może mieć niezależną pozycję i orientację, dlatego na pewno potrzebne są trzy obliczenia: l1, l2 i l3, z których każda wymaga 2 mnożenia. Gdy znane są l1, l2 i l3, wynikiem jest zaledwie kilka podstawowych porównań i operacji boolowskich.

Podobno kod o wysokiej wydajności, który dostosowałem w JavaScript (artykuł poniżej):

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) - dla trójkątów przeciwnych do ruchu wskazówek zegara
• pointInTriangle(p, p0, p1, p2) - dla trójkątów zgodnych z ruchem wskazówek zegara

Spójrz w jsFiddle (test wydajności w zestawie), jest też sprawdzanie uzwojenia w osobnej funkcji. Lub naciśnij „Uruchom fragment kodu” poniżej

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