Discussion :

[valentin03]

Questions:
D'où sort ton fichier de noeuds ?
Pourquoi veux-tu supprimer les confondus ?
Quel est le but final ?
Merci pour tes réponses.

[nekcorp]

Le fichiers nœuds c'est ma donné d'entrée, je peux le créer moi même ou le récupérer.

Parce que je dois faire des études de treillis derrière et que certains éléments ne respectent pas la structure dite de treillis.

Le but final c'est d'avoir une structure dite treillis.

[valentin03]

Où peux-tu récupérer le fichier ? ("sur le net", n'est pas une réponse).
A quoi va servir la structure dite "treillis".

[nekcorp]

C'est un interrogatoire de police ?

[valentin03]

Rien ne t'oblige à répondre, et tu peux même répondre n'importe quoi (mais ça risque de provoquer d'autres questions).

[dourouc05]

Aussi, tes réponses pourront suggérer d'autres approches pour résoudre ton problème initial, peut-être même pour éliminer le besoin de supprimer ces segments.

[valentin03]

Et même éliminer carrément le problème.

[Guesset]

Bonjour,

Sauf si je n'ai rien compris, le problème de base est de supprimer les grands cotés des triangles de surface nulle.

Si c'est exact, j'ai deux questions :

• Peut-il y avoir des points redondants ?
• Il est fait allusion à un treillis. Dans ce cas seuls les triangles élémentaires sont intéressants à étudier. Est-ce exact ?

La compréhension du véritable problème à résoudre est indispensable à une réelle solution.

Salutations

[BeanzMaster]

Salut, je reprend ton énoncé pour être sure que j'ai bien compris.

- Tu as une liste de points
- Tu as une liste de segment de ligne (donc bornée) défini par un indice dans la table des points

1ere passe :
- Trouver les lignes avec des indices similaires
- Si 2 indices identiques on peut supprimer une des lignes directement
- Si 1 indice on vérifie l'intersection du 2eme point avec les autres points des autres lignes. Si correspondance on supprime la ligne de la liste
EDIT : On peut réduire le nombre de test en vérifiant simplement le Slope, l'angle ou la direction des lignes

2eme passe : On vérifie les intersections des lignes restantes pour trouver si un segment en chevauche un autre si c'est la cas on supprime le segment de ligne le plus petit

Pour l'optimisation :
- Entre les 2 passes un trie sur un élément de l'équation pourrait être fait (désolé je ne suis pas assez doué en maths, là à chaud pour préciser lequel) EDIT : Idem que plus haut du coup : slope, angle..., et le faire dès le début
- Diviser la liste en 2 puis en 2... ("divide and conquer")
- utiliser des threads,
-...

voila à part ça, c'est avec quel langage de programmation que tu codes ?

Sinon il y a quelques mois j'ai fait quelques recherches sur les équations de ligne pour un besoin personnel: ici c'est avec Lazarus

A+

EDIT : Désolé, pour le "sur-éditage"
Je suis en plein dans la 3D en ce moment. Un autre truc au quel je viens de penser. Pour l'optimisation, vue que tu as énormément de points. Ce serait de regrouper cet énorme nuage de points en plus petits et utiliser des "Bounding Box/Sphere" pour tester les collisions, afin d'éliminer un maximum de points et de faire des tests inutiles par la suite. On ne testerai plus que les potentiels nuages susceptibles d'avoir un segment de ligne en commun entre eux. En gros cela revient à faire ce que dourouc dit faire du partitionnement dans l'espace.

[anapurna]

salut

pour qu'il y ai connectivité :
il faut qu'il ai la même définition de l’équation de droite passant par deux point
il faut que l'un des points du segment S1 soit sur l’intervalle du segment S2 ou inversement

pour rappel
- calcul d'une droite à partir de 2 points :
droite d'équation : Y = aX + b

soit deux segments S1,S2 défini par 2 point (X1,Y1) et (X2,Y2)

a = (S1.Y1 - S1.Y2 ) / (S1.X1 - S1.X2)
b = S1.Y1 - a*S1.X1

a' = (S2.Y1 - S2.Y2 ) / (S2.X1 - S2.X2)
b' = S2.Y1 - a*S1.X1

si a = a' et b=b' les droites sont parallèle et non sécante

il reste a savoir si elles sont confondu

pour cela il suffit juste de savoir si (( S2.X1 > S1.X1 < S2.X2) et ( S2.Y1 > S1.Y1 < S2.Y2)) ou (( S2.X1 > S1.X2 < S2.X2) et ( S2.Y1 > S1.Y2 < S2.Y2))
ou (( S1.X1 > S2.X1 < S1.X2) et ( S1.Y1 > S2.Y1 < S1.Y2)) ou (( S1.X1 > S2.X2 < S1.X2) et ( S1.Y1 > S2.Y2 < S1.Y2))

je pense que si toutes les conditions son remplit alors tes segments sont confondu en parti ou complètement

[Guesset]

bonjour,

Le fichiers nœuds c'est ma donné d'entrée, je peux le créer moi même ou le récupérer.

Parce que je dois faire des études de treillis derrière et que certains éléments ne respectent pas la structure dite de treillis.

Le but final c'est d'avoir une structure dite treillis.

Une structure de treillis (Delaunay ou autre) est composée de triangles élémentaires et il faut s'assurer qu'aucun de triangles du treillis ne soit de surface nulle (ie. composé de segment colinéaires). Mais ce sont seulement les triangles élémentaires qui sont à vérifier (le nombre est de l'ordre de N et non d'un N^3). De plus, par efficacité, en général on vérifie ces cas au moment du maillage c'est à dire à la création des triangles élémentaires.

C'était la raison de mes questions car j'avais le sentiment, peut être erroné, que le problème réel est plus simple que d'éliminer tout grand segment AC colinéaire à deux autres, AB et BC, avec recouvrement quelque soit leur distance.

Ce treillis triangulaire très régulier montre que les points ABC correspondent au problème tel que traité actuellement mais vraisemblablement pas s'il s'agit d'éviter des triangles élémentaires de surface nulle.

Salutations