Comment déterminer si un point est dans un triangle 2D?

résoudre le système d'équation suivant:

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

le point p est à l'intérieur du triangle si 0 <= s <= 1 et 0 <= t <= 1 et s + t <= 1 .

s , t et 1 - s - t sont appelés les coordonnées barycentriques du point p .

je suis d'accord avec Andreas Brinck , les coordonnées barycentriques sont très pratiques pour cette tâche. Notez qu'il n'est pas nécessaire de résoudre une équation à chaque fois: il suffit d'évaluer la solution analytique. En utilisant Andreas 'notation, la solution est:

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

où Area est la zone (signée) du triangle:

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

Simplement évaluer s , t et 1-s-t . Le point p est à l'intérieur du triangle si et seulement si elles sont toutes positives.

modifier: notez que l'expression ci-dessus pour la zone suppose que la numérotation des noeuds triangle est dans le sens contraire des aiguilles d'une montre. Si la numérotation est dans le sens des aiguilles d'une montre, cette expression retournera une zone négative (mais avec une magnitude correcte). Le test lui-même ( s>0 && t>0 && 1-s-t>0 ) ne dépend pas de la direction de la numérotation, cependant, puisque les expressions ci-dessus qui sont multipliées par 1/(2*Area) aussi changer le signe si l'orientation du noeud du triangle change.

EDIT 2: pour une efficacité de calcul encore meilleure, voir le commentaire de coproc ci-dessous (qui fait le point que si l'orientation des noeuds du triangle (dans le sens des aiguilles d'une montre ou dans le sens contraire des aiguilles d'une montre) est connue au préalable, la division par 2*Area dans les expressions pour s et t peut être évitée). Voir aussi Perro Azul ' s jsfiddle-code dans les commentaires sous Andreas Brinck 'S réponse.

j'ai écrit ce code avant Une dernière tentative avec Google et trouver cette page, donc j'ai pensé que je partagerais. Il s'agit essentiellement d'une version optimisée de Kisielewicz réponse. J'ai aussi examiné la méthode barycentrique, mais à en juger par L'article de Wikipedia, j'ai du mal à voir comment elle est plus efficace (je devine qu'il y a une équivalence plus profonde). Quoi qu'il en soit, cet algorithme a l'avantage de ne pas utiliser la division; un problème potentiel est le comportement de la détection de bord en fonction orientation.

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

en mots, l'idée est celle-ci: est-ce que les points à gauche ou à droite des deux lignes AB et AC? Si c'est vrai, ça ne peut pas être à l'intérieur. Si false, Il est au moins à l'intérieur des "cônes" qui satisfont à la condition. Maintenant, puisque nous savons qu'un point à l'intérieur d'un trigon (triangle) doit être du même côté de AB que BC (et aussi CA), nous vérifions s'ils diffèrent. S'ils le font, s ne peut pas être à l'intérieur, sinon doit être à l'intérieur.

Some les mots clés utilisés dans les calculs sont les demi-plans linéaires et le déterminant (produit croisé 2x2). Peut-être une façon plus pédagogique est-elle de penser qu'il s'agit d'un point à l'intérieur du FIF, c'est du même côté (à gauche ou à droite) de chacune des lignes AB, BC et CA. Le ci-dessus semble mieux convenir à certains d'optimisation.

c# version de la méthode barycentrique publiée par andreasdr et Perro Azul. Il est à noter que le calcul de la superficie peut être évité si s et t ont des signes opposés. J'ai vérifié le comportement avec un test assez complet.

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;
    if (A < 0.0)
    {
        s = -s;
        t = -t;
        A = -A;
    }
    return s > 0 && t > 0 && (s + t) <= A;
}

_{[ modifier ]}

^{accepted proposed modification by @Pierre; see comments}

une façon simple est de:

trouver les vecteurs de connexion pointe vers chacun des trois triangles les sommets et la somme des angles entre ces vecteurs. Si la somme de la les angles sont de 2 * pi puis le point est à l'intérieur du triangle.

deux bons sites qui expliquent les solutions de rechange sont:

blackpawn et wolfram

version Java de la méthode barycentrique:

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

le code ci-dessus fonctionnera correctement avec les entiers, en supposant aucun débordement. Il travaillera également avec des aiguilles d'une montre et dans le sens inverse des triangles. Il ne fonctionnera pas avec les triangles collinéaires (mais vous pouvez vérifier cela en testant det==0).

la version barycentrique est la plus rapide si vous allez tester différents points avec le même triangle.

la version barycentrique n'est pas symétrique dans les 3 points du triangle, de sorte qu'il est probablement moins cohérent que la version demi-plan du bord de Kornel Kisielewicz, en raison d'erreurs d'arrondi de la pointe flottante.

crédit: j'ai fait le code ci-dessus à partir de L'article de Wikipedia sur les coordonnées barycentriques.

en utilisant la solution analytique aux coordonnées barycentriques (indiquées par Andreas Brinck ) et:

• pas la distribution de la multiplication sur la mise entre parenthèses les termes
• éviter de calculer plusieurs fois les mêmes termes en les stockant
• la réduction des comparaisons (comme l'a souligné coproc et Thomas Eding )

on peut minimiser le nombre d'opérations "coûteuses":

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

(le code peut être collé dans Perro Azul jsfiddle )

conduisant à:

• variable " rappels": 30
• stockage variable: 7
• adjonctions: 4
• soustractions: 8
• multiplications: 6
• divisions: aucune
• comparaisons: 4

cela se compare assez bien avec Kornel Kisielewicz solution (25 rappels, 1 stockage, 15 soustractions, 6 multiplications, 5 comparaisons), et pourrait être encore mieux si une détection dans le sens des aiguilles d'une montre/anti-sens des aiguilles d'une montre est nécessaire (ce qui prend 6 rappels, 1 addition, 2 soustractions, 2 multiplications et 1 comparaison en soi, en utilisant le déterminant de la solution analytique, comme indiqué par rhgb ).

Ce que je fais est précalculer les trois visage normales,

• en 3D par produit croisé du vecteur latéral et du vecteur normal face.

• en 2D, en changeant tout simplement les composants et la négation de l'un,

alors intérieur/extérieur pour un côté quelconque est quand un produit de point du côté normal et le vertex à point vecteur, changer de signe. Répétez l'opération pour les deux autres (ou plus) côté.

prestations:

• un lot est précalculé si grand pour les tests à points multiples sur un même triangle.

• rejet précoce du cas commun de plus de points extérieurs que intérieurs. (également si la distribution de point pondéré à un côté, peut tester ce côté d'abord.)

voici un Python implémentation:

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

et un exemple de sortie:

si vous cherchez la vitesse, voici une procédure qui pourrait vous aider.

trient les sommets triangulaires sur leurs ordonnées. Cela prend au pire trois comparaisons. Que Y0, Y1, Y2 soient les trois valeurs triées. En dessinant trois horizontales à travers eux, vous divisez le plan en deux demi-plans et deux plaques. Soit Y l'ordonnée du point de requête.

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

coûte deux comparaisons supplémentaires. Comme vous le voyez, rapide rejet est atteint pour les points à l'extérieur de la"dalle limite".

en option, vous pouvez fournir un test sur les abscisses pour un rejet rapide à gauche et à droite ( X <= X0' or X >= X2' ). Cela permettra de mettre en œuvre un test de boxe rapide en même temps, mais vous aurez besoin de trier sur les abscisses aussi.

éventuellement, vous devrez calculer le signe du point donné par rapport aux deux côtés du triangle qui délimitent la dalle pertinente (supérieur ou inférieur). Le test a la forme:

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

la discussion complète des combinaisons i, j, k (il y en a six, selon le résultat du tri) est hors de la portée de cette réponse et" laissée au lecteur comme exercice"; pour des raisons d'efficacité, elles doivent être codées en dur.

si vous pensez que cette solution est complexe, observez qu'elle implique principalement des comparaisons simples (dont certaines peuvent être calculées à l'avance), plus 6 soustractions et 4 multiplications en si le test de la boîte de délimitation échoue. Ce dernier coût est difficile à battre car dans le pire des cas, vous ne pouvez pas éviter de comparer le point de test contre deux côtés (aucune méthode dans d'autres réponses a un coût plus faible, certains font pire, comme 15 soustractions et 6 multiples, parfois divisions).

mise à jour: Plus rapide avec une transformation de cisaillement

comme expliqué ci-dessus, vous pouvez rapidement localiser le point à l'intérieur d'une des quatre bandes horizontales délimitées par les trois sommets coordonnées, à l'aide de deux comparaisons.

vous pouvez éventuellement effectuer un ou deux tests X supplémentaires pour vérifier l'insideness de la boîte de limite (lignes pointillées).

puis considérer la transformation de" cisaillement "donnée par X'= X - m Y, Y' = Y , où m est la pente DX/DY pour le bord le plus élevé. Cette transformation va rendre ce côté du triangle vertical. Et comme vous savez de quel côté de l'horizontale du milieu vous êtes, il suffit de tester le signe avec respect d'un seul côté du triangle.

en supposant que vous avez calculé la pente m , ainsi que le X' pour les sommets triangulaires cisaillés et les coefficients des équations des côtés comme X = m Y + p , vous aurez besoin dans le pire des cas

• deux coordonner les comparaisons pour le classement vertical;
• éventuellement un ou deux abscisses comparaisons de la boîte englobante de rejet;
• calcul de X' = X - m Y ;
• une ou deux comparaisons avec les abscisses du triangle cisaillé;
• un signe de test X >< m' Y + p' , le côté de la cisaillé triangle.

Si vous connaissez les coordonnées des trois sommets et les coordonnées du point spécifique, alors vous pouvez obtenir la zone complète de la triangle. Ensuite, calculez la surface des trois segments du triangle (un point étant le point donné et les deux autres étant deux sommets du triangle). Ainsi, vous obtiendrez la zone des trois segments de triangle. Si la somme de ces zones est égale à la superficie totale (que vous avez obtenu auparavant), alors, le point devrait être à l'intérieur de la triangle. Sinon, le point n'est pas à l'intérieur du triangle. Cela devrait fonctionner. Si il y a des problèmes, laissez-moi savoir. Remercier.

autre fonction dans python , plus rapide que méthode du développeur (pour moi au moins) et inspiré par Cédric Dufour solution:

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  )

vous pouvez le tester avec:

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

il faut beaucoup pour tracer, mais cette grille est testé en 0,0195319652557 secondes contre 0.0844349861145 secondes de Code du développeur .

Enfin le Commentaire du code:

# 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

il y a des conditions de bord désagréables où un point est exactement sur le bord commun de deux triangles adjacents. Le point ne peut pas être dans les deux, ni dans aucun des triangles. Vous avez besoin d'une façon arbitraire mais cohérente d'attribuer le point. Par exemple, tracez une ligne horizontale à travers le point. Si la ligne croise l'autre côté du triangle à droite, le point est traité comme s'il se trouvait à l'intérieur du triangle. Si l'intersection est sur la gauche, le point est à l'extérieur.

si la ligne sur laquelle se trouve le point est horizontale, utiliser au-dessus/au-dessous.

si le point est situé sur le sommet commun de plusieurs triangles, utilisez le triangle avec le centre duquel le point forme le plus petit angle.

Plus de plaisir: trois points en ligne droite (zéro degré), par exemple (0,0) - (0,10) - (0,5). Dans un algorithme de triangulation, l '"oreille" (0,10) doit être détachée, le" triangle " généré étant le cas dégénéré d'une droite ligne.

je veux juste utiliser quelques mathématiques vectorielles simples pour expliquer la solution de coordonnées barycentriques qui Andreas avait donné, il sera beaucoup plus facile à comprendre.

1. la zone A est définie comme tout vecteur donné par s * v02 + t * v01, avec les conditions s >= 0 et t >= 0. Si tout point à l'intérieur du triangle v0, v1, v2, il doit être à l'intérieur de la Zone A.

2. Si la poursuite de restreindre s, et t appartient à [0, 1]. Nous obtenons la zone B qui contient tous les vecteurs de s * v02 + t * v01, avec la condition s, t appartient à [0, 1]. Il est intéressant de noter que la partie basse de la zone B est le miroir du Triangle v0, v1, v2. Le problème vient si nous pouvons donner certaines conditions de s, et t, à exclure encore plus la partie basse de la zone B.

3. supposons que nous donnons une valeur s, et que t change en [0, 1]. Sur le pic suivant, le point p se trouve sur le bord de v1v2. Tous les vecteurs de s * v02 + t * v01 qui sont le long de la ligne de tiret par la somme vectorielle simple. À v1v2 et dash line cross point p, nous avons:

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

nous obtenons 1 - s = tp, puis 1 = s + tp. Si t > tp, où 1 < s + t se trouve sur la ligne de double tiret, le vecteur est à l'extérieur du triangle, tout t <= tp, 1 >= s + t où est sur une seule ligne pointillée, le vecteur est à l'intérieur du triangle.

alors si nous donnons un s dans [0, 1], Le t correspondant doit rencontrer 1 >= s + t, pour le vecteur à l'intérieur du triangle.

donc finalement nous obtenons v = s * v02 + t * v01, v est à l'intérieur triangle avec condition s, t, s+t appartient à [0, 1]. Ensuite traduire point, nous avons

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

qui est la même que la solution D'Andreas pour résoudre le système d'équation p = p0 + s * (p1 - p0) + t * (p2 - p0), avec s, t, s + t appartiennent à [0, 1].

Voici une solution en python qui est efficace, documentée et contient trois unittests. C'est une qualité professionnelle et prête à être introduite dans votre projet sous la forme d'un module tel quel.

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)

il existe un test graphique optionnel supplémentaire pour l'algorithme ci-dessus afin de confirmer sa validité:

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

produisant le graphique suivant:

J'avais besoin d'un point dans le triangle, Vérifiez "environnement contrôlable" quand vous êtes absolument sûr que les triangles seront dans le sens des aiguilles d'une montre. Donc, j'ai pris Perro Azul 's jsfiddle et l'ai modifié comme suggéré par coproc pour de tels cas; également supprimé redondance 0.5 et 2 multiplications parce qu'ils sont juste s'annuler l'un l'autre.

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

Voici code C équivalent pour L'Unité:

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

code censément haute performance que J'ai adapté en JavaScript (article ci-dessous):

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) - pour triangles dans le sens contraire des aiguilles d'une montre

pointInTriangle (p, p0, p1, p2) - pour triangles dans le sens des aiguilles d'une montre

Look in jsFiddle (performance test included), il y a aussi le contrôle d'enroulement dans une fonction séparée http://jsfiddle.net/z7x0udf7/3 /

Inspiré par cette: http://www.phatcode.net/articles.php?id=459

la façon la plus facile et il fonctionne avec tous les types de triangles est de déterminer simplement les angles du point P A, B , C points angles. Si les angles sont plus grandes que 180.0 degré alors qu'il est à l'extérieur, si 180.0 alors il est sur la circonférence et si acos tricher sur vous et moins de 180.0 puis c'est à l'intérieur.Cherchez à comprendre http://math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Honnêtement, il est aussi simple que Simon P réponse de Steven cependant, avec cette approche, vous n'avez pas un contrôle solide sur la question de savoir si vous voulez que les points sur les bords du triangle soit inclus ou non.

Mon approche est un peu différente mais très basique. Considérez le triangle suivant:

pour avoir le point dans le triangle nous doivent remplir 3 conditions

1. L'angle ACE (vert) doit être plus petit que l'angle ACB (rouge)
2. de la BCE angle (bleu) doit être plus petit que l'angle ACB (rouge)
3. les points E et C doivent avoir le même signe lorsque leurs valeurs de x et de y sont appliquées à l'équation de la ligne |AB|.

dans cette méthode, vous avez le plein contrôle pour inclure ou exclure le point sur les bords individuellement. Si vous pouvez vérifier si un point est dans le triangle incluant seulement le |AC| edge par exemple.

donc ma solution en JavaScript serait la suivante;

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

Il ne peut pas être plus efficace que ce! Chaque côté d'un triangle peut avoir une position et une orientation indépendantes, donc trois calculs: l1, l2 et l3 sont certainement nécessaires impliquant deux multiplications chacune. Une fois que l1, l2 et l3 sont connus, résultat est juste quelques comparaisons de base et des opérations booléennes loin.

C'est le concept le plus simple pour déterminer si un point est à l'intérieur ou à l'extérieur du triangle ou sur un bras de triangle. la détermination d'un point est à l'intérieur d'un tringle par les déterminants

le code de travail le plus simple:

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

`

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

coordonnées cartésiennes presque parfaites converties à partir de coordonnées barycentriques sont exportés en *v (x) et *w (y) doubles. Les deux doublets d'exportation devraient avoir un * car * avant dans chaque cas, probablement: * v et * w Le Code peut être utilisé pour l'autre triangle, d'un quadrilatère. Par la présente signé a écrit seulement triangle abc du quad ABCD dans le sens des aiguilles d'une montre.

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

le point o est à L'intérieur du triangle ABC pour tester avec le deuxième triangle appeler cette fonction CDA direction, et les résultats doivent être corrects après *v=1-*v; et *w=1-*w; pour le quadrilatère

Puisqu'il n'y a pas de réponse JS,

Solution dans le sens des aiguilles d'une montre et dans le sens inverse des aiguilles d'une montre:

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 

}

modifier: il y avait une faute de frappe pour le calcul det ( cy - ay au lieu de cx - ax ), ceci est fixe.

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

j'utilise ici la même méthode que décrite ci-dessus: un point est à L'intérieur de ABC s'il est respectivement du "même" côté de chaque ligne AB, BC, CA.