Wie kann ich feststellen, ob sich ein Punkt in einem 2D-Dreieck befindet?

Lösen Sie das folgende Gleichungssystem:

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

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

s, t und 1 - s - t werden als baryzentrische Koordinaten des Punktes p bezeichnet.

Ich stimme zu Andreas Brinck , baryzentrische Koordinaten sind für diese Aufgabe sehr bequem. Beachten Sie, dass Sie nicht jedes Mal ein Gleichungssystem lösen müssen: Bewerten Sie einfach die analytische Lösung. Mit 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);

wobei Area der (vorzeichenbehaftete) Bereich des Dreiecks ist:

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

Bewerten Sie einfach s, t und 1-s-t. Der Punkt p liegt genau dann im Dreieck, wenn alle positiv sind.

BEARBEITEN: Beachten Sie, dass der obige Ausdruck für den Bereich davon ausgeht, dass die Nummerierung der Dreiecksknoten gegen den Uhrzeigersinn erfolgt. Wenn die Nummerierung im Uhrzeigersinn erfolgt, wird mit diesem Ausdruck ein negativer Bereich (aber mit korrekter Größe) zurückgegeben. 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 1/(2*Area) multipliziert werden, auch das Vorzeichen ändern, wenn sich die Ausrichtung des Dreiecksknotens ändert.

BEARBEITEN 2: Für eine noch bessere Recheneffizienz siehe den Kommentar von coproc (der den Punkt macht, dass, wenn die Orientierung der Dreiecksknoten (im Uhrzeigersinn oder gegen den Uhrzeigersinn) vorher bekannt ist, die Division durch 2*Area im Ausdrücke für s und t können vermieden werden). Siehe auch Perro Azul jsfiddle-code in den Kommentaren unter Andreas Brinck s Antwort.

Ich habe diesen Code vor einem letzten Versuch mit Google geschrieben und diese Seite gefunden. Ich dachte, ich würde ihn teilen. Es ist im Grunde eine optimierte Version der Antwort von Kisielewicz. Ich habe mir die Baryzentrische Methode auch angesehen, aber aus dem Wikipedia-Artikel zu urteilen, fällt es mir schwer zu sehen, wie sie effizienter ist (ich vermute, es gibt eine tiefere Gleichwertigkeit). Dieser Algorithmus hat jedoch 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 links oder rechts von den Linien AB und AC? Wenn ja, kann es nicht drinnen sein. Wenn dies nicht der Fall ist, erfüllen mindestens die "Zapfen" die Bedingung. Da wir 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 dies der Fall ist, kann s möglicherweise nicht drinnen sein, andernfalls muss s drin sein.

Einige Schlüsselwörter in den Berechnungen sind Linienhalbebenen und die Determinante (2x2-Kreuzprodukt). Ein pädagogischerer Weg ist vielleicht, es als einen Punkt zu betrachten, der sich im Inneren befindet, wenn er auf derselben Seite (links oder rechts) zu jeder der Linien AB, BC und CA liegt. Der obige Weg schien jedoch besser für einige Optimierungen zu sein.

C # Version der von andreasdr und Perro Azul geposteten baryzentrischen Methode. Beachten Sie, dass die Flächenberechnung vermieden werden kann, wenn s und t entgegengesetzte Vorzeichen haben. Ich habe das richtige 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);
}

_{[ edit ]}
^{akzeptierte Änderungsvorschlag von @Pierre; Zeige Kommentare}

Ein einfacher Weg ist:

finde die Vektoren, die die .__ verbinden. Zeigen Sie auf jedes der drei Dreiecke Scheitelpunkte und addieren Sie die Winkel zwischen diese Vektoren. Wenn die Summe der Winkel ist 2 * pi dann ist der Punkt innerhalb des Dreiecks.

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

blackpawn und wolfram

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, vorausgesetzt, es gibt keine Überläufe. Es funktioniert auch mit Dreiecken im und gegen den Uhrzeigersinn. Es funktioniert nicht mit kollinearen Dreiecken (Sie können dies jedoch ü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 drei Dreieckspunkten nicht symmetrisch, daher ist sie aufgrund von Rundungsfehlern mit Fließkommazahlen wahrscheinlich weniger konsistent als die halbgehöfte Version von Kornel Kisielewicz.

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

Durch die Verwendung der analytischen Lösung für die baryzentrischen Koordinaten (auf Andreas Brinck hingewiesen) und:

• die Multiplikation nicht über die Klammern verteilt
• vermeiden Sie, mehrmals dieselben Begriffe zu berechnen, indem Sie sie speichern
• vergleiche reduzieren (wie von coproc und Thomas Eding hervorgehoben)

man kann die Anzahl "teurer" 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 Azuljsfiddle eingefügt werden)

Führt zu:

• variable "Rückrufe": 30
• variabler Speicher: 7
• ergänzungen: 4
• substraktionen: 8
• multiplikationen: 6
• abteilungen: keine
• vergleiche: 4

Dies lässt sich gut mit der Kornel Kisielewicz -Lösung (25 Rückrufe, 1 Speicher, 15 Substraktionen, 6 Multiplikationen, 5 Vergleiche) vergleichen und könnte sogar noch besser sein, wenn eine Erkennung im Uhrzeigersinn/gegen den Uhrzeigersinn benötigt wird (was 6 Rückrufe erfordert, 1 Addition, 2 Subtraktionen, 2 Multiplikationen und 1 Vergleich in sich, unter Verwendung der analytischen Lösungsdeterminante, wie von rhgb) hervorgehoben.

Was ich mache, ist die drei Gesichtsnormalen vorberechnen, 

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

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

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

Leistungen:

• vieles ist so vorberechnet, dass mehrere Punkte an demselben Dreieck getestet werden können.

• frühzeitige Ablehnung des allgemeinen Falls von mehr äußeren als inneren Punkten. (Auch wenn 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: 

Andere Funktion in python, schneller als Methode des Entwicklers (für mich mindestens) und inspiriert von 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  )

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 das Raster wird in 0,0195319652557 Sekunden gegen 0,0844349861145 Sekunden Entwicklercode getestet.

Zum Schluss noch der Code-Kommentar:

# 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

Wenn Sie die Koordinaten der drei Scheitelpunkte und die Koordinaten des jeweiligen Punktes 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 gegebene Punkt und die anderen zwei sind zwei Scheitelpunkte 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. Ansonsten liegt der Punkt nicht innerhalb des Dreiecks. Das sollte funktionieren. Wenn es Probleme gibt, lass es mich wissen. Vielen Dank.

Wenn Sie nach Geschwindigkeit suchen, finden Sie hier eine Vorgehensweise, die Ihnen helfen könnte.

Sortiere die Dreieckscheitelpunkte auf ihren Ordinaten. Dies erfordert im schlimmsten Fall drei Vergleiche. Sei Y0, Y1, Y2 die drei sortierten Werte. Wenn Sie drei Horizontale durchziehen, unterteilen 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 einen Test auf den Abscissas zur schnellen Ablehnung links und rechts (X <= X0' or X >= X2') vorlegen. Dadurch wird gleichzeitig ein schneller Bounding-Box-Test implementiert, aber Sie müssen auch die Abszissen sortieren.

Eventuell müssen Sie das Vorzeichen des gegebenen Punktes in Bezug auf die beiden Seiten des Dreiecks berechnen, die die betreffende Platte (obere oder untere) 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, k-Kombinationen (es gibt sechs davon, basierend auf dem Ergebnis der Sortierung) ist nicht Gegenstand dieser Antwort und "dem Leser als Übung überlassen"; aus Effizienzgründen sollten sie hart codiert sein.

Wenn Sie der Meinung sind, dass diese Lösung komplex ist, müssen Sie vor allem einfache Vergleiche (von denen einige vorberechnet werden können) sowie 6 Subtraktionen und 4 Multiplikationen umfassen, falls der Bounding-Box-Test fehlschlägt. Die letztgenannten Kosten sind schwer zu schlagen, da im schlimmsten Fall ein Vergleich des Testpunkts mit zwei Seiten nicht vermieden werden kann (keine Methode in anderen Antworten ist kostengünstiger, manche machen sie schlechter, wie 15 Subtraktionen und 6 Multiplikationen, manchmal Divisionen).

UPDATE: Schneller mit einer Scher-Transformation

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

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

Betrachten Sie dann die durch X'= X - m Y, Y' = Y gegebene "Shear" -Transformation, wobei m die Steigung DX/DY fü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, genügt es, das Zeichen in Bezug auf eine einzelne Seite des Dreiecks zu testen.

Angenommen, Sie haben die Steigung m sowie den X' für die Dreiecksschere und die Koeffizienten der Seitengleichungen als X = m Y + p vorausberechnet, werden Sie im schlimmsten Fall benötigen

• zwei Ordinatenvergleiche zur vertikalen Klassifikation;
• optional ein oder zwei Abszissenvergleiche zur Sperrung der Begrenzungsbox;
• berechnung von X' = X - m Y;
• ein oder zwei Vergleiche mit den Abszissen des gescherten Dreiecks;
• ein Vorzeichentest X >< m' Y + p' gegen die relevante Seite des gescherten Dreiecks.

Es gibt lästige Randbedingungen, bei denen sich ein Punkt genau auf dem gemeinsamen Rand zweier benachbarter Dreiecke befindet. Der Punkt kann nicht in beiden oder in keinem der Dreiecke sein. Sie benötigen einen beliebigen, aber konsistenten Weg, um den Punkt zuzuweisen. Ziehen Sie beispielsweise eine horizontale Linie durch den Punkt. Wenn sich die Linie mit der anderen Seite des Dreiecks rechts schneidet, wird der Punkt so behandelt, als befände er sich innerhalb des Dreiecks. Wenn sich die Kreuzung auf der linken Seite 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 sein (null Grad), zum Beispiel (0,0) - (0,10) - (0,5). In einem Triangulationsalgorithmus muss das "Ohr" (0,10) abgeschnitten werden, wobei das erzeugte "Dreieck" der entartete Fall einer geraden Linie ist.

Hier ist eine Lösung in Python, die effizient und dokumentiert ist und drei Prüfungen enthält. Es ist professionelle Qualität und bereit, in Form eines Moduls in Ihr Projekt aufgenommen zu 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 __== "__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")

Erstellung der folgenden Grafik:

Ich möchte nur eine einfache Vektor-Mathematik verwenden, um die Lösung der baryzentrischen Koordinaten zu erläutern, die Andreas gegeben hatte. Es wird viel einfacher zu verstehen sein.

1. Der Bereich A ist als ein beliebiger Vektor definiert, 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 des Bereichs A liegen.

2. Wenn s weiter einschränken, gehört t zu [0, 1]. Wir erhalten Bereich B, der alle Vektoren von s * v02 + t * v01 enthält, wobei Bedingung s, t zu [0,1] gehört. Es sei darauf hingewiesen, dass der untere Teil der Fläche B der Spiegel von Triangle v0, v1, v2 ist. Das Problem besteht, wenn wir bestimmte Bedingungen von s und t angeben können, um den unteren Teil von Bereich B weiter auszuschließen.

3. Nehmen wir an, 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 entlang der gestrichelten Linie liegen, werden durch einfache Vektorsumme gebildet. Bei v1v2 und dem Schnittpunkt p der gestrichelten Linie haben wir: 

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

wir erhalten 1 - s = tp, dann 1 = s + tp. Wenn irgendein t> tp, wobei 1 <s + t wo auf der doppelten gestrichelten Linie liegt, der Vektor außerhalb des Dreiecks ist, irgendein t <= tp, wobei 1> = s + t wo auf einer einfachen gestrichelten Linie liegt, dann ist der Vektor innerhalb des Dreiecks. 

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

So erhalten wir schließlich v = s * v02 + t * v01, v liegt innerhalb des Dreiecks mit Bedingung s, t, s + t gehört zu [0, 1]. Dann übersetzen wir nach Punkt, den wir haben

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

das ist das gleiche 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 .

Ich brauchte einen Punkt im Dreieck, um in "kontrollierbare Umgebung" zu prüfen, wenn Sie absolut sicher sind, dass Dreiecke im Uhrzeigersinn sind. Also nahm ich Perro Azul 's jiddle und modifizierte es, wie von coproc für solche Fälle vorgeschlagen; Außerdem wurden redundante 0,5- und 2-Multiplikationen entfernt, da sie sich einfach gegenseitig aufheben.

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

Hier ist der gleichwertige C # -Code für 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;
}

Ehrlich gesagt ist es so einfach wie Simon P Stevens Antwort Mit diesem Ansatz haben Sie jedoch keine feste Kontrolle darüber, ob die Punkte an den Rändern des Dreiecks eingeschlossen werden sollen oder nicht.

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

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

1. ACE-Winkel (grün) sollte kleiner als ACB-Winkel (rot) sein
2. ECB-Winkel (blau) sollte kleiner als ACB-Winkel (rot) sein
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, um den Punkt an den Kanten einzeln ein- oder auszuschließen. Sie können also überprüfen, ob sich ein Punkt im Dreieck befindet, der nur das Zeichen | AC | enthält Edge 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));

Der einfachste Weg, und er funktioniert mit allen Arten von Dreiecken, besteht darin, einfach die Winkel der P-Punkte A, B, C zu bestimmen. Wenn einer der Winkel größer als 180,0 Grad ist, befindet er sich außerhalb, wenn 180,0 am Umfang und wenn Sie von einem Betrüger betrogen werden und weniger als 180,0, befindet er sich innerhalb. Achten Sie auf das Verständnis von http : //math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Da es keine Antwort von JS 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 bei der Berechnung (cy - ay statt cx - ax), dies ist behoben.

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

Ich benutze 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.   

        one of the easiest ways to check if the area formed by the vertices of triangle 
        (x1,y1),(x2,y2),(x3,y3) is postive or not .
        area can by calculated by the formula.
        1/ 2 [x1(y2–y3) + x2 (y3–y1) + x3 (y1–y2)]
        or python code can be written as:-


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

Dies ist das einfachste Konzept, um zu bestimmen, ob sich ein Punkt innerhalb oder außerhalb des Dreiecks oder auf einem Arm eines Dreiecks befindet Die Bestimmung eines Punktes liegt 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)

`

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 entgegen dem Uhrzeigersinn

pointInTriangle (p, p0, p1, p2) - für Dreiecke im Uhrzeigersinn

Schauen Sie in jsFiddle (Leistungstest enthalten), in einer separaten Funktion wird auch die Abwicklung überprüft http://jsfiddle.net/z7x0udf7/3/

Inspiriert von diesem: http://www.phatcode.net/articles.php?id=459

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

Es kann nicht effizienter sein als dies! Jede Seite eines Dreiecks kann eine unabhängige Position und Orientierung haben. Daher sind drei Berechnungen erforderlich: l1, l2 und l3, die jeweils zwei Multiplikationen beinhalten. Sobald l1, l2 und l3 bekannt sind, sind nur wenige grundlegende Vergleiche und boolesche Operationen möglich.