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

258

Existe-t-il un moyen facile de déterminer si un point se trouve à l'intérieur d'un triangle? C'est 2D, pas 3D.

ET 0,618
la source
15
J'ai écrit un article complet sur le test du point dans le triangle. Il montre les méthodes barycentriques, paramétriques et basées sur les produits scalaires. Ensuite, il traite du problème de précision qui se produit lorsqu'un point se trouve exactement sur un bord (avec des exemples). Enfin, il expose une nouvelle méthode complète basée sur la distance point à bord. totologic.blogspot.fr/2014/01/… Profitez-en!
Logique du
1
Il convient de noter que toutes les méthodes discutées ici sont également valables dans l'espace 3D. Ils doivent juste être précédés d'une transformation de coordonnées (et d'une projection appropriée du point sur le plan du triangle). Un triangle est un objet bidimensionnel.
andreasdr
Pour une solution indépendante de l'ordre d'enroulement. Voici un violon qui fonctionne: jsfiddle.net/ibowankenobi/oex3pzq2
ibrahim tanyalcin
2
Je vote pour clore cette question car elle concerne les mathématiques plutôt que la programmation et est basée sur l'opinion (qu'est-ce qui est "facile" pour vous?).
TylerH

Réponses:

264

En général, l'algorithme le plus simple (et tout à fait optimal) vérifie de quel côté du demi-plan créé par les bords se trouve le point.

Voici quelques informations de haute qualité dans cette rubrique sur GameDev , y compris les problèmes de performances.

Et voici un code pour vous aider à démarrer:

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);
}
Kornel Kisielewicz
la source
12
Il est couramment utilisé en 2D. Les coordonnées barycentriques ont tendance à confondre les gens. De plus, étant donné les cooridats du triangle et le point de coordonnées, je ne suis pas sûr de l'efficacité de l'utilisation des barycentriques.
Kornel Kisielewicz
7
@Kornel La version barycentrique est également plus efficace en 2D. Votre solution a également le problème de générer un résultat différent pour les points situés exactement sur les bords du triangle, selon que le triangle est spécifié dans le sens horaire ou antihoraire.
Andreas Brinck
9
Pour mes besoins (la raison pour laquelle j'ai trouvé ce site), la réponse originale proposée par Kornel Kisielewicz est beaucoup plus efficace. Je travaille avec un écran LCD avec des coordonnées de taille BYTE et un microprocesseur très typique où la multiplication d'entiers est une instruction très rapide et la division est beaucoup, beaucoup plus lente. Les problèmes numériques sont également beaucoup plus petits, en raison de l'absence de division! tous les calculs sont exacts. Merci, Rick
4
La fonction signe () vous indique donc de quel côté du demi-plan (formé par la ligne entre p2 et p3) p1 est?
David Doria
1
Notez que si vous supposez un certain ordre des sommets (disons dans le sens inverse des aiguilles d'une montre), vous n'avez pas besoin de calculer tous ces déterminants tout le temps. En fait dans le meilleur des cas, 1 déterminant suffit pour constater que le point n'est pas à l'intérieur du triangle.
Thash
176

Résolvez le système d'équation suivant:

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

Le point pest à l'intérieur du triangle si 0 <= s <= 1et 0 <= t <= 1et s + t <= 1.

s, tet 1 - s - tsont appelées les coordonnées barycentriques du point p.

Andreas Brinck
la source
1
C'est plus rapide que la vérification en demi-plan, mais peut-être un peu plus difficile à saisir si vous êtes nouveau dans les coordonnées barycentriques.
Daniel Rikowski
8
Avec des sorties triviales (non implémentées) dans la méthode de Kornel, la sienne peut en fait beaucoup plus efficace que la vôtre. Si vous essayez de calculer s et t, vous comprendrez ce que je veux dire.
85
Je voulais tester cela, alors j'ai fait un jsfiddle, en m'appuyant sur la solution @andreasdr et le commentaire coproc
urraka
5
Optimisation: s + t <= 1implique s <= 1et t <= 1si s >= 0et t >= 0.
Thomas Eding
7
L'article totologic.blogspot.fr/2014/01/… proposé par @Logic post m'a aidé à mieux comprendre cette solution
Flayn
112

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 un système d'équations à chaque fois: il suffit d'évaluer la solution analytique. En utilisant la notation d' Andreas , 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);

Areaest la zone (signée) du triangle:

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

Évaluez simplement s, tet 1-s-t. Le point pest à l'intérieur du triangle si et seulement s'ils sont tous positifs.

EDIT: Notez que l'expression ci-dessus pour la zone suppose que la numérotation des nœuds triangulaires est dans le sens antihoraire. Si la numérotation est dans le sens horaire, cette expression renvoie une zone négative (mais avec une amplitude correcte). s>0 && t>0 && 1-s-t>0Cependant, le test lui-même ( ) ne dépend pas de la direction de la numérotation, car les expressions ci-dessus qui sont multipliées par 1/(2*Area)changent également de signe si l'orientation du nœud triangulaire change.

EDIT 2: Pour une efficacité de calcul encore meilleure, voir le commentaire de coproc ci-dessous (ce qui fait que si l'orientation des nœuds triangulaires (dans le sens horaire ou antihoraire) est connue à l'avance, la division par 2*Areadans les expressions pour set tpeut être évité). Voir aussi le code jsfiddle de Perro Azul dans les commentaires sous la réponse d' Andreas Brinck .

andreasdr
la source
6
C'est la résolution du système d'équations :)
Andreas Brinck
1
Oui, mon point est que toute critique de votre méthode basée sur le coût de calcul de la résolution du système d'équation n'est pas fondée, car cela ne doit pas être fait dans le cadre de l'algorithme.
andreasdr
13
L'efficacité peut être améliorée en ne divisant pas 2*Area, c'est-à-dire en calculant s´=2*|Area|*set t´=2*|Area|*t(si l'orientation des points - dans le sens horaire ou antihoraire - n'est pas connue, le signe de Areadoit être vérifié, bien sûr, mais sinon il ne peut même pas besoin d'être calculé), car pour le vérifier, s>0il suffit de le vérifier s´>0. Et au lieu de vérifier, 1-s-t>0il suffit de vérifier s´+t´<2*|Area|.
coproc
1
Je peux ajouter que si p0->p1->p2est dans le sens antihoraire en cartésien (qui est généralement dans le sens horaire en coordonnées d'écran ), le Areacalculé par cette méthode sera positif.
rhgb
1
@ user2600366 Lorsque vous vous déplacez le long de la limite du triangle dans la direction p0 -> p1 -> p2 -> p0, et ainsi de suite, vous aurez l'intérieur du triangle toujours à droite ou toujours à gauche. Dans le premier cas, la numérotation est dans le sens horaire, dans le second cas, elle est anti-horaire.
andreasdr
47

J'ai écrit ce code avant une dernière tentative avec Google et trouver cette page, alors j'ai pensé le partager. Il s'agit essentiellement d'une version optimisée de la réponse de Kisielewicz. J'ai également examiné la méthode barycentrique, mais à en juger par l'article de Wikipédia, j'ai du mal à voir comment elle est plus efficace (je suppose 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 des bords en fonction de l'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 termes, l'idée est la suivante: le point s est-il à gauche ou à droite des lignes AB et AC? Si c'est vrai, ça ne peut pas être à l'intérieur. Si elle est fausse, c'est au moins à l'intérieur des "cônes" qui remplissent la condition. Maintenant que nous savons qu'un point à l'intérieur d'un trigone (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, il est impossible qu'ils soient à l'intérieur, sinon ils doivent être à l'intérieur.

Certains mots-clés dans les calculs sont les demi-plans de ligne et le déterminant (produit croisé 2x2). Peut-être qu'une manière plus pédagogique est probablement de le considérer comme un point se trouvant à l'intérieur même s'il est du même côté (gauche ou droite) pour chacune des lignes AB, BC et CA. Cependant, la méthode ci-dessus semblait mieux adaptée à une certaine optimisation.

John Bananas
la source
2
Ce test est environ 140-180% plus rapide que le premier fourni (merci à vous deux btw :). J'ai exécuté le code ici: paste.ubuntu.com/p/k5w7ywH4p8 en utilisant le moteur nodejs v8 avec les optimisations désactivées et j'ai obtenu les résultats suivants:: w! Node -p --minimal test1: 114.852ms test2: 64.330ms test1: 115.650ms test2: 63.491ms test1: 117.671ms test2: 65.353ms test1: 119.146ms test2: 63.871ms test1: 118.271ms test1: 118.670ms test2: 63.352ms
surgemcgee
@surgemcgee pourquoi voudriez-vous l'exécuter sans optimisations? N'est-ce pas plus éloigné de la réalité alors?
xuiqzy
@xuiqzy Eh bien, mon programme contient les deux solutions différentes. Je n'ai pas encore administré la méthode la plus rapide pour le faire. Peut-être que ce commentaire devrait être supprimé et remplacé par mes travaux terminés à ce sujet ..
surgemcgee
33

Version C # de la méthode barycentrique publiée par andreasdr et Perro Azul. Notez que le calcul d'aire peut être évité si set tont des signes opposés. J'ai vérifié le comportement correct avec un test unitaire assez approfondi.

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

[ modifier ]
accepté la modification suggérée par @Pierre; voir les commentaires

Glenn Slayden
la source
La solution avec l'instruction if se termine pour les points triangulaires dans le sens horaire et antihoraire.
Luke Dupin
@LukeDupin Je ne suis pas sûr de comprendre votre commentaire. Cette réponse fonctionne comme affichée pour toute commande fournie des 3 points.
Glenn Slayden
12

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 avec précision avec des entiers, en supposant qu'aucun débordement. Il fonctionnera également avec des triangles dans le sens horaire et antihoraire. Cela ne fonctionnera pas avec les triangles colinéaires (mais vous pouvez le vérifier 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 triangulaires, elle est donc probablement moins cohérente que la version demi-plan de bord de Kornel Kisielewicz, en raison d'erreurs d'arrondi à virgule flottante.

Crédit: J'ai créé le code ci-dessus à partir de l'article de Wikipedia sur les coordonnées barycentriques.

Adam Gawne-Cain
la source
Agréable ! Il peut même être amélioré pour utiliser les tuples Point3f / Point2f de javax.vecmath, afin de mieux gérer l'entrée de données.
Alex Byrth
10

Un moyen simple consiste à:

trouver les vecteurs reliant le point à chacun des trois sommets du triangle et additionner les angles entre ces vecteurs. Si la somme des angles est de 2 * pi, le point se trouve à l'intérieur du triangle.

Deux bons sites qui expliquent les alternatives sont:

blackpawn et wolfram

Simon P Stevens
la source
3
Hum, cette méthode n'est pas exactement efficace et est très sujette aux erreurs numériques ...
Kornel Kisielewicz
C'est tout le contraire, c'est très inefficace :-) Mais ce n'est qu'une manière simple, c'est facile à mettre en œuvre. Pouvez-vous donner un exemple d'erreur numérique que cela provoquerait?
Simon P Stevens
Bien que cela me semble simplement être la meilleure des réponses dans ce sujet, je suppose que les points sur les bords du triangle sont calculés pour être inclus dans le triangle et vous n'avez pas de contrôle solide à ce sujet.
Redu
vérifier si c'est exactement 2pi est numériquement impossible étant donné que pi est irrationnel. Cependant, il vous suffit de vérifier si les angles correspondent à quelque chose de plus grand que pi.
lonewarrior556
10

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

  • ne pas distribuer la multiplication sur les termes entre parenthèses
  • éviter de calculer plusieurs fois les mêmes termes en les stockant
  • réduire les comparaisons (comme l'ont 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 ou l'essayer en cliquant sur "Exécuter l'extrait de code" ci-dessous

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>

Menant à:

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

Cela se compare assez bien à la solution Kornel Kisielewicz (25 rappels, 1 stockage, 15 soustractions, 6 multiplications, 5 comparaisons), et pourrait être encore mieux si une détection dans le sens horaire / antihoraire est nécessaire (ce qui prend 6 rappels, 1 ajout, 2 soustractions , 2 multiplications et 1 comparaison en soi, en utilisant le déterminant de la solution analytique, comme le souligne rhgb ).

Cédric Dufour
la source
Belle solution. Je pense que c'est assez équivalent à ma dernière approche ici sur MSE: math.stackexchange.com/questions/51326/…
Jack D'Aurizio
Je viens de tester le code tel quel et cela ne fonctionne pas pour moi (exemple p -4.69317198, -6.99191951 p0 -7.05846786 0.596718192 p1 -6.8703599 -2.36565161 p2 -4.69317198, -6.99191951)
Giovanni Funchal
@GiovanniFunchal Strange, votre exemple fonctionne pour moi, à la fois dans les définitions jsfiddle (remplacer les définitions initiales "point" et "triangle") et dans mon implémentation Python locale. Problèmes de précision numérique (essayez de supprimer certaines décimales)?
Cédric Dufour
1
Votre semble le plus rapide dans mon test: jsfiddle.net/eyal/gxw3632c/27 . La différence entre toutes les méthodes est cependant assez petite.
Eyal
Essayez le triangle (-1, -1), (1, -1), (0,1) et le point (0, -1). Renvoie false alors qu'il devrait retourner vrai car s (2) + t (2)> d (2). Quelque chose ne va pas avec les mathématiques sur les bords du triangle, semble-t-il, car le point p est juste à la frontière entre p0 et p1 et ce n'est pas une simple question de convertir un <en un <= ou quelque chose comme ça.
devnullicus
5

Ce que je fais, c'est précalculer les trois faces normales,

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

  • en 2D en échangeant simplement les composants et en les annulant,

puis à l'intérieur / à l'extérieur pour n'importe quel côté, c'est quand un produit scalaire du côté normal et du vecteur sommet à point change de signe. Répétez l'opération pour les deux autres côtés (ou plus).

Avantages:

  • beaucoup est précalculé, donc idéal pour les tests en plusieurs points sur le même triangle.

  • rejet précoce du cas commun de points plus extérieurs qu'intérieurs. (également si la distribution des points est pondérée d'un côté, vous pouvez tester ce côté en premier.)

psiman
la source
5

Voici une implémentation Python efficace :

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:

entrez la description de l'image ici

Développeur
la source
Je n'ai pas pu faire ce travail, par exemple pour le point dans le triangle [(0,0), (3,0), (3,4)], ni les points (1,1) ou (0 , 0) test positif. J'ai essayé avec des points triangulaires dans le sens horaire et anti-horaire.
ThorSummoner
3

Si vous recherchez la vitesse, voici une procédure qui pourrait vous aider.

Trier les sommets triangulaires sur leurs ordonnées. Cela prend au pire trois comparaisons. Soit Y0, Y1, Y2 les trois valeurs triées. En dessinant trois horizontales à travers eux, vous divisez l'avion en deux demi-plans et deux dalles. 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 autres comparaisons. Comme vous le voyez, un rejet rapide est obtenu pour les points en dehors de la "dalle de délimitation".

En option, vous pouvez fournir un test sur les abscisses pour un rejet rapide à gauche et à droite (X <= X0' or X >= X2' ). Cela implémentera un test de boîte de délimitation rapide en même temps, mais vous devrez également trier les abscisses.

Finalement, vous devrez calculer le signe du point donné par rapport aux deux côtés du triangle qui délimitent la dalle pertinente (supérieure ou inférieure). 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 de i, j, k combinaisons (il y en a six, sur la base du résultat du genre) est hors de portée de cette réponse et «laissée comme exercice au lecteur»; pour plus d'efficacité, ils doivent être codés en dur.

Si vous pensez que cette solution est complexe, notez qu'elle implique principalement des comparaisons simples (dont certaines peuvent être précalculées), plus 6 soustractions et 4 multiplications en cas d'échec du test de la boîte englobante. Ce dernier coût est difficile à battre car dans le pire des cas, vous ne pouvez pas éviter de comparer le point de test avec deux côtés (aucune méthode dans les autres réponses n'a un coût inférieur, certains l'aggravent, comme 15 soustractions et 6 multiplications, parfois des divisions).

MISE À JOUR: Plus rapide avec une transformation de cisaillement

Comme expliqué ci-dessus, vous pouvez rapidement localiser le point à l'intérieur de l'une des quatre bandes horizontales délimitées par les trois ordonnées du sommet, en utilisant deux comparaisons.

Vous pouvez éventuellement effectuer un ou deux tests X supplémentaires pour vérifier l'insidicité de la zone de délimitation (lignes pointillées).

Considérons alors la transformée de "cisaillement" donnée par X'= X - m Y, Y' = Y, où mest la pente DX/DYdu bord le plus haut. Cette transformation rendra ce côté du triangle vertical. Et puisque vous savez de quel côté de l'horizontale moyenne vous vous trouvez, il suffit de tester le signe par rapport à un seul côté du triangle.

entrez la description de l'image ici

En supposant que vous ayez précalculé la pente m, ainsi que les X'sommets du triangle cisaillé et les coefficients des équations des côtés X = m Y + p, vous aurez besoin dans le pire des cas

  • deux comparaisons ordonnées pour la classification verticale;
  • éventuellement une ou deux comparaisons d'abscisses pour le rejet de la boîte englobante;
  • calcul de X' = X - m Y;
  • une ou deux comparaisons avec les abscisses du triangle cisaillé;
  • un test de signe X >< m' Y + p'contre le côté pertinent du triangle cisaillé.
Yves Daoust
la source
3

Si vous connaissez les coordonnées des trois sommets et les coordonnées du point spécifique, vous pouvez obtenir l'aire du triangle complet. Ensuite, calculez l'aire des trois segments du triangle (un point étant le point donné et les deux autres étant deux sommets quelconques du triangle). Ainsi, vous obtiendrez l'aire des trois segments triangulaires. Si la somme de ces zones est égale à la surface totale (que vous avez obtenue précédemment), alors le point doit être à l'intérieur du triangle. Sinon, le point n'est pas à l'intérieur du triangle. Cela devrait fonctionner. S'il y a des problèmes, faites-le moi savoir. Je vous remercie.

ihayet
la source
3

Autre fonction en python , plus rapide que la méthode du développeur (pour moi du moins) et inspirée de la solution de 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  )

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

Cela prend beaucoup de temps à tracer, mais cette grille est testée en 0,0195319652557 secondes contre 0,0844349861145 secondes du 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
Ramiro RC
la source
Cette fonction ne fonctionne pas. Donnez ptInTriang([11,45],[45, 45],[45, 45] ,[44, 45])et il reviendra truebien que ce soit faux
Code Pape
3

Puisqu'il n'y a pas de réponse JS, la solution
Clockwise & Counter-Clockwise:

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}

EDIT: il y avait une faute de frappe pour le calcul de det ( cy - ayau lieu de cx - ax), cela est fixe.

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>

entrez la description de l'image ici

J'utilise ici la même méthode que celle 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.

exemple d'inclusion de triangle

Joseph Merdrignac
la source
J'ai fatigué ce code et ça ne marche pas. Elle renvoie toujours False.
xApple
hmmm ... vous avez probablement fait une erreur. Voici un violon avec cette fonction en cours d'exécution: jsfiddle.net/jniac/rctb3gfL
Joseph Merdrignac
j'ai vu votre réponse Python, nous utilisons la même méthode, si j'utilise une ligne de plus ( let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)), c'est pour déterminer l'ordre d'enroulement du triangle, donc la méthode fonctionnera avec les triangles CW et CCW (voir jsFiddle).
Joseph Merdrignac
1
hm j'ai fait une erreur, j'ai écrit: let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)au lieu de let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)c'est résolu, merci d'avoir signalé
Joseph Merdrignac
2

Je veux juste utiliser des mathématiques vectorielles simples pour expliquer la solution de coordonnées barycentriques qu'Andreas avait donnée, elle sera beaucoup plus facile à comprendre.

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

entrez la description de l'image ici

  1. Si restreindre davantage 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 convient de noter que la partie basse de la zone B est le miroir du triangle v0, v1, v2. Le problème vient de si nous pouvons donner une certaine condition de s, et t, pour exclure davantage la partie basse de la zone B.

entrez la description de l'image ici

  1. Supposons que nous donnons une valeur s, et t change dans [0, 1]. Dans l'image suivante, le point p est sur le bord de v1v2. Tous les vecteurs de s * v02 + t * v01 qui sont le long de la ligne de tiret par simple somme vectorielle. À v1v2 et au point de croisement de la ligne pointillée p, nous avons:

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

on obtient 1 - s = tp, puis 1 = s + tp. Si tout t> tp, dont 1 <s + t où est sur la double ligne de tiret, le vecteur est en dehors du triangle, tout t <= tp, qui 1> = s + t où est sur la ligne de tiret simple, le vecteur est à l'intérieur du triangle.

Alors si nous avons donné n'importe quel s dans [0, 1], le t correspondant doit rencontrer 1> = s + t, pour le vecteur à l'intérieur du triangle.

entrez la description de l'image ici

Donc, finalement, nous obtenons v = s * v02 + t * v01, v est à l'intérieur du triangle avec la condition s, t, s + t appartient à [0, 1]. Ensuite, traduisez au 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].

Orup
la source
Vous pouvez simplement dire que vous utilisez le cadre local défini par les trois sommets pour que les côtés deviennent s = 0, t = 0 et s + t = 1. La transformation des coordonnées affines est une opération bien connue de l'algèbre linéaire.
Yves Daoust
2

Voici une solution en python qui est efficace, documentée et contient trois unittests. Il est de qualité professionnelle et prêt à être intégré 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 supplémentaire facultatif pour l'algorithme ci-dessus pour 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")

Produire le graphique suivant:

Testez la fonction point_in_triangle

xApple
la source
1

Il existe des conditions de bord embêtantes 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 manière arbitraire mais cohérente d'attribuer le point. Par exemple, tracez une ligne horizontale passant par le point. Si la ligne coupe avec l'autre côté du triangle à droite, le point est traité comme s'il était à l'intérieur du triangle. Si l'intersection est à gauche, le point est à l'extérieur.

Si la ligne sur laquelle se trouve le point est horizontale, utilisez dessus / dessous.

Si le point se trouve sur le sommet commun de plusieurs triangles, utilisez le triangle dont le centre forme le point le plus petit.

Plus amusant: trois points peuvent être 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 coupée, le "triangle" généré étant le cas dégénéré d'une ligne droite.

Pierre
la source
1

Il s'agit du concept le plus simple pour déterminer si un point se trouve à l'intérieur ou à l'extérieur du triangle ou sur un bras d'un triangle.

La détermination d'un point est à l'intérieur d'un triangle par des déterminants:

La détermination d'un point est à l'intérieur d'un triangle par des 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)
Shaon Majumder
la source
0

La manière la plus simple et qui fonctionne avec tous les types de triangles est simplement de déterminer les angles des angles des points P, A, B et C. Si l' un des angles sont plus grands que 180,0 degrés , alors il est à l' extérieur, si 180,0 alors il est sur la circonférence et si ACOS triche sur vous et moins de 180,0 alors il est inside.Take un regard pour comprendre http: //-math physique -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Bela Bessenyei
la source
0

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

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

entrez la description de l'image ici

Pour avoir le point dans le triangle, nous devons satisfaire 3 conditions

  1. L'angle ACE (vert) doit être inférieur à l'angle ACB (rouge)
  2. L'angle ECB (bleu) doit être inférieur à l'angle ACB (rouge)
  3. Le point E et le point C doivent avoir le même signe lorsque leurs valeurs x et y sont appliquées à l'équation de | AB | ligne.

Dans cette méthode, vous avez le contrôle total pour inclure ou exclure le point sur les bords individuellement. Vous pouvez donc vérifier si un point est dans le triangle comprenant uniquement le | AC | bord 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));

Redu
la source
0
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);
}

Ça ne peut pas être plus efficace que ça! Chaque côté d'un triangle peut avoir une position et une orientation indépendantes, d'où trois calculs: l1, l2 et l3 sont définitivement nécessaires impliquant 2 multiplications chacun. Une fois l1, l2 et l3 connus, le résultat n'est qu'à quelques comparaisons de base et opérations booléennes.

Ajay Anand
la source
0

Code supposément performant 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 les triangles antihoraires
  • pointInTriangle(p, p0, p1, p2) - pour les triangles dans le sens horaire

Regardez dans jsFiddle (test de performance inclus), il y a aussi une vérification de l'enroulement dans une fonction séparée. Ou appuyez sur "Exécuter l'extrait de code" ci-dessous

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

document.querySelector('#performance').addEventListener('click', _testPerformance);

test();

function test() {
    var result = checkClockwise(triangle.a, triangle.b, triangle.c) ? pointInTriangle(point, triangle.a, triangle.c, triangle.b) : pointInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function _testPerformance () {
	var px = [], py = [], p0x = [], p0y = [], p1x = [], p1y = [], p2x = [], p2y = [], p = [], p0 = [], p1 = [], p2 = [];
    
	for(var i = 0; i < 1000000; i++) {
    p[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p0[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p1[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p2[i] = {x: Math.random() * 100, y: Math.random() * 100};
  }
  console.time('optimal: pointInTriangle');
  for(var i = 0; i < 1000000; i++) {
    pointInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('optimal: pointInTriangle');

  console.time('original: ptInTriangle');
  for(var i = 0; i < 1000000; i++) {
  	ptInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('original: ptInTriangle');
}

function pointInTriangle (p, p0, p1, p2) {
	return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return (s + t) < A;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<button id="performance">Run performance test (open console)</button>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

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

Pawel
la source
-1
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;
} 

les coordonnées cartésiennes presque parfaites converties en barycentrique sont exportées dans les doubles * v (x) et * w (y). Les deux doubles d'exportation devraient avoir un caractère * avant dans tous les cas, probablement: * v et * w Le code peut également être utilisé pour l'autre triangle d'un quadrilatère. Signé par les présentes a écrit uniquement le triangle abc du quadruple abcd dans le sens horaire.

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

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

QuestionFeed
la source
-1

J'avais besoin de vérifier les triangles dans un "environnement contrôlable" lorsque vous êtes absolument sûr que les triangles seront dans le sens des aiguilles d'une montre. Donc, j'ai pris le jsfiddle de Perro Azul et l'ai modifié comme suggéré par coproc pour de tels cas; également supprimé les multiplications redondantes de 0,5 et 2, car elles s'annulent simplement.

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

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = {
    x: W / 2,
    y: H / 2
};
var triangle = randomTriangle();

$("canvas").click(function (evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function (evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);

    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    while (true) {
        var result = {
            a: {
                x: rand(0, W),
                y: rand(0, H)
            },
            b: {
                x: rand(0, W),
                y: rand(0, H)
            },
            c: {
                x: rand(0, W),
                y: rand(0, H)
            }
        };
        if (checkClockwise(result.a, result.b, result.c)) return result;
    }
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>

<pre id="result"></pre>

<canvas width="500" height="500"></canvas>

Voici le code C # équivalent pour 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;
}
Maxim Kamalov
la source
-3

L'une des façons les plus simples de vérifier si l'aire formée par les sommets des triangles (x1, y1), (x2, y2), (x3, y3) est positive ou non.

La superficie peut être calculée par la formule:

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

ou le code python peut être écrit comme suit:

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])]
ravi tanwar
la source