Savoir si un point (3d) est dans un triangle / pyramide
0/5 (8 avis)
Vue 7 401 fois - Téléchargée 450 fois
Description
Voici la généralisation directe de ma source pour le cas 2D. Je poste cette source car plusieurs messages circulaient sur ce sujet
L'interface est très rudimentaire, le but étant d'utiliser les fonctions dans vos programmes. Ce code est donc fait uniquement pour comprendre comment ça marche, alors n'essayez pas de rentrer autre chose que des chiffres dans les cases de coordonnées, je n'ai fait aucun contrôle de type de données!
Pour savoir si un point P (3D) se trouve dans un triangle ABC, il existe une autre méthode que celle donnée ici:
on projette le triangle ABC et le point P sur les plans XY, XZ et YZ (càd qu'on "oublie" une composante à chaque fois), et on vérifie avec le programme 2D (calculs légèrement plus simples) que la projection de P se trouve les 3 fois à l'intérieur de la projection du triangle.
Source / Exemple :
' tout se trouve dans le zip, mais voici ici la fonction principale du programme
' entrée des données
For i = 1 To 3
A(i) = CDbl(txtA(i - 1).Text)
B(i) = CDbl(txtB(i - 1).Text)
C(i) = CDbl(txtC(i - 1).Text)
D(i) = CDbl(txtD(i - 1).Text)
P(i) = CDbl(txtP(i - 1).Text) - A(i)
u(i) = B(i) - A(i)
v(i) = C(i) - A(i)
w(i) = D(i) - A(i)
Next
' pour le triangle, le vecteur w est choisi (arbitrairement) comme u x v
If optType(0).Value Then
w(1) = u(2) * v(3) - u(3) * v(2)
w(2) = u(3) * v(1) - u(1) * v(3)
w(3) = u(1) * v(2) - u(2) * v(1)
End If
' matrice de changement de base
For i = 1 To 3
M(i, 1) = u(i)
M(i, 2) = v(i)
M(i, 3) = w(i)
Next
Inverse M, MInv
' Q = nouvelles coordonnées du point P
Q(1) = MInv(1, 1) * P(1) + MInv(1, 2) * P(2) + MInv(1, 3) * P(3)
Q(2) = MInv(2, 1) * P(1) + MInv(2, 2) * P(2) + MInv(2, 3) * P(3)
Q(3) = MInv(3, 1) * P(1) + MInv(3, 2) * P(2) + MInv(3, 3) * P(3)
' vérification de la position du point P
If optType(0).Value Then Resultat = 2 Else Resultat = 4
If Q(1) >= -DELTA And Q(2) >= -DELTA And Q(3) >= -DELTA And _
Q(1) + Q(2) + Q(3) <= 1 + DELTA Then
If optType(1).Value Or Abs(Q(3)) < DELTA Then
Resultat = Resultat - 1
End If
End If
' affichage du résultat
lblResultat.Visible = True
Select Case Resultat
Case 1: strResultat = "le point P se trouve dans le triangle ABC"
Case 2: strResultat = "le point P ne se trouve pas dans le triangle ABC"
Case 3: strResultat = "le point P se trouve dans la pyramide ABCD"
Case 4: strResultat = "le point P ne se trouve pas dans la pyramide ABCD"
End Select
lblResultat.Caption = strResultat
Conclusion :
L'interface est très rudimentaire, le but étant d'utiliser les fonctions dans vos programmes. Ce code est donc fait uniquement pour comprendre comment ça marche, alors n'essayez pas de rentrer autre chose que des chiffres dans les cases de coordonnées, je n'ai fait aucun contrôle de type de données!
Pour savoir si un point P (3D) se trouve dans un triangle ABC, il existe une autre méthode que celle donnée ici:
on projette le triangle ABC et le point P sur les plans XY, XZ et YZ (càd qu'on "oublie" une composante à chaque fois), et on vérifie avec le programme 2D (calculs légèrement plus simples) que la projection de P se trouve les 3 fois à l'intérieur de la projection du triangle.
Codes Sources
A voir également
- Savoir si un point (3d) est dans un triangle / pyramide
- Triangle arrondi - Forum Graphisme/design
- L'exception point d'arret un point d'arret a été atteint ✓ - Forum C
- Construction d'une pyramide france ioi ✓ - Forum Python
- Regex point ✓ - Forum Regex
- Point d'interrogation ✓ - Forum Java
18 mai 2007 à 18:51
18 mai 2007 à 20:34
Tu parles d'un point défini en 3D, et d'un triangle, figure 2D (sinon, ça s'appellerait une pyramide).
Essaye d'éclaircir ce dilèmne, stp
19 mai 2007 à 16:35
dilèmne résolu Jack?
6 juin 2007 à 23:57
- elle marche sous directX8
- elle est rapide
- permet une marge d'erreur ca un point ne peut pas exactement etre dans un plan pas en prog du moins
' Description : Exprime V dans le repere (O,i,j,k)
Public Sub FZ3DVec3Coords( _
VOut As D3DVECTOR, _
O As D3DVECTOR, I As D3DVECTOR, J As D3DVECTOR, k As D3DVECTOR, _
v As D3DVECTOR)
Dim matEq As D3DMATRIX, matSlv As D3DMATRIX
With matEq
.m11 I.X: .m12 J.X: .m13 = k.X: .m14 = 0
.m21 I.Y: .m22 J.Y: .m23 = k.Y: .m24 = 0
.m31 I.z: .m32 J.z: .m33 = k.z: .m34 = 0
.m41 0: .m42 0: .m43 = 0: .m44 = 1
End With
With matSlv
.m11 = v.X - O.X
.m21 = v.Y - O.Y
.m31 = v.z - O.z
.m41 = 0
End With
D3DXMatrixInverse matEq, 1, matEq
D3DXMatrixMultiply matSlv, matEq, matSlv
VOut.X = matSlv.m11
VOut.Y = matSlv.m21
VOut.z = matSlv.m31
End Sub
Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)
Dim A As D3DVECTOR, B As D3DVECTOR, C As D3DVECTOR
Dim v1 As D3DVECTOR, v2 As D3DVECTOR, v3 As D3DVECTOR, v As D3DVECTOR
Dim VTest As D3DVECTOR
A.X 500: A.Y 0: A.z = 0
B.X 6000: B.Y 500: B.z = 0
C.X 500: C.Y 7000: C.z = 10
VTest.X X: VTest.Y Y: VTest.z = 10
Cls
Line (A.X, A.Y)-(B.X, B.Y)
Line (A.X, A.Y)-(C.X, C.Y)
Line (C.X, C.Y)-(B.X, B.Y)
Me.DrawWidth = 5
PSet (VTest.X, VTest.Y), vbYellow
Me.DrawWidth = 1
D3DXVec3Subtract v1, B, A
D3DXVec3Subtract v2, C, A
D3DXVec3Cross v3, v1, v2
D3DXVec3Normalize v3, v3
FZ3DVec3Coords v, A, v1, v2, v3, VTest
If (v.X + v.Y) <= 1 And v.X >= 0 And v.X <= 1 And v.Y > 0 And v.Y < 1 Then
If Abs(v.z) < 0.001 Then
Caption = "Pt dans le triangle"
' le point est dans le triangle d'une distance < 0.001
Else
Caption = "progection dans triangle, d'une distance au plan de " + CStr(Abs(v.z))
End If
Else
Caption = "Point en dehors du triangle, d'une distance au plan de " + CStr(Abs(v.z))
End If
End Sub
' si quelqu'un a envie de la faire marcher il faut d'abord referencer la DLL de DirectX8.
7 juin 2007 à 00:35
- elle marche sous directX8
mon prog aussi car il n'a même pas besoin de l'utiliser!
- elle est rapide
j'attends un test comparatif entre mon prog et celui de directX8, et sans être chauvin, comme il n'y a que très peu d'opérations avec des matrices, je suis sûr qu'il vaut mieux utiliser mon prog avec quelques opérations très basiques plutôt que de charger toute l'artillerie directX...
- permet une marge d'erreur ca un point ne peut pas exactement etre dans un plan pas en prog du moins
c'est exactement ce que j'ai fait avec la variable "DELTA", qui dans ton cas particulier vaut 0.001 (entre nous on peut quand même travailler avec un peu plus de précision, du genre 10^(-6)...)
bref, de toute façon c'est sympa de montrer qu'on peut utiliser directX, mais j'ajouterais quand même 2 arguments pour ne pas le faire:
1) il n'y a quasiment pas d'opérations matricielles pour ce problème, et pour des choses si simples je doute que directX apporte quelque chose
2) il me semble que ce prog aide plus pour la compréhension mathématique d'un problème donné, plutôt que pour l'utilisation à outrance dans un programme donné (quel programme aurait besoin de savoir 10'000 fois par sec. si un point est dans un triangle ou non?). Ainsi, ne faire recours qu'au fonction de base de VB permet de TOUT comprendre, ce qui n'est pas forcément le cas avec l'appel de librairies externes
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.