Discussion :

[ewaca]

le soucis avec atan2 c'est que si on prend un point quelconque, les points alignés avec celui auront le meme angle, du coup, si on classe suivant l'angle, ils seront a coté, alors que pas du tout
si on prend le points rouge en référence, les points bleu et vert auront le meme angle et seront donc confondu.

et comme je dis dans mon premier message, si sur une plage de 3° j'ai plusieurs points, je prend le plus lointain.
pour moi la solution de l'atan2 marche que si le point de référence est au centre, car dans mon cas de figure (sonde laser), je ne me retrouverait pas a recouper plusieurs fois une paroi car le laser ne voit pas a travers les obstacles

[souviron34]

mais non...

D'une part l'égalité stricte est extrêmement difficile à obtenir en informatique
Et d'autre part, dans un tri il y a une "fonction de tri".

Cette fonction de tri prend 2 points et les compare entre eux, et prévoit 3 cas :

• quantité 1 < quantité 2 => point 1 avant point 2
• quantité 1 > quantité 2 => point 2 avant point 1
• égalité : alors on prend une deuxième quantité qui a du sens

Dans le cas du tri angulaire, le 2ième quantité est la distance :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Si angle 1 < angle 2   alors   point 1 avant point 2
Si angle 1 > angle 2   alors   point 2 avant point 1
Si angle 1 = angle 2  alors
    si distance (ref, point1) < distance (ref, point2)   alors point 1 avant point 2
    si distance (ref, point1) > distance (ref, point2)   alors point 2 avant point 1
    si distance (ref, point1) = distance (ref, point2)   alors point 1 = point 2

Regarde les docs sur les tris dans le langage que tu utilises (que ce soit qsort ou autre), tu auras toujours à définir une fonction de comparaison entre 2 points...

[wiwaxia]

Bonjour,

Ce problème soulève des difficultés redoutables, la triangulation d'un nuage de points exigeant des procédés d'exploration et de tri dont la mise au point ne va pas de soi. Et la quantité de calculs paraît à priori si énorme que la résolution semble hors de portée d'un simple programme, et demande la mise en oeuvre d'un logiciel spécialisé.
Mais en consultant les remarques qui ont été données, il m'est venu les idées suivantes.

... Une sonde laser est placée dans un forage ayant rencontré une cavité, et elle mesure à 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 final c'est de remplir cette surface 3D par des petits cubes. ... Je suis pas sûr de comprendre tout ...
Du coup je souhaite faire quelque chose plus à 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)...

1°) Il faut impérativement renoncer à tout algorithme 2D, apparemment plus facile, la réduction de toute tranche du nuage à un plan par projection orthogonale dénaturant complètement le système et conduisant à une impasse: tbc92 en a fait la remarque, et tu t'en es toi-même rendu compte.

... ç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 faibles, et au final je voudrais faire des cubes de 50cm de côté.
Pour un même 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 convexe, il y a forcément un moment ou ça ne va pas.

2°) Le recours à l'isobarycentre (G) du système est le réflexe de quiconque entreprend de décrire un ensemble de (N) points; d'autant que la somme des carrés des distances séparant un point donné (M) de tous ceux du nuage S_M = Somme(MM_k)² est minimale en (G), et que la moyenne quadratique R = (S_G/N)^1/2 représente le rayon de la sphère centrée en (G) à laquelle le nuage creux peut être grossièrement assimilé.
Toutefois ce point ne peut être ici retenu, en raison des irrégularités possibles de la cavité: une bosse en creux peut dissimuler une partie de la paroi vis-à-vis de (G), et celui-ci se trouver même en dehors ... A ce titre, il faut lui préférer la position de la sonde, depuis laquelle la paroi est (en principe) entièrement visible.
Il faut ajouter que faute d'un maillage suffisamment dense et uniforme, le tracé de la surface présentera toujours des incertitudes.

3°) La méthode à suivre se trouve dans l'énoncé:

Le but final c'est de remplir cette surface 3D par des petits cubes.

Empiler des cubes, donc se livrer à une exploration systématique de l'espace selon des directions parallèles aux axes de symétrie du cube - les mauvais plaisants s'abstiendront d'insinuer que c'est du niveau Mat'Sup (maternelle supérieure).

On pourrait envisager les étapes suivantes:

1°) Inscrire le nuage de points dans le plus petit cube centré sur l'origine du repère (Oxyz), et pour cela:
a) localiser le centre (C) du nuage défini à partie des valeurs extrêmes des coordonnées des points par les relations:
x°_C = (x°_min + x°_max)/2 , y°_C = (y°_min + y°_max)/2 , z°_C = (z°_min + z°_max)/2 ;
b) imposer à tous les points du nuage la translation de vecteur (CO);
c) choisir pour l'arête (2H) du cube le plus grand des écarts séparant les valeurs extrêmes:
2*H = Max((x°_max - x°_min), (y°_max - y°_min), (z°_max - z°_min));
On vérifie aisément que les nouvelles coordonnées (x, y, z) se situent dans [-H ; H] .

2°) Envisager une exploration méthodique de l'intérieur du cube, selon des directions parallèles aux axes du repère, sur les domaines délimités par les cônes de sommet (O), s'appuyant sur le contour des faces carrées, et qui définissent une partition de l'espace:
D₁: x > 0 ; ((x >= |y|) et (x > |z|)) ; D₂: x < 0 ; ((x <= -|y|) et (x < -|z|)) ;
D₃: y > 0 ; ((y >= |z|) et (y > |x|)) ; D₄: y < 0 ; ((y <= -|z|) et (y < -|x|)) ;
D₅: z > 0 ; ((z >= |x|) et (z > |y|)) ; D₆: z < 0 ; ((z <= -|x|) et (z < -|y|)) .
a) Définir un treillis sur chacune des faces à partir de (2*m + 1) points uniformément répartis sur les arêtes, et séparés de leurs plus proches voisins par la distance: h = (H/m) ; on trouvera ainsi (24*m² + 2) noeuds sur la surface du cube, nombre à comparer à l'effectif (N) du nuage.
b) Associer à chaque domaine d'exploration (D_l) un sous-ensemble (E_l) du nuage, afin d'accélérer la recherche des points; par exemple, pour (D₁): E₁ = { M(x, y, z) | x >= 0 } ... etc, ce qui a pour intérêt de diviser le nombre d'éventuels triangles par environ 2³ = 8 .
Ces nouveaux plans-frontières rejoignent les cônes au voisinage de l'origine, ce qui est normalement sans conséquence si la zone centrale est vide; dans le cas contraire, prendre une définition plus large de (E_l).

3°) Parcourir toutes les cellules des six domaines précédemment définis en y détectant les points éventuellement présents (cas favorable dès qu'on en trouve un), ou sinon recherche d'une intersection.
En associant les entiers (i, j, k) aux coordonnées (x, y, z), la suite des instructions prendra, pour (D₁) par exemple, la forme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
Pour j variant de -m à +m
    y:= j * h;
    Pour k variant de -m à +m
        z:= k * h;     
        si |j|< |k| alors Lim:= |k| + 1
                    sinon Lim:= |j|;
        i:= m + 1;
        Répéter i:=  i - 1; Testcase(x, y, z, t)
            jusqu'à ce que ((i=Lim) ou (t=vrai);
        Si (t=vrai) alors TracerCube(x, y, z)
                    sinon Rech_Triangle1(y, z, t');
        Si (t'=vrai) alors TracerCube(x, y, z);
    Fin; {Pour k}
Fin; {Pour j}

Désolé pour ce sabir, que j'espère malgré tout compréhensible.

Testcase(x, y, z, t) s'arrête et renvoie la valeur (t=vrai) dès qu'un point du nuage (ou plus précisément du sous-domaine correspondant (E_l) a été trouvé dans la case élémentaire (x+-h/2, y+-h/2, z+-h/2).
Rech_Triangle1(y, z, t') détecte tous les triangles de sommets en (E₁) recoupant la demie-droite considérée (x>0, y, z), et renvoie la valeur (t'=vrai) dès qu'un résultat a été trouvé; de tous les triangles trouvés il ne retient que le plus "petit", vérifiant donc l'un des 3 critères suivants - au choix:
- Max(a², b², c²) minimal;
- Somme (a² + b² + c²) minimale;
- Aire (S) minimale (calcul possible, mais un peu lourd).
Le premier critère, qui privilégie les triangles dont les sommets sont les plus proches, me paraît le plus approprié.

Reste la question de savoir où se situe le point d'intersection (K) du triangle avec la demi-droite; on retrouve là l'épouvantail qui a détourné le demandeur du droit chemin de l'algorithme 3D:

Je ne sais pas comment écrire le code correspondant aux algos permettant de tester si un point recoupe un triangle dans un espace en 3 dimensions. Je reste donc sur du 2D.

La position de tout point (K) du plan d'un triangle (ABC) s'exprime à l'aide de deux réels (p, q) par la relation: AK = p*AB + q*AC ; il se situe de surcroît à l'intérieur (ou sur les bords) de la figure si et seulement si ces coefficients vérifient les conditions:
0 <= p <= 1 ; 0 <= q <= 1 ; 0 <= p + q <= 1 .

Tout ce qui précède est une ébauche rapide, susceptible d'être améliorée.
a) On peut diminuer le nombre de points testés, moyennant quelques modifications mineures, en partant du prisme droit à base rectangulaire circonscrit au nuage, d'arêtes (x°_max - x°_min), (y°_max - y°_min), (z°_max - z°_min) ;
b) Le procédé d'exploration s'est limité aux 3 axes quaternaires du cube, perpendiculaires aux faces; et il pourrait être séduisant d'envisager des polyèdres comportant un plus grand nombres de faces, mais au prix de difficultés croissantes, et bientôt démesurées; par exemple:
- l'octaèdre régulier (4 axes d'ordre 3, donc 8 normales aux faces et 8 secteurs partitionnant l'espace),
- le dodécaèdre rhombique (6 axes d'ordre 2, donc 12 normales aux faces et 12 secteurs),
- et les polyèdres archimédiens cumulant les axes précédents ...
c) Si le nombre de points est vraiment trop grand (N >> 24*m² + 2), on peut "tricher" en se limitant d'abord à la recherche des cellules occupées (procédure Testcase) dans tous les secteurs, puis en remplaçant le nuage initial par l'ensemble des centres des cellules occupées.