Jak określić, czy punkt znajduje się w trójkącie 2D? [zamknięte]

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

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

Punkt p znajduje się wewnątrz trójkąta if 0 <= s <= 1 oraz 0 <= t <= 1 i s + t <= 1.

s,t i 1 - s - t nazywane są współrzędnymi barycentrycznymi punktu p.

Zgadzam się z Andreas Brinck , 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. Używając notacji Andreas , 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 Area jest (podpisanym) obszarem trójkąta:

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

Po prostu oceń s, t i 1-s-t. Punkt p znajduje się wewnątrz trójkąta wtedy i tylko wtedy, gdy wszystkie są dodatnie.

EDIT: Uwaga że powyższe wyrażenie dla obszaru zakłada, że numeracja węzłów trójkąta jest przeciwnie 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 pomnożone przez 1/(2*Area) również zmieniają znak, jeśli zmienia się orientacja węzła trójkąta.

Napisałem ten kod przed ostateczną próbą z Google i znalezienie tej strony, więc pomyślałem, że podzielę się nim. Jest to w zasadzie zoptymalizowana wersja odpowiedzi Kisielewicza. Przyjrzałem się również metodzie Barycentrycznej, ale sądząc po artykule w Wikipedii, trudno mi dostrzec, jak jest ona bardziej efektywna (domyślam się, że istnieje głębsza równoważność). W każdym razie ten algorytm ma tę zaletę, że nie używa się podziału; potencjalnym problemem jest zachowanie detekcji krawędzi w zależności od orientacja.

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

W słowach, idea jest taka: czy punkt s na lewo lub na prawo obu linii AB i AC? Jeśli to prawda, to nie może być w środku. Jeśli jest fałszywy, to przynajmniej wewnątrz "stożków", które spełniają warunek. Teraz, ponieważ wiemy, że punkt wewnątrz trygonu (trójkąta) musi być po tej samej stronie AB co BC (a także CA), sprawdzamy, czy różnią się one. Jeśli tak, to s nie może być w środku, inaczej S musi być w środku.

Niektóre słowa kluczowe w obliczeniach są liniowe pół-płaszczyzny i wyznacznik (iloczyn krzyżowy 2x2). Być może bardziej Pedagogicznym sposobem jest myślenie o tym, że punkt jest wewnątrz iff jest po tej samej stronie (po lewej lub prawej) do każdej z linii AB, BC i CA. Powyższy sposób wydawał się jednak lepiej dopasowany do pewnej optymalizacji.

C # Wersja metody barycentrycznej opublikowanej przez andreasdr i Perro Azul. Dodałem czek, aby zrezygnować z obliczania powierzchni, gdy s i t mają przeciwne znaki, ponieważ potencjalnie uniknięcie jednej trzeciej kosztów mnożenia wydaje się uzasadnione.

Również, mimo że matematyka tutaj jest już mocno ugruntowana, przeprowadziłem dokładny test jednostkowy na tym konkretnym kodzie dla dobrej miary.

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

Java Wersja metody barycentrycznej:

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ł poprawnie z liczbami całkowitymi, przy założeniu braku przepełnień. Będzie również działać 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 kolinearnymi (ale możesz to sprawdzić testując det= = 0).

Wersja barycentryczna jest najszybsza, jeśli zamierzasz testować różne punkty z tym samym trójkątem.

Wersja barycentryczna nie jest symetryczna w 3 punktach trójkąta, więc prawdopodobnie być mniej spójna niż wersja Półpłaszczyznowa Kornela Kisielewicza, ze względu na błędy zaokrąglania zmiennoprzecinkowego.

Kredyt: zrobiłem powyższy kod z artykułu Wikipedii o współrzędnych barycentrycznych.

Prosty sposób to:

Znajdź wektory łączące wskaż każdy z trzech trójkątów wierzchołków i sumują kąty między te wektory. Jeżeli suma kąty to 2 * pi wtedy punkt jest wewnątrz trójkąta.

Dwie dobre strony wyjaśniające alternatywy to:

Blackpawn i wolfram

Za pomocą roztworu analitycznego do współrzędnych barycentrycznych (wskazanego przez Andreasa Brincka ) i:

• nie rozłożenie mnożenia na wyrazy w nawiasach
• unikanie obliczania kilkukrotnie tych samych terminów poprzez ich przechowywanie
• redukcja porównań (jak wskazywali 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 Perro Azul jsfiddle lub spróbuj 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ące do:

• zmienna "przypomina": 30
• przechowywanie zmiennych: 7
• dodatki: 4
• odjęcia: 8
• mnożenie: 6
• działy: brak
• porównania: 4

To całkiem dobrze porównuje się z rozwiązanie Kornela Kisielewicza (25 przypomnień, 1 pamięć, 15 odejmowań, 6 mnożenia, 5 porównań), a może być jeszcze lepiej, jeśli potrzebne jest wykrywanie w kierunku zgodnym z ruchem wskazówek zegara/przeciwnie do ruchu wskazówek zegara (co wymaga 6 przypomnień, 1 dodawania, 2 odejmowania, 2 mnożenia i 1 porównania, używając wyznacznika rozwiązania analitycznego, jak wskazano przez rhgb ).

To, co robię, to prekalkulacja trzech normalnych twarzy,

• W 3D przez iloczyn poprzeczny wektora bocznego i wektora normalnego twarzy.

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

Wtedy Wewnątrz/Na zewnątrz dla dowolnej strony jest, gdy iloczyn punktowy strony normalnej i wierzchołka do wektora punktowego zmienia znak. Powtórz dla pozostałych dwóch (lub więcej) stron.

Korzyści:

• Wiele jest wstępnie obliczonych, więc świetnie dla wielu punktów test na tym samym trójkącie.

• Wczesne odrzucenie wspólnego przypadku więcej zewnętrznych niż wewnętrznych punktów. (również jeśli rozkład punktowy ważony na jedną stronę, może najpierw przetestować tę stronę.)

Jeśli znasz współrzędne trzech wierzchołków i współrzędne określonego punktu, to możesz uzyskać obszar całego trójkąta. Następnie Oblicz pole trzech segmentów trójkąta (jeden punkt to dany punkt, a dwa pozostałe 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ę wewnątrz trójkąta. To powinno zadziałać. Jeśli będą jakieś problemy, daj mi znać. Dziękuję.

Oto skuteczny Python realizacja:

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ładowe wyjście:

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

Posortuj wierzchołki trójkąta na ich współrzędnych. To wymaga co najmniej trzech porównań. 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 porządkiem 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 jeszcze dwa porównania. Jak widać, szybkie odrzucenie jest osiągane dla punktów poza " bounding slab".

Opcjonalnie można wykonać badanie ropni w celu szybkiego odrzucenia po lewej i po prawej stronie (X <= X0' or X >= X2'). Spowoduje to zaimplementowanie szybkiego testu obwiedni w tym samym czasie, ale musisz również posortować na abscissas.

Ostatecznie 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 i, j, k kombinacje (jest ich sześć, w oparciu o wynik sortowania) są poza zakresem tej odpowiedzi i "pozostawione jako ćwiczenie dla czytelnika"; dla skuteczności powinny być mocno zakodowane.

Jeśli uważasz, że to rozwiązanie jest złożone, zwróć uwagę, że obejmuje ono głównie proste porównania (niektóre z nich można wstępnie obliczyć), plus 6 odejmowań i 4 mnożenia w przypadku niepowodzenia testu obwiedni. Ten ostatni koszt jest trudny do pokonania, ponieważ w najgorszym przypadku nie można uniknąć porównania testu punktuj z dwóch stron (żadna metoda w innych odpowiedziach nie ma niższego kosztu, niektóre pogarszają, np. 15 odejmowań i 6 mnożenia, czasem podziałów).

UPDATE: Faster with a shear transform

Jak wyjaśniono powyżej, można szybko zlokalizować punkt wewnątrz jednego z czterech poziomych pasm ograniczonych przez trzy wierzchołki, używając dwóch porównań.

Opcjonalnie można wykonać jeden lub dwa dodatkowe testy X, aby sprawdzić wewnątrz obwiedni (kropkowane linie).

Następnie rozważmy transformatę "ścinania" podaną przez X'= X - m Y, Y' = Y, Gdzie m jest nachyleniem DX/DY dla najwyższej krawędzi. Ta transformacja sprawi, że ta strona trójkąta będzie pionowa. A ponieważ wiesz, po której stronie środkowego poziomego jesteś, wystarczy przetestować znak w odniesieniu do jednej strony trójkąta.

Zakładając, że wstępnie obliczyłeś nachylenie m, a także {[8] } dla ściętych wierzchołków trójkąta i współczynników równań z boków jako X = m Y + p, będziesz potrzebował w najgorszym przypadku

• dwa porównania porządkowe dla klasyfikacji pionowej;
• opcjonalnie jedno lub dwa porównania abscissa dla odrzucenia bounding box;
• obliczenie X' = X - m Y;
• jedno lub dwa porównania z abscissami trójkąta ścinanego;
• test jednego znaku X >< m' Y + p' na odpowiedniej stronie ściętego trójkąta.

Inna funkcja w Pythonie , szybsza niż Metoda programisty (przynajmniej dla mnie) i zainspirowana Cédric Dufour rozwiązanie:

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

Rysowanie zajmuje dużo czasu, ale ta siatka jest testowana w 0.0195319652557 sekund przeciwko 0.0844349861145 sekund kodu programisty .

Wreszcie 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

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

1. Obszar A jest zdefiniowany jako dowolny wektor dany przez s * v02 + t * v01, z warunkami s > = 0 i t > = 0. Jeśli dowolny punkt wewnątrz trójkąta v0, v1, v2, musi być wewnątrz obszaru A.

1. Jeśli dalsze ograniczenie s, A t należy do [0, 1]. Otrzymujemy obszar B zawierający wszystkie wektory s * v02 + t * v01, z warunkiem s, t należy do [0, 1]. Warto zauważyć, że dolna część obszaru B jest zwierciadłem trójkąta v0, v1, V2. Problem pojawia się, jeśli możemy dać pewien warunek s I t, aby dodatkowo wykluczyć niską część obszaru B.

1. Załóżmy, że dajemy 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 znajdują się wzdłuż linii prostej przez sumę wektorów prostych. Na v1v2 i dash line cross point p, mamy:

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

Otrzymujemy 1 - s = tp, następnie 1 = s + tp. Jeśli dowolny t> tp, który 1 = s + t gdzie jest na pojedynczej linii kreski, wektor jest wewnątrz trójkąta.

Wtedy, jeśli daliśmy dowolne s W [0, 1], odpowiednie t musi spełniać 1 >= s + t, dla wektora wewnątrz trójkąta.

W końcu otrzymujemy v = s * v02 + t * v01, V jest wewnątrz trójkąta o warunku s, t, s+T należy do [0, 1]. Następnie translate to point, mamy

P-p0 = s *(p1 - p0) + t *(p2 - p0), z 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 unittesty. Jest to profesjonalna jakość i gotowy do wprowadzenia do projektu w postaci modułu w takim stanie, w jakim jest.

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, aby potwierdzić jego ważność:

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

Tworzenie następującej Grafiki:

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 

}

EDIT: była literówka dla obliczeń det (cy - ay zamiast 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 jest wewnątrz ABC, jeśli jest odpowiednio po "tej samej" stronie każdej linii AB, BC, OK.

Jest to najprostsza koncepcja do określenia, czy punkt znajduje się wewnątrz lub na zewnątrz trójkąta lub na ramieniu trójkąta.

Wyznaczenie punktu wewnątrz trójkąta przez wyznaczniki:

Najprostszy kod roboczy:

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

Istnieją niekorzystne warunki brzegowe, w których punkt znajduje się dokładnie na wspólnej krawędzi dwóch sąsiednich trójkątów. Punkt nie może znajdować się w obu lub żadnym z trójkątów. Potrzebny jest arbitralny, ale spójny sposób przypisania 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ę wewnątrz trójkąta. Jeśli skrzyżowanie jest po lewej stronie, punkt jest 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, z którego środkiem punkt tworzy najmniejszy kąt.

Więcej zabawy: trzy punkty mogą być w linii prostej (zero stopni), na przykład (0,0) - (0,10) - (0,5). W algorytmie triangulacyjnym" ucho "(0,10) musi zostać odcięte, a" trójkąt " wygenerowany jest zdegenerowanym przypadkiem linii prostej.

Najprostszym sposobem, który działa ze wszystkimi typami trójkątów, jest po prostu wyznaczenie kątów punktu P A , B, C kątów 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 acos jest mniejszy niż 180,0 to jest wewnątrz.Poszukaj zrozumienia http://math-physics-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 solidnej kontroli, czy chcesz, aby punkty na krawędziach trójkąta były uwzględniane, czy nie.

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 mają ten sam znak, gdy ich wartości x i y są stosowane do równania linii / AB/.

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

Więc moje rozwiązanie w JavaScript byłoby jak follows;

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 efektywne niż to! Każda strona trójkąta może mieć niezależne położenie i orientację, stąd potrzebne są trzy obliczenia: l1, l2 i L3, z których każda zawiera po 2 mnożenia. Gdy l1, l2 i l3 są znane, wynik jest tylko kilka podstawowych porównań i operacji logicznych.

Rzekomo wysokowydajny kod, który zaadaptował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 przeciwnie do ruchu wskazówek zegara
• pointInTriangle(p, p0, p1, p2) - dla trójkątów zgodnych z ruchem wskazówek zegara

Zajrzyj do jsFiddle (test wydajności w zestawie), istnieje również sprawdzanie uzwojenia w oddzielnej 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) }
    };
}

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

Zainspirowany tym: http://www.phatcode.net/articles.php?id=459

Potrzebowałem punktu w trójkącie sprawdzić w "sterowalnym środowisku", kiedy jesteś absolutnie pewien, że Trójkąty będą zgodne z ruchem wskazówek zegara. Więc wziąłem Perro Azul 's jsfiddle i zmodyfikowałem go zgodnie z sugestią coproc dla takich przypadków; usunąłem również zbędne mnożenia 0.5 I 2, ponieważ po prostu się anulują.

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>

Oto równoważny kod C # Dla 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;
}

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

Prawie doskonałe współrzędne kartezjańskie przekształcone z barycentrycznego są eksportowane do *v (x) i *w (y). Oba podwójne eksport powinny mieć znak * przed w każdym przypadku, prawdopodobnie: * v i * w Kod może być również używany do drugiego trójkąta czworokąta. Podpisane zostało tylko trójkątne abc z kwadratu ABCD w kierunku zgodnym z ruchem wskazówek zegara.

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

Punkt o znajduje się wewnątrz trójkąta ABC do testowania z drugim trójkątem wywołaj tę funkcję kierunek CDA, a wyniki powinny być poprawne po *v=1-*v; i *w=1-*w; dla czworokąta

Jeden z najprostszych sposobów sprawdzenia, czy obszar utworzony przez wierzchołki trójkąta (x1, y1), (x2,y2),(x3,y3) jest dodatnia lub nie.

Obszar można obliczyć wzorem:

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

Lub kod Pythona można zapisać jako:

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