Wie kann man feststellen, ob sich ein Punkt in einem 2D-Dreieck befindet? [geschlossen]

Gibt es eine einfache Möglichkeit, festzustellen, ob sich ein Punkt innerhalb eines Dreiecks befindet? Es ist 2D, nicht 3D.

Im Allgemeinen prüft der einfachste (und recht optimale) Algorithmus, auf welcher Seite der Halbebene, die durch die Kanten erzeugt wird, der Punkt liegt.

Hier finden Sie einige hochwertige Informationen in diesem Thema zu GameDev , einschließlich Leistungsproblemen.

Und hier ist ein Code, mit dem Sie beginnen können:

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

Lösen Sie das folgende Gleichungssystem:

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

Der Punkt pliegt innerhalb des Dreiecks, wenn 0 <= s <= 1und 0 <= t <= 1und s + t <= 1.

s, tUnd 1 - s - tsind , um die genannten baryzentrischen Koordinaten des Punktes p.

Ich stimme Andreas Brinck zu , baryzentrische Koordinaten sind für diese Aufgabe sehr praktisch. Beachten Sie, dass nicht jedes Mal ein Gleichungssystem gelöst werden muss: Bewerten Sie einfach die analytische Lösung. Unter Verwendung der Andreas -Notation lautet die Lösung:

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

Wo Areaist der (signierte) Bereich des Dreiecks:

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

Nur bewerten s, tund 1-s-t. Der Punkt pliegt genau dann innerhalb des Dreiecks, wenn alle positiv sind.

BEARBEITEN: Beachten Sie, dass der obige Ausdruck für den Bereich davon ausgeht, dass die Nummerierung des Dreiecksknotens gegen den Uhrzeigersinn erfolgt. Wenn die Nummerierung im Uhrzeigersinn erfolgt, gibt dieser Ausdruck einen negativen Bereich zurück (jedoch mit der richtigen Größe). Der Test selbst ( s>0 && t>0 && 1-s-t>0) hängt jedoch nicht von der Richtung der Nummerierung ab, da die obigen Ausdrücke, die mit multipliziert werden, 1/(2*Area)auch das Vorzeichen ändern, wenn sich die Ausrichtung des Dreiecksknotens ändert.

EDIT 2: Für eine noch bessere Recheneffizienz siehe Coprocs Kommentar unten (der darauf hinweist , dass, wenn die Ausrichtung der Dreiecksknoten (im oder gegen den Uhrzeigersinn) vorher bekannt ist, die Division durch 2*Areain den Ausdrücken für sund sein tkann vermieden). Siehe auch Perro Azul 's jsfiddle-Code in den Kommentaren unter Andreas Brincks Antwort.

Ich habe diesen Code vor einem letzten Versuch mit Google geschrieben und diese Seite gefunden, also dachte ich, ich würde ihn teilen. Es ist im Grunde eine optimierte Version der Kisielewicz-Antwort. Ich habe mich auch mit der Barycentric-Methode befasst, aber nach dem Wikipedia-Artikel fällt es mir schwer zu erkennen, wie effizient sie ist (ich vermute, es gibt eine tiefere Äquivalenz). Auf jeden Fall hat dieser Algorithmus den Vorteil, dass keine Division verwendet wird. Ein mögliches Problem ist das Verhalten der Kantenerkennung in Abhängigkeit von der Ausrichtung.

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

In Worten lautet die Idee: Befindet sich der Punkt s links oder rechts von den Linien AB und AC? Wenn das stimmt, kann es nicht drinnen sein. Wenn falsch, ist es zumindest innerhalb der "Zapfen", die die Bedingung erfüllen. Da wir nun wissen, dass ein Punkt innerhalb eines Trigons (Dreiecks) auf derselben Seite von AB liegen muss wie BC (und auch CA), prüfen wir, ob sie sich unterscheiden. Wenn ja, kann s unmöglich drinnen sein, sonst muss s drinnen sein.

Einige Schlüsselwörter in den Berechnungen sind Linienhalbflächen und die Determinante (2x2-Kreuzprodukt). Vielleicht ist es pädagogischer, es als einen Punkt zu betrachten, der sich innerhalb derselben Linie (links oder rechts) zu jeder der Linien AB, BC und CA befindet. Der obige Weg schien jedoch für einige Optimierungen besser geeignet zu sein.

C # -Version der baryzentrischen Methode von andreasdr und Perro Azul. Beachten Sie, dass die Flächenberechnung , wenn vermieden werden können sund tentgegengesetzte Vorzeichen haben. Ich habe das korrekte Verhalten mit einem ziemlich gründlichen Unit-Test überprüft.

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

_{[ Bearbeiten ]}
^{akzeptierte Änderungsvorschläge von @Pierre; Zeige Kommentare}

Java-Version der baryzentrischen Methode:

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

Der obige Code funktioniert genau mit ganzen Zahlen, sofern keine Überläufe auftreten. Es funktioniert auch mit Dreiecken im Uhrzeigersinn und gegen den Uhrzeigersinn. Es funktioniert nicht mit kollinearen Dreiecken (aber Sie können dies überprüfen, indem Sie det == 0 testen).

Die baryzentrische Version ist am schnellsten, wenn Sie verschiedene Punkte mit demselben Dreieck testen möchten.

Die baryzentrische Version ist in den 3 Dreieckspunkten nicht symmetrisch, daher ist sie aufgrund von Gleitkomma-Rundungsfehlern wahrscheinlich weniger konsistent als die Rand-Halbebenen-Version von Kornel Kisielewicz.

Bildnachweis: Ich habe den obigen Code aus dem Wikipedia-Artikel über Schwerpunktkoordinaten erstellt.

Ein einfacher Weg ist:

Finden Sie die Vektoren, die den Punkt mit jedem der drei Eckpunkte des Dreiecks verbinden, und addieren Sie die Winkel zwischen diesen Vektoren. Wenn die Summe der Winkel 2 * pi ist, liegt der Punkt innerhalb des Dreiecks.

Zwei gute Websites, die Alternativen erklären, sind:

Blackpawn und Wolfram

Durch Verwendung der analytischen Lösung für die Schwerpunktkoordinaten (von Andreas Brinck hervorgehoben ) und:

• Verteilen der Multiplikation nicht auf die in Klammern gesetzten Begriffe
• Vermeiden Sie es, mehrmals dieselben Begriffe zu berechnen, indem Sie sie speichern
• Reduzierung der Vergleiche (wie von Coproc und Thomas Eding hervorgehoben )

Man kann die Anzahl der "kostspieligen" Operationen minimieren:

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

Code kann in Perro Azul jsfiddle eingefügt werden oder versuchen Sie es, indem Sie unten auf "Code-Snippet ausführen" klicken

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>

Führend zu:

• Variable "Rückrufe": 30
• variabler Speicher: 7
• Ergänzungen: 4
• Subtraktionen: 8
• Multiplikationen: 6
• Abteilungen: keine
• Vergleiche: 4

Dies ist ein guter Vergleich mit der Kornel Kisielewicz- Lösung (25 Rückrufe, 1 Speicher, 15 Subtraktionen, 6 Multiplikationen, 5 Vergleiche) und könnte sogar noch besser sein, wenn eine Erkennung im Uhrzeigersinn / gegen den Uhrzeigersinn erforderlich ist (was 6 Rückrufe, 1 Addition, 2 Subtraktionen erfordert , 2 Multiplikationen und 1 Vergleich an sich unter Verwendung der analytischen Lösungsdeterminante, wie durch rhgb ) hervorgehoben.

Was ich tue, ist die drei Gesichtsnormalen vorberechnen,

• in 3D durch Kreuzprodukt des Seitenvektors und des Gesichtsnormalenvektors.

• in 2D durch einfaches Austauschen und Negieren von Komponenten,

dann ist innen / außen für eine Seite, wenn ein Punktprodukt der Seitennormalen und des Scheitelpunkt-zu-Punkt-Vektors das Vorzeichen ändert. Wiederholen Sie dies für zwei andere (oder mehr) Seiten.

Leistungen:

• Vieles ist vorberechnet und eignet sich daher hervorragend für Mehrpunkttests an demselben Dreieck.

• frühzeitige Ablehnung des allgemeinen Falls von mehr äußeren als inneren Punkten. (Auch wenn die Punktverteilung auf eine Seite gewichtet ist, kann diese Seite zuerst getestet werden.)

Hier ist eine effiziente Python- Implementierung:

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

und eine Beispielausgabe:

Wenn Sie auf der Suche nach Geschwindigkeit sind, finden Sie hier ein Verfahren, das Ihnen helfen kann.

Sortieren Sie die Dreiecksscheitelpunkte nach ihren Ordinaten. Dies erfordert im schlimmsten Fall drei Vergleiche. Sei Y0, Y1, Y2 die drei sortierten Werte. Indem Sie drei Horizontale durchziehen, teilen Sie die Ebene in zwei Halbebenen und zwei Platten. Sei Y die Ordinate des Abfragepunktes.

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

Kostet zwei weitere Vergleiche. Wie Sie sehen, wird eine schnelle Zurückweisung für Punkte außerhalb der "Begrenzungsplatte" erreicht.

Optional können Sie links und rechts einen Test für die Abszissen zur schnellen Ablehnung durchführen (X <= X0' or X >= X2' ). Dadurch wird gleichzeitig ein schneller Bounding-Box-Test durchgeführt, aber Sie müssen auch die Abszissen sortieren.

Schließlich müssen Sie das Vorzeichen des angegebenen Punkts in Bezug auf die beiden Seiten des Dreiecks berechnen, die die betreffende Platte (oben oder unten) begrenzen. Der Test hat die Form:

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

Die vollständige Erörterung von i, j, kKombinationen (es gibt sechs davon, basierend auf dem Ergebnis der Sortierung) liegt außerhalb des Rahmens dieser Antwort und wird "dem Leser als Übung überlassen". Aus Gründen der Effizienz sollten sie fest codiert sein.

Wenn Sie der Meinung sind, dass diese Lösung komplex ist, beachten Sie, dass es sich hauptsächlich um einfache Vergleiche (von denen einige vorberechnet werden können) sowie um 6 Subtraktionen und 4 Multiplikationen handelt, falls der Bounding-Box-Test fehlschlägt. Die letztgenannten Kosten sind schwer zu übertreffen, da Sie im schlimmsten Fall nicht vermeiden können, den Testpunkt mit zwei Seiten zu vergleichen (keine Methode in anderen Antworten hat geringere Kosten, einige verschlimmern sie, wie 15 Subtraktionen und 6 Multiplikationen, manchmal Divisionen).

UPDATE: Schneller mit einer Schertransformation

Wie oben erläutert, können Sie den Punkt innerhalb eines der vier horizontalen Bänder, die durch die drei Scheitelpunkt-Ordinaten begrenzt sind, mithilfe von zwei Vergleichen schnell lokalisieren.

Optional können Sie ein oder zwei zusätzliche X-Tests durchführen, um die Unversehrtheit des Begrenzungsrahmens (gepunktete Linien) zu überprüfen.

Betrachten Sie dann die "Scher" -Transformation, die durch gegeben ist X'= X - m Y, Y' = Y, wobei mdie Steigung DX/DYfür die höchste Kante ist. Diese Transformation macht diese Seite des Dreiecks vertikal. Und da Sie wissen, auf welcher Seite der mittleren Horizontalen Sie sich befinden, reicht es aus, das Zeichen in Bezug auf eine einzelne Seite des Dreiecks zu testen.

Angenommen, Sie haben die Steigung msowie die X'Eckpunkte für die gescherten Dreiecke und die Koeffizienten der Gleichungen der Seiten als vorberechnet , X = m Y + pbenötigen Sie im schlimmsten Fall

• zwei Ordinatenvergleiche zur vertikalen Klassifizierung;
• optional ein oder zwei Abszissenvergleiche zur Begrenzung des Begrenzungsrahmens;
• Berechnung von X' = X - m Y ;
• ein oder zwei Vergleiche mit den Abszissen des gescherten Dreiecks;
• Ein-Zeichen-Test X >< m' Y + p'gegen die relevante Seite des gescherten Dreiecks.

Wenn Sie die Koordinaten der drei Eckpunkte und die Koordinaten des spezifischen Punkts kennen, können Sie die Fläche des gesamten Dreiecks ermitteln. Berechnen Sie anschließend die Fläche der drei Dreiecksegmente (ein Punkt ist der angegebene Punkt und die anderen beiden sind zwei beliebige Eckpunkte des Dreiecks). So erhalten Sie die Fläche der drei Dreiecksegmente. Wenn die Summe dieser Flächen gleich der Gesamtfläche ist (die Sie zuvor erhalten haben), sollte sich der Punkt innerhalb des Dreiecks befinden. Andernfalls befindet sich der Punkt nicht innerhalb des Dreiecks. Das sollte funktionieren. Wenn es irgendwelche Probleme gibt, lass es mich wissen. Danke dir.

Andere Funktion in Python , schneller als die Entwicklermethode (zumindest für mich) und inspiriert von der Cédric Dufour- Lösung:

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  )

Sie können es testen mit:

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

Das Plotten erfordert viel Zeit, aber dieses Raster wird in 0,0195319652557 Sekunden gegen 0,0844349861145 Sekunden des Entwicklercodes getestet .

Zum Schluss der Codekommentar:

# 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

Da es keine JS-Antwort gibt,
Lösung im Uhrzeigersinn und gegen den Uhrzeigersinn:

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 

}

BEARBEITEN: Es gab einen Tippfehler für die Det-Berechnung ( cy - ayanstelle von cx - ax), dies ist behoben.

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>

Ich verwende hier die gleiche Methode wie oben beschrieben: Ein Punkt befindet sich innerhalb von ABC, wenn er sich jeweils auf der "gleichen" Seite jeder Linie AB, BC, CA befindet.

Ich möchte nur eine einfache Vektormathematik verwenden, um die Lösung der Schwerpunktkoordinaten zu erklären, die Andreas gegeben hat. Es wird viel einfacher zu verstehen sein.

1. Bereich A ist definiert als ein beliebiger Vektor, der durch s * v02 + t * v01 gegeben ist, mit der Bedingung s> = 0 und t> = 0. Wenn sich ein Punkt innerhalb des Dreiecks v0, v1, v2 befindet, muss er innerhalb von Bereich A liegen.

2. Wenn weiter eingeschränkt, gehört s und t zu [0, 1]. Wir erhalten den Bereich B, der alle Vektoren von s * v02 + t * v01 enthält, wobei die Bedingung s, t zu [0, 1] gehört. Es ist anzumerken, dass der untere Teil des Bereichs B der Spiegel des Dreiecks v0, v1, v2 ist. Das Problem tritt auf, wenn wir bestimmte Bedingungen von s und t angeben können, um den unteren Teil von Bereich B weiter auszuschließen.

3. Angenommen, wir geben einen Wert s an und t ändert sich in [0, 1]. Im folgenden Bild befindet sich Punkt p am Rand von v1v2. Alle Vektoren von s * v02 + t * v01, die durch einfache Vektorsumme entlang der Strichlinie liegen. Bei v1v2 und dem Strichlinienkreuzungspunkt p haben wir:

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

wir erhalten 1 - s = tp, dann 1 = s + tp. Wenn irgendein t> tp, welches 1 <s + t, wo sich auf der doppelten Strichlinie befindet, der Vektor außerhalb des Dreiecks liegt, jedes t <= tp, welches 1> = s + t, wo sich auf der einzelnen Strichlinie befindet, ist der Vektor innerhalb des Dreiecks.

Wenn wir dann in [0, 1] ein s angeben, muss das entsprechende t für den Vektor innerhalb des Dreiecks 1> = s + t erfüllen.

Schließlich erhalten wir v = s * v02 + t * v01, v befindet sich innerhalb des Dreiecks mit der Bedingung s, t, s + t gehört zu [0, 1]. Dann übersetzen wir auf Punkt, den wir haben

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

Dies ist die gleiche Lösung wie Andreas 'Lösung zur Lösung des Gleichungssystems. p = p0 + s * (p1 - p0) + t * (p2 - p0), wobei s, t, s + t zu [0, 1] gehören.

Hier ist eine Lösung in Python, die effizient und dokumentiert ist und drei Unittests enthält. Es ist von professioneller Qualität und kann so wie es ist in Form eines Moduls in Ihr Projekt eingefügt werden.

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)

Es gibt einen zusätzlichen optionalen grafischen Test für den obigen Algorithmus, um seine Gültigkeit zu bestätigen:

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

Erstellen der folgenden Grafik:

Es gibt lästige Kantenbedingungen, bei denen ein Punkt genau auf der gemeinsamen Kante zweier benachbarter Dreiecke liegt. Der Punkt kann nicht in beiden oder keinem der Dreiecke liegen. Sie benötigen eine willkürliche, aber konsistente Art, den Punkt zuzuweisen. Zeichnen Sie beispielsweise eine horizontale Linie durch den Punkt. Wenn sich die Linie mit der anderen Seite des Dreiecks auf der rechten Seite schneidet, wird der Punkt so behandelt, als ob er sich innerhalb des Dreiecks befindet. Wenn sich der Schnittpunkt links befindet, befindet sich der Punkt außerhalb.

Wenn die Linie, auf der der Punkt liegt, horizontal ist, verwenden Sie oben / unten.

Wenn sich der Punkt auf dem gemeinsamen Scheitelpunkt mehrerer Dreiecke befindet, verwenden Sie das Dreieck, mit dessen Mittelpunkt der Punkt den kleinsten Winkel bildet.

Mehr Spaß: Drei Punkte können in einer geraden Linie (null Grad) liegen, zum Beispiel (0,0) - (0,10) - (0,5). Bei einem Triangulationsalgorithmus muss das "Ohr" (0,10) abgeschnitten werden, wobei das erzeugte "Dreieck" der entartete Fall einer geraden Linie ist.

Dies ist das einfachste Konzept, um festzustellen, ob sich ein Punkt innerhalb oder außerhalb des Dreiecks oder auf einem Arm eines Dreiecks befindet.

Die Bestimmung eines Punktes erfolgt innerhalb eines Dreiecks durch Determinanten:

Der einfachste Arbeitscode:

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

Der einfachste Weg und es funktioniert mit allen Arten von Dreiecken ist einfach die Winkel der P-Punkt A-, B-, C-Punktwinkel zu bestimmen. Wenn eine des Winkels größer als 180,0 Grad , dann ist es draußen, wenn 180.0 dann ist es auf dem Umfang und wenn acos auf Sie zu betrügen und weniger als 180,0 dann ist es inside.Take ein Blick für das Verständnis http: // Mathe-Physik -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Ehrlich gesagt ist es so einfach wie die Antwort von Simon P. Steven aber mit diesem Ansatz haben Sie keine solide Kontrolle darüber, ob die Punkte an den Kanten des Dreiecks enthalten sein sollen oder nicht.

Mein Ansatz ist etwas anders, aber sehr einfach. Betrachten Sie das folgende Dreieck;

Um den Punkt im Dreieck zu haben, müssen wir 3 Bedingungen erfüllen

1. Der ACE-Winkel (grün) sollte kleiner sein als der ACB-Winkel (rot).
2. Der EZB-Winkel (blau) sollte kleiner sein als der ACB-Winkel (rot).
3. Punkt E und Punkt C sollten das gleiche Vorzeichen haben, wenn ihre x- und y-Werte auf die Gleichung von | AB | angewendet werden Linie.

Bei dieser Methode haben Sie die volle Kontrolle darüber, den Punkt an den Kanten einzeln einzuschließen oder auszuschließen. Sie können also überprüfen, ob sich ein Punkt im Dreieck befindet, der nur | AC | enthält Kante zum Beispiel.

Meine Lösung in JavaScript wäre also wie folgt:

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

Effizienter geht es nicht! Jede Seite eines Dreiecks kann eine unabhängige Position und Ausrichtung haben, daher sind drei Berechnungen erforderlich: l1, l2 und l3 werden definitiv mit jeweils 2 Multiplikationen benötigt. Sobald l1, l2 und l3 bekannt sind, sind nur wenige grundlegende Vergleiche und boolesche Operationen entfernt.

Angeblich Hochleistungscode, den ich in JavaScript angepasst habe (Artikel unten):

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) - für Dreiecke gegen den Uhrzeigersinn
• pointInTriangle(p, p0, p1, p2) - für Dreiecke im Uhrzeigersinn

Schauen Sie in jsFiddle (Leistungstest eingeschlossen), es gibt auch Wicklungsprüfung in einer separaten Funktion. Oder klicken Sie unten auf "Code-Snippet ausführen"

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