Discussion :

[ewaca]

Bonjour,

je ne sais pas si c'est plus des maths ou de l'image mais il fallait bien trancher et c'est tombé sur maths ^^

voici ce que j'ai


ce que je voudrais faire c'est tracer le contour de ce nuage de point.

pour tracer un contour je procède comme ça quand j'ai le centre a l'intérieur du nuage de point :
1- calcul l'angle formé par chacun des point par rapport a un plan horizontale (Atan2)
2 - classer les point suivant l'ange croissant
3 - pour lisser un peu, je prend un pas de mesure (3° par exemple )et je regarde le point le plus loin (utile en cas de nuage de point plus "rempli")

ainsi j'ai les points classés les un a la suite des autres, que je peux relier par une ligne, sans que cela parte dans tous les sens.

Le soucis sur cette figure, c'est que le centre est en dehors du nuage de point. Du coup ma façon de procéder avec les angles ne fonctionne pas du tout.

connaissez vous le moyen de tracer les contour d'un nuage de point dans ces différents cas de figure ?

merci par avance

[tbc92]

Comment le centre peut-il se trouver à l'extérieur du nuage ???
On est bien d'accord que tu veux tracer l'enveloppe, c'est à dire une forme CONVEXE, c'est à dire que sur ton exemple, les 5 points qui ont comme coordonnées (-1,0) environ ne seront pas sur ce contour ?

[ewaca]

je voulais pas donner trop d'info pour éviter de perdre les gens dans des détails, mais voici le contexte.

une sonde laser est placée dans un forage ayant rencontré une cavité, et elle mesure a l'aide d'un laser, les bords de la cavité.
Je récupère ainsi un nuage de point XYZ qui sont le contour de la cavité en 3D.
Le but finale c'est de remplir cette surface 3D par des petits cubes. On m'a déjà parlé d'octree, mais je ne trouve pas d’algorithme pour le faire et je suis pas sur de comprendre tout ce qui se cache derriere.

du coup je souhaite faire quelque chose plus a ma portée à savoir :
- sélectionner des points pour un plan Z donné
- tracer le contour
- remplir le contour 2D par des carrés (ça je sais faire)

J'ai pas d'exemple de nuage de point en vue 3D sous la main, mais voici une image qui montre comment je peux me retrouver avec un centre en dehors du nuage de point.


(coupe suivant l'axe XZ)

les points appartenant au plan rouge sont situés complétement a coté de l'aplomb de la sonde.

les points -1, 0 sont pas forcément a exclure, les forme des cavités pouvant etre assez complexes, ça peut etre un retour brusque de la parois, ou un rocher en plein milieu.

[Flodelarab]

Bonjour

La sonde se trouve-t-elle en (0,0) ?
Le laser tourne, la lumière est réfléchie et la mesure est faite ?

Si oui, il faut prendre comme point de référence la sonde et refaire son parcours. Pour les directions pour lesquelles il n'y a pas de mesure, il faut faire une interpolation des 2 points qui l'encadrent.

[ewaca]

la sonde dans l'exemple se trouve en 0,0, mais des fois on peut lui donner des coordonnées locales, mais en tout cas on connait toujours les coordonnées de la sonde.

Le laser a un cheminement, on peut lui demander de faire des plans verticaux ou horizontaux, avec un pas de quelques degrés.

on peut extraire les différentes boucles mais je ne pense pas que cela soit la solution, du moins pour ma façon de procéder.
Je ne vais pas rentrer dans les détails de fonctionnement, mais on ne se retrouve pas avec des plans horizontaux comme je veux.

scan verticaux (plans XZ)

(la petite fleche indique le coté des capteurs)
donc si on prend un plan vertical d'un azimuthe donné, il sera formé par deux boucles verticales séparé de 180°
et les plans tourne autour de l'axe donc ce ne me permet pas de découper l'espace en cubes suivant différents plans parallèles

je ne vais pas réussir a dessiner le cheminement en scan horizontale, mais je ne pense pas que ce soit aussi la solution, tous les points du cercle formé par une boucle horizontale ne seront pas a la meme cote Z.

hors il me fait des plans horizontaux pour pouvoir avoir seulement 2 Z différents pour une cube (la base et le toit). c'est pour mes calculs qui vont suivre

je ne peux pas exploiter le cheminement de la sonde, y a t il une solution pour délimiter le contour d'un nuage de points quelconque, sans que le centre initiale (de la sonde) soit a l'intérieur de ces points ?

[picodev]

Bonjour,

oui … même sur wikipedia …

[ewaca]

Merci pour le lien, mais je crois que j'ai un soucis ... pour décrire le contour d'une cavité ... c'est a la fois convexe et concave sur le meme contour.
voici un exemple :


ça représente le bord des parois sur une tranche Z de 50cm.
Je prends une un tranche de 50cm car il y a une lacune de points sur des tranches plus faible, et au final de voudrais faire des cubes de 50cm de coté.
pour un meme angle on a plusieurs distances, car sur cette tranche de 50cm, le bord de la cavité évolue et recule ou se rapproche.

on a un alignement suivant un angle donné car les scan sont fait verticalement par incrément de 2°

que je prenne un algo concave ou ocnvexe, il y a forcément un moment ou ça ne va pas.

en pointillé vers (désolé pas très lisible) le contour que ça tracerait avec un algo concave, mais ça va pas.
en pointillé bleu, le contour si je prend un algo convexe, et ça ne va pas non plus.

En écrivant tout ça, je crois que la seule solution c'est un mixe des 3 algo cités :

je commence par faire une enveloppe convexe.
si mon centre (ma sonde) est dans l'enveloppe, je peux faire mon algo avec les angles et distance du premier message.
Sinon, faire une enveloppe concave.

[Jerome Briot]

Tu peux jeter un œil du coté des Alpha Shapes, voire des contours actifs.

Mais le nuage de points semble manquer de densité…

[ewaca]

Cgal a l'air très puissant, faudrait que je prenne le temps de regarder, avec un peu de chance il peut me remplir directement mon nuage de points 3D avec des petits cubes, mais a premiere ve, c'est surtout du meshing

[tbc92]

Sur l'image postée ce matin, tu as retenu toutes les mesures sur une certaine tranche de 50 cm. Et sur cette tranche, tu n'as aucune mesure sur la partie en bas à gauche (angle entre 200° et 250°)
J'imagine que sur les tranches voisines, tu peux avoir des données sur cette zone.

Et donc, en raisonnant en problème 2D tu perds de l'information, et tu aurais intérêt à voir ce problème comme un problème 3D ?

Ok, je sais que déjà en 2D, c'est galère ... et ça va l'être encore plus en 3D. Mais c'était juste pour dire.

[ewaca]

je n'ai pas plus de lacune en 2D qu'en 3D sur ce secteur, je posterais l'image 3D du nage de point mais, le laser n’atteignais pas cette partie de la cavité (zone d'ombre)
s'il y avait un moyen aussi simple de voir si un point est dans un polygone en 2D qu'en 3D, ça serait un jeu d'enfant ... mais c'est pas le cas :/

[tbc92]

En 3D, on peut définir un polyèdre par une série de triangles (c'est la norme par exemple pour les imprimantes 3D). Et pour définir si un point est dans le polyèdre, on peut imaginer un axe vertical qui passe par notre point. Si entre +oo et notre point, on a traversé un nombre impair de triangles, c'est qu'on est dans le polyèdre.

[ewaca]

oui c'est le meme principe pour tester si un point est dans un polygone en 2D (meme si en C# il y a une fonction de base qui le fait très bien)

en 3D ça voudrait déja dire etre capable de recréer la surface par triangulation et ensuite tester l'intersection d'un segment et d'un plan ....
Les 2 je sais pas faire ... (surtout la premiere étape)

[tbc92]

Décomposons :
1- A partir d'un nuage de point en 3D, déterminer l'enveloppe convexe (une série de triangles) : Pour cette étape, il existe probablement des algorithmes 'tout-faits', mais sinon, je pense que je saurais faire, et je peux détailler si ça t'aide.
2- Cette enveloppe convexe n'est pas satisfaisante, car il y a visiblement des zones avec des creux et des bosses. Il faut donc détecter les endroits où l'enveloppe convexe est trop loin de la réalité. Cette étape là est la plus floue. La façon dont je procéderais, c'est :
* Parmi tous mes triangles, détecter la plus longue longueur. Couper cette longueur L en 2, en sélectionnant un point parmi toutes les mesures de ma sonde. On choisit le point qui donne max(L1,L2) minimal. Mais on ne reprend pas un point qui était déjà utilisé pour faire l'enveloppe.
* La longueur L en question participait sur 2 triangles ; on coupe donc chacun de ces 2 triangles en 2.
* Boucler un certain nombre de fois, tant que la plus longue longueur L est supérieure à un seuil donné.
Je suis assez confiant pour le résultat pour les creux et les bosses. Mais beaucoup moins confiant pour les zones où on a peu de mesures. J'ai peur que cette étape génère des choses bizarres sur les zones où on a peu de mesures.
3- Détecter pour chaque cube de 5050x50 s'il est dans l'enveloppe ainsi obtenue : c'est des maths pures et dures, ça ne devrait pas poser de problème.

PS : sur les zones où on a peu de mesures, voici une 'rustine' qui devrait aider :
On a 2 triangles ABC et ABD avec l'arête commune AB. On cherche à remplacer le segment AB par AE+EB ( E est un point parmi les mesures, ce n'est pas un point du segment AB.) On trouve un point E qui semble coller. Si EC ou ED est plus long que AB, alors problème ! Donc dans ce cas on ne change rien à ce segment AB.

[souviron34]

Comme on a cité au dessus, les "alpha-shapes" sont faites pour ça..


Maintenant, j'ai déjà exposé ici quelques lignes d'un logiciel que j'ai fait pour du 2D, mais il est commercial... Donc j'ai déjà fourni l'essentiel de la démarche dans les autres posts... Le reste serait payant (MP).

Cependant, au vu de l'image donnée, c'est pas vraiment le style de nuages qu'on peut traiter "standard" avec les alpha-shapes ou mon algo.. Ce n'est pas vraiment un nuage..

L'image jointe montre ce que peut faire mon algo..


Maintenant pour ton problème je crois que c'est beaucoup plus simple...

• Tu fais un tri de tous tes points par angle
• Tu les stockes dans l'ordre du tri

Maintenant, pour avoir un tri angulaire qui marche à tous les coups, une méthode donnée pour les algos convexes est simple : tu prends le point le plus en bas à droite comme point de référence.. (sinon ce que moi je fais c'est prendre le point le plus proche du barycentre. Tu vas de 0-360 et non de 0-180)

[ewaca]

voici les images de nuages de points, pour se faire une idée plus globale de la chose.
Cas simple :

nuage de points :

surface obtenue par le logiciel :


cas plus compliqué :

nuage de points :

surface obtenue par le logiciel :


dans le premier cas on serait tenté de faire une surface avec le point le plus proche, mais avec le 2e cas, ça marcherait pas.
Le logiciel fonctionne par triangulation.

si on tient vraiment a travailler en 3D, je peux exporter la surface, en format DXF, j'ai accès aux triangles qui forment la surface. (suivant cette structure)

ça résout déja une bonne partie du problème.
après, c'est comment tester si un point est a l'intérieur de ce bordel ?
parce que je pensais tester le centre du cube, comme des intégrales, une partie des cube dépasserait un peu, mais c'est compensé par le vide laissé par d'autres.

pour la forme complexe, il y en a 57 000

à souviron34 :
le coup de l'angle c'est ce a quoi j'ai pensé en premier, mais dans le cas ou le centre est en dehors du nuage de point, tu auras pas 360°, et ça marche pas

[souviron34]

nos messages se sont croisés....

[souviron34]

à souviron34 :
le coup de l'angle c'est ce a quoi j'ai pensé en premier, mais dans le cas ou le centre est en dehors du nuage de point, tu auras pas 360°, et ça marche pas

le centre est TOUJOURS dans le nuage, si tu suis :

Maintenant, pour avoir un tri angulaire qui marche à tous les coups, une méthode donnée pour les algos convexes est simple : tu prends le point le plus en bas à droite comme point de référence.. (sinon ce que moi je fais c'est prendre le point le plus proche du barycentre. Tu vas de 0-360 et non de 0-180)

On ne sait pas trop ce que tu cherches, mais en utilisant ce que je dis ci-dessus, tu peux avoir une série de contours par Z... (l'enveloppe de ta forme 3D)

[ewaca]

je ne sais pas comment écrire le code correspondant aux algo permettant de tester si un point recoupe un triangle dans un espace en 3 dimension.
je reste donc sur du 2D.
je veux donc faire une enveloppe correcte d'une tranche de ma cavité (du coup je passe le problème en 2D)
une enveloppe correcte est à la fois concave et convexe.
c'est pour ca que le coup d'un tri angulaire est plus judicieux.
mais ça marche pas tout le temps.
de base, je prend les coordonnées de ma sonde pour centre du nuage de points.
mais dans certains cas (cavité oblique), ma sonde est a l'extérieur des points formant cette tranche.
il faut donc trouver un nouveau centre qui soit bien a l'intérieur des points, mais dans le premier cas que j'ai posté, ça tombe a coté si je fais la moyenne des x et des y.

et si je ne dis pas de bêtise, le barycentre d'un nuage de points (X,Y), c'est ni plus ni moins que la moyenne des X et la moyenne des Y, il n'y a pas de "poids" donné aux points.
mais la moyenne des X et des Y dans le premier nuage de point donné me fait tomber a coté, si je fait un tri angulaire, je n'aurais pas 360°

[souviron34]

mais la moyenne des X et des Y dans le premier nuage de point donné me fait tomber a coté, si je fait un tri angulaire, je n'aurais pas 360°

Je pense pas que ça tombe à côté (à vue de nez je le verrais vers -1 -1), mais de toutes façons on s'en fiche totalement.. C'est juste pour avoir une référence pour le tri.. On pourrait prendre le point le plus en bas à droite ou n'importe lequel autre....

Qu'on ait pas 360 on s'en fiche aussi, on veut juste avoir un maximum pour l'écart mais on pourrait se contenter de 30 ou 100 degrés


Si tu te sers de atan2, la fonction arctangente qui détermine le quartier, c'est simple

pour chaque point :

angle = atan2 ( (y - yref), (x - xref) )


https://en.wikipedia.org/wiki/Atan2