-coques concaves simplifié

Question

Problème:

Compte tenu: n points qui sont fortement corrélées à un 3d k-verso polygone non convexe, où n >> k

Trouver: la meilleur ajustement coque concave qui correspond à la géométrie originale des points

---

solutions tentatives:

Attention: pseudocode

segments = [] 
for each point in image: 
    #segment points into planes via comparing approximate normals 
    #actual implementation is more complicated 
    findSegment(image,point) 
for each segment in image: 
    #transform coordinate system to be a 
    #2D-plane perpendicular to the normal of segment 
    transform(segment, segment.normal) 
    edges = findEdges(segment) 
    polygonHull = reconstructPolygon(edges) 
    #transform back to original coordinate system 
    transform(segment, segment.normal) 

---

Exemple:

___ 
| |    | 
| \__ ==>  | ___ 
|  |   |__/ /_____ 
|_______|  // \_ 
       //_____/ 
       /

entrée serait simplement un nuage de points de haute densité qui est approximativement uniformément distribué points aléatoires à l'intérieur le plan polygonal, l'esprit h un peu de bruit.

La sortie correspond aux sommets du polygone en points 3D.

---

Ma question est, y at-il une meilleure façon d'aborder ce problème? Le problème avec la solution ci-dessus est que les points peuvent être bruyants. En outre, la pixellisation des points en 2d puis en préformant une recherche de bords est très coûteuse.

Tout pointeur serait génial. Merci d'avance

Answer 1

Si vos coins concaves ne sont pas trop nets, je pourrais essayer de faire une triangulation Delaunay 3D sur le jeu de points. Les régions de Voronoi des points sur la frontière tendront à être infinies ou beaucoup plus longues que celles à l'intérieur. De même, les cellules à la limite associées à une seule face du polyèdre auront tendance à être alignées dans une direction presque normale à la face à laquelle elles sont associées, en ce qu'elles seront toutes longues et minces et leurs axes longs seront presque parallèle et pointant hors du polygone. Dans un peu sorta quasi-pseudocode

Compute Delaunay triangulation 
Collect long thin Voronoi regions 
Partition the Voronoi regions into clusters that are nearby and nearly parallel. 
Create faces normal to the axes of the Voronoi regions. 

Modifier Maintenant, je vois que vous voulez juste un polygone. L'approche ci-dessus fonctionne, mais il est probablement préférable de le faire en deux étapes. D'abord trouver le plan dans lequel se trouve le polygone, faire un ajustement des moindres carrés d'un petit échantillon de points est probablement assez bon. Projetez les points sur un plan (c'est à peu près ce que vous avez fait) puis calculez la triangulation Delaunay 2d pour trouver les points de contour et continuez comme ci-dessus.

Answer 2

Il semble que vous souhaitiez calculer la coque concave d'une collection de points dans un espace 3 projeté sur un plan. Le cas 2D est discuté en détail here.

Answer 3

Tout d'abord, vous devez choisir une représentation pour votre maillage. En 2D, j'ai implémenté un algo concave Python en utilisant cette représentation: half-edge data structure.

Ensuite, l'algorithme en 2D (vous devez adapter à la 3D) peut être proche to alpha shape algorithm, by Edelbrunner.