Savoir si un point de l'espace est ou n'est pas dans un triangle (de l'espace lui aussi)

Soyez le premier à donner votre avis sur cette source.

Vue 5 573 fois - Téléchargée 378 fois

Description

Voila un principe que j'ai mis au point pour un travaille que je faisais sur DirectX.
Ce code marche pour tous les triangles dans l'espace.

Pour savoir si un point est dans un triangle il faut savoir qu'un triangle c'est trois point A, B, C definit dans E (l'espace).
Soit M le point que nous testerons.

Dans le triangle ABC on a deux repere (A;AB;AC) et (B;BC;BA), bon il y en a d'autre mais ceux la suffiront.

Si on exprime AM dans le repere (A;AB;AC), on aura
AM = alpha * AB + betha * AC
Si M est dans le secteur angulaire BAC, alpha et betha seront positif.
on refait pareille avec BM dans le repere (B;BC;BA) et si M est dans le secteur angulaire ABC alors les coeficients seront positifs

Si un point M se trouve dans le secteur angulair BAC et ABC alors M est dans le triangle ABC.

en bref, voici le code :

Source / Exemple :


Option Explicit

Public Type D3DVECTOR
    X As Double
    Y As Double
    z As Double
End Type
  
Public Function C3D(X, Y, z) As D3DVECTOR ' Pour tracer des vecteur et des
C3D.X = X: C3D.Y = Y: C3D.z = z ' points plus rapidement
End Function
  
Public Sub CoefficientVecteur(VecteurI As D3DVECTOR, VecteurJ As D3DVECTOR, _
            VecteurM As D3DVECTOR, Ret_CoefI, Ret_CoefJ, Ret_IsPossible As Boolean)
' Pour exprimer un vecteur en
' fonction de deux autres
  
Dim Alpha As Double, Betha   As Double ' Les coeficiants des vecteurs
Dim AB As D3DVECTOR, AC As D3DVECTOR, aM As D3DVECTOR
Dim A As Double, B   As Double, C As Double, D As Double, N As Byte
AB = VecteurI: AC = VecteurJ: aM = VecteurM
    If Not AB.X = 0 Then ' On ne peut pas prendre tous les
        A = aM.X / AB.X ' vecteurs dans n'importe quel sens
        B = -AC.X / AB.X ' Ici on doit diviser par AB.x il ne
        N = 1: GoTo CalculeBetha ' donc pas etre egal a Zéro.
    End If
  
' Ce qui donne Alpha = AM.x/AB.x - Betha * AC.X/AB.X
' Avec A = AM.x/AB.x et B = -AC.X/AB.X
  
CalculeAlphaABy:
    If Not AB.Y = 0 Then ' Même probleme ici pour AB.y
        A = aM.Y / AB.Y
        B = -AC.Y / AB.Y
        N = 2: GoTo CalculeBetha
    End If
  
' Ce qui donne Alpha = AM.y/AB.y - Betha * AC.y/AB.y
' Avec A = AM.y/AB.y et B = -AC.y/AB.y
  
CalculeAlphaABz:
    If Not AB.z = 0 Then ' Là egalement pour AB.z
        A = aM.z / AB.z
        B = -AC.z / AB.z
        N = 3: GoTo CalculeBetha
    End If
  
' Ce qui donne Alpha = AM.x/AB.x - Betha * AC.X/AB.X
' Avec A = AM.x/AB.x et B = -AC.X/AB.X
  
Ret_IsPossible = False
Exit Sub
' Si rien est possible et bien tant
' pis on quitte le sub et
' Ret_IsPossible aura la valeur FALSE
  
' On a exprimer Alpha en fonction de Betha, maintenant on termine le calcule
CalculeBetha:
    If Not N = 1 And Not (B * AB.X + AC.X = 0) Then ' Si on n'a pas exprimer Alpha en
        Betha = (aM.X - A * AB.X) / (B * AB.X + AC.X) ' fonction des X
        GoTo CalculeAlpha
    End If
    If Not N = 2 And Not (B * AB.Y + AC.Y = 0) Then ' Si on n'a pas exprimer Alpha en
        Betha = (aM.Y - A * AB.Y) / (B * AB.Y + AC.Y) ' fonction des y
        GoTo CalculeAlpha
    End If
    If Not N = 3 And Not (B * AB.z + AC.z = 0) Then ' Si on n'a pas exprimer Alpha en
        Betha = (aM.z - A * AB.z) / (B * AB.z + AC.z) ' fonction des z
        GoTo CalculeAlpha
    End If
    If N = 1 Then GoTo CalculeAlphaABy
' Si (B * AB.y + AC.y = 0) et que
' (B * AB.z + AC.z = 0) alors on
' essai de definir Alpha en fonction
' d'une autre variable
    If N = 2 Then GoTo CalculeAlphaABz ' Meme explication
    Exit Sub
CalculeAlpha: Alpha = A + B * Betha ' On definit Alpha
Ret_CoefI = Alpha: Ret_CoefJ = Betha ' On renvoit les valeurs
Ret_IsPossible = True ' Les coeficiants existes
End Sub
' Si les coeficiant exist ou pas on peut savoir si un point est coplanaire aux trois autres
  
  
' Pour cette Function Voir l'explication du code
Public Function IsPointInTRGL(TRGLpt1 As D3DVECTOR, TRGLpt2 As D3DVECTOR, _
                TRGLpt3 As D3DVECTOR, PtTest As D3DVECTOR) As Boolean
Dim V1 As D3DVECTOR, V2 As D3DVECTOR, V3 As D3DVECTOR, _
S1 As Byte, S2 As Byte, S3 As Byte, S4 As Byte, S5 As Byte, _
S6 As Byte, Ri As Single, Rj As Single, Possible As Boolean
V1 = CreerVecteur(TRGLpt1, TRGLpt2)
V2 = CreerVecteur(TRGLpt1, TRGLpt3)
V3 = CreerVecteur(TRGLpt1, PtTest)
CoefficientVecteur V1, V2, V3, Ri, Rj, Possible
If Not Possible Then Exit Function ' Si ce n'est pas possible, c'est que
' les points ne sont pas coplanaire donc pas dans le triangle
S1 = Sgn(Ri) + 1: S2 = Sgn(Rj) + 1
V1 = CreerVecteur(TRGLpt2, TRGLpt1)
V2 = CreerVecteur(TRGLpt2, TRGLpt3)
V3 = CreerVecteur(TRGLpt2, PtTest)
CoefficientVecteur V1, V2, V3, Ri, Rj, Possible
If Not Possible Then Exit Function
S3 = Sgn(Ri) + 1: S4 = Sgn(Rj) + 1
If S1 >= 1 Then
    If S2 >= 1 Then
        If S3 >= 1 Then
            If S4 >= 1 Then
                IsPointInTRGL = True
            End If
        End If
    End If
End If
End Function
  
Public Function CreerVecteur(Pt1 As D3DVECTOR, Pt2 As D3DVECTOR) As D3DVECTOR ' Pour crer un vecteur à
CreerVecteur = C3D(Pt2.X - Pt1.X, Pt2.Y - Pt1.Y, Pt2.z - Pt1.z) ' partir de deux points
End Function

Conclusion :


Pour l'utiliser il vaut mieu le mettre dans un module sinon il faut changer les public par des private mais bon ...
Ce code est entierement de moi.
Je n'ai vu aucun code qui definisait un point dans un triangle en fonction de vecteurs. S'ils existe je tien a m'en excuser.

Ce n'est qu'un petit code je prepare pour l'instant un moteur 3D genre TrueVision3D, cela ne va pas trop tarder mais d'ici quelque semaine je mettrais une ebauche quasi definitive (et gratuite contrairement a TrueVision3D) et entierement de moi.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
63
Date d'inscription
dimanche 5 novembre 2000
Statut
Membre
Dernière intervention
1 décembre 2013

oui c'est un erreur mais le truc c'est que ma fonction test si la progection du point est ou non dans le triangle.
Messages postés
14
Date d'inscription
mardi 15 mai 2007
Statut
Membre
Dernière intervention
20 décembre 2007

Excellent merci :-) !!
Je regarde ca de suite !
Messages postés
221
Date d'inscription
vendredi 30 novembre 2001
Statut
Membre
Dernière intervention
13 février 2010
4
j'ai généralisé un de mes programmes (2D) pour faire finalement la même chose que ce programme... l'intérêt est qu'il permet aussi de savoir si un point est dans une pyramide, et qu'il utilise une autre approche mathématique du problème (changement de base), tout ceci avec très peu de calculs.
(c'était en réponse à Oliv_Def, mon prog devrait fonctionner avec son problème)

http://www.vbfrance.com/codes/SAVOIR-SI-POINT-3D-EST-DANS-TRIANGLE-PYRAMIDE_42743.aspx

bonne prog à tous
Messages postés
14
Date d'inscription
mardi 15 mai 2007
Statut
Membre
Dernière intervention
20 décembre 2007

Désolé, mais j'ai executer ce code en testant non pas 0 pour Z mais une valeure autre et le point est toujours dans le triangle..

Bref sauf erreure de ma part, cela ne fonctionne pas en 3D :-(
Messages postés
6
Date d'inscription
mercredi 26 juillet 2006
Statut
Membre
Dernière intervention
11 février 2008

Bonjour à tous,

Je suis à la recherche d'un code similaire.

Explication:
Je capture des trames GPS et converti les coordonnées WGS(etrs89) en lambert72.
Ainsi j'obtiens des valeurs X, Y, H (ma position actuelle).

J'ai un fichier CSV qui contient des position X, Y, H et j'aimerait maintenant que mon code vérifie le contenu ce mon fichier et m?indique si mes coordonnées actuelle se situent dans un rayon de 2 mètres autour d'une des valeurs lu dans le fichiers CSV.

Si oui, alors BIP
Si non alors on continue.

Ceci est mon premier commentaire, alors si je ne m'y suis pas bien pris, veuillez m'en excuser.

Voici un exemple de position X,Y,Z voir l'application cconvert sur le site: www.ngi.be
Valeur de X=150120.001
Valeur de Y=170365.998
Valeur de H=65.345

conversion de:
datum:ETRS89
Elipsoide: GRS80
Projection:None
Coordinates:Geographic

<<<<< Conversion vers:
Datum: Belgian Datum72
Elipsiode: Hayford24
Projection: Lambert
Coordinates: Plane

En Vous remerciant pour votre aide et B-R-A-V-O pour VBfrance !!!
Afficher les 14 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.