Problème des polygones jointifs

Signaler
Messages postés
252
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
29 juin 2013
-
Messages postés
252
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
29 juin 2013
-
Bonjour,
Soit un espace plan contenant un grand nombre de polygones quelconques jointifs.
Quelqu'un aurait-il déjà trouvé une méthode élégante et rapide pour déterminer si deux polygones pris au hasard sont ou non jointifs?
Jacques13

9 réponses

Messages postés
1447
Date d'inscription
jeudi 2 novembre 2000
Statut
Membre
Dernière intervention
23 septembre 2007
2
Personellement je sais pas mais fais une recherche en tapant 3D+Polygones peut-être.

Redman
Messages postés
3140
Date d'inscription
vendredi 14 mai 2004
Statut
Membre
Dernière intervention
11 mars 2019
31
Salut,

le principe c'est de créer une région pour chaque polygone et de regarder

si l'intersection est vide.

c'est pour VB6





Const RGN_AND = 1

Const RGN_OR = 2

Const RGN_XOR = 3

Const RGN_DIFF = 4

Const RGN_COPY = 5



Const NULLREGION = 1

Const COMPLEXREGION = 3

Const SIMPLEREGION = 2

Const ERRORAPI = 0



Const ALTERNATE = 1

Const WINDING = 2

Const BLACKBRUSH = 4



Private Type COORD

x As Long

y As Long

End Type



Private Declare Function CreatePolygonRgn Lib "gdi32" (lpPoint As Any,
ByVal nCount As Long, ByVal nPolyFillMode As Long) As Long

Private Declare Function Polygon Lib "gdi32" (ByVal hdc As Long, lpPoint As Any, ByVal nCount As Long) As Long

Private Declare Function FillRgn Lib "gdi32" (ByVal hdc As Long, ByVal hRgn As Long, ByVal hBrush As Long) As Long

Private Declare Function GetStockObject Lib "gdi32" (ByVal nIndex As Long) As Long

Private Declare Function DeleteObject Lib "gdi32" (ByVal hObject As Long) As Long

Private Declare Function CombineRgn Lib "gdi32" (ByVal hDestRgn As
Long, ByVal hSrcRgn1 As Long, ByVal hSrcRgn2 As Long, ByVal
nCombineMode As Long) As Long



Private Sub Command1_Click()

Dim poly() As COORD

Dim hRgn1 As Long

Dim hRgn2 As Long

Dim hBrush As Long

Dim Rep As Long



Me.Cls

Me.ScaleMode = vbPixels



ReDim poly(3)

poly(0).x = 10

poly(0).y = 10

poly(1).x = 100

poly(1).y = 30

poly(2).x = 200

poly(2).y = 100

poly(3).x = 100

poly(3).y = 200

Polygon Me.hdc, poly(0), 4

hRgn1 = CreatePolygonRgn(poly(0), 4, ALTERNATE)



ReDim poly(4)

poly(0).x = 200

poly(0).y = 20

poly(1).x = 300

poly(1).y = 100

poly(2).x = 300

poly(2).y = 200

poly(3).x = 200

poly(3).y = 250

poly(4).x = 100

poly(4).y = 100

Polygon Me.hdc, poly(0), 5

hRgn2 = CreatePolygonRgn(poly(0), 5, ALTERNATE)



Rep = CombineRgn(hRgn1, hRgn1, hRgn2, RGN_AND)

If Rep = NULLREGION Then

MsgBox "aucun point d'intersection"

Else

hBrush = GetStockObject(BLACKBRUSH)

FillRgn Me.hdc, hRgn1, hBrush

End If



DeleteObject hRgn1

DeleteObject hRgn2



End Sub


Daniel
Messages postés
252
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
29 juin 2013

Salut Daniel,
J'avais pensé à une solution purement analytique, mais je vois que tu proposes une approche géométrique "tactile".
Cette voie me parait intéressante, je vais tester.
En tout état de cause, je te remercie beaucoup pour le coup de main.
Jacques13
Messages postés
252
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
29 juin 2013

J'ai essayé ta technique qui est très astucieuse mais elle permet seulement de savoir si 2 polygones sont disjoints ou sécants.
En revanche elle ne discrimine pas (d'après mes essais!) les polygones qui ont un ou plusieurs côtés communs.
Dommage.
Merci quand même.
Messages postés
164
Date d'inscription
jeudi 6 mars 2003
Statut
Membre
Dernière intervention
9 octobre 2006

Pour savoir s'ils ont simplement un coté commun mais pas s'ils sont sécants, tu peux faire comme ca :
Tu créés tous tes points dans un meme tableau. Ensuite tu créés tes polygones en définissant une liste d'index. Enfin pour savoir si 2 polygones ont un coté commun, il te suffit de regarder si au moins 2 indexs sont partagés.
En VB6 ca doit donner un truc dans ce style là pour la déclaration :


Public Structure Indices
Public Index() as Long
End Structure

Public Structure Points
Public X as Single
Public Y as Single
End Structure

Public PointsTab(0 to 4) as Points
Public Polygones(0 to 2) as Indices

With PointsTab(0) : .x 1 : .y 2 : End With
With PointsTab(1) : .x 2 : .y -1 : End With
With PointsTab(2) : .x 3 : .y 0.5 : End With
With PointsTab(3) : .x -0.5 : .y 2 : End With
With PointsTab(4) : .x 1 : .y 1.5 : End With

With Polygones(0)
Redim .Index(0 to 2)
.Index(0) = 0
.Index(1) = 1
.Index(2) = 2
End With

With Polygones(1)
Redim .Index(0 to 2)
.Index(0) = 1
.Index(1) = 2
.Index(2) = 4
End With

With Polygones(2)
Redim .Index(0 to 2)
.Index(0) = 0
.Index(1) = 3
.Index(2) = 4
End With


Ensuite pour savoir quel point compose ton polygone, tu regarde les indexs. Le 1er polygone (d'ordre 0) se compose de 3 points auxquels tu accèdes comme ça :
PointsTab(Polygones(0).Index(0))
PointsTab(Polygones(0).Index(1))
PointsTab(Polygones(0).Index(2))

Tu n'as donc plus qu'à comparer les 2 listes d'indexs des points composants les polygones (si tu n'utilises que des triangles, il te suffit de regarder si 2 indexs apparaissent dans les 2 polygones). Cette méthode est inspiré des Vertex et Index Buffers utilisés par DirectX :)
Messages postés
164
Date d'inscription
jeudi 6 mars 2003
Statut
Membre
Dernière intervention
9 octobre 2006

Pour des polygones quelconques tu peux faire un truc comme ça (attention je viens de coder cet algorythme a la volée, ce n'est pas du tout optimisé, il doit sans doute y avoir une méthode plus performante) :

Dim Joints As Boolean
Joints = False
For i = 0 To UBound(Polygones(0).Index)
For j = 0 To UBound(Polygones(1).Index)
If Polygones(0).Index(i) = Polygones(1).Index(j) Then
k = i + 1
l = j + 1
If k > UBound(Polygones(0).Index) Then k = 0
If l > UBound(Polygones(1).Index) Then l = 0
If Polygones(0).Index(k) = Polygones(1).Index(l) Then
Joints = True
Exit For
End If

k = i + 1
l = j - 1
If k > UBound(Polygones(0).Index) Then k = 0
If l < 0 Then l = UBound(Polygones(1).Index)
If Polygones(0).Index(k) = Polygones(1).Index(l) Then
Joints = True
Exit For
End If

k = i - 1
l = j - 1
If k < 0 Then k = UBound(Polygones(0).Index)
If l < 0 Then l = UBound(Polygones(1).Index)
If Polygones(0).Index(k) = Polygones(1).Index(l) Then
Joints = True
Exit For
End If

k = i - 1
l = j + 1
If k < 0 Then k = UBound(Polygones(0).Index)
If l > UBound(Polygones(1).Index) Then l = 0
If Polygones(0).Index(k) = Polygones(1).Index(l) Then
Joints = True
Exit For
End If
End If
Next j
If Joints = True Then Exit For
Next i
Messages postés
252
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
29 juin 2013

Bonjour vr3h,
Je vais essayer ta méthode, qui, a priori, me semble la bonne!
J'en avais établi une qui comparait les vecteurs communs mais elle est très lourde et la tienne me parait plus élégante.
Merci pour l'aide.
Jacques13
Messages postés
164
Date d'inscription
jeudi 6 mars 2003
Statut
Membre
Dernière intervention
9 octobre 2006

Coucou, la méthode correspond t elle a ce que tu cherchais ?
Messages postés
252
Date d'inscription
mardi 3 juin 2003
Statut
Membre
Dernière intervention
29 juin 2013

Coucou vr3h, excuse moi pour le retard apporté à te répondre.
Je pense que ta méthode est parfaite sur le plan théorique.
Elle a, cependant, du mal a être transposée à mon cas particulier.
En effet, tu utilises, en quelque sorte, des matricules de points PointsTab(i) que je ne peux manipuler.
Ma BD consiste en une salve de points double-précision stockés binaires du genre:
.................,n,x1,y1,x2,y2,........,xn,yn,...................
chaque salve définit un polygone; avec ta méthode, il faudrait faire un premier passage en lecture pour stocker dans un tableau toutes les coordonnées en leur attribuant un numéro individuel puis faire un deuxième passage pour éliminer les doublons:--> trop lourd en temps de traitement et en espace mémoire!
Merci quand même et bravo.
Jacques13