Polygonnetz – Wikipedia
Points connectés les uns aux autres dans le graphique informatique Polygonnetz , qui définit la forme d’un polyédrique. Les réseaux triangulaires et les filets carrés sont les plus courants ici. Il existe un certain nombre de structures de données bien connues pour stocker des réseaux et des polygones polygonns. Les meilleures structures connues sont la liste des nœuds, la liste des bords, le bord ailé et la liste des bords à double tête (liste Halfedge en double connectée).
Chaque nœud doit avoir au moins une connexion au reste du réseau pour être membre du réseau. Il s’ensuit que chaque nœud peut être atteint de tout le monde sur le net. Dans la théorie des graphiques, les réseaux de polygonn peuvent être représentés comme des graphiques inappropriés sans bords multiples. [d’abord] [2]
Les propriétés suivantes peuvent avoir un réseau, mais aucune d’entre elles n’est requise pour un filet polygonn: [d’abord]
- Structure : Un filet polygonn est appelé structuré lorsque chaque point interne a le même nombre de bords et de surfaces adjacents.
- Régularité : Un filet polygonn est régulier si les longueurs de bord sont constantes dans toutes les directions. Cette propriété s’appuie sur la structuration.
- Orthogonalité : Un filet de polygone est décrit comme orthogonal lorsque les bords du réseau forment des angles droits. L’orthogonalité s’appuie sur la propriété de la structuration et de la régularité.
Le filet polygonn en tant que réseau triangulaire est une forme répandue du réseau de polygones. Il est particulièrement important pour les triangulations et le maillage.
(CROIRE)
Structures de données simples [ Modifier | Modifier le texte source ]]
Liste de nœuds [ Modifier | Modifier le texte source ]]
Avec la liste des nœuds, les points sont placés dans une liste de points distincte. Une zone est ensuite définie comme une liste de pointeurs sur les points de cette liste. Cela crée une séparation entre la géométrie (les coordonnées des nœuds) et la topologie (que les nœuds connectent les bords, qui limitent les zones).
Liste de bords [ Modifier | Modifier le texte source ]]
Les inconvénients de la liste des nœuds sont évités sur la liste des bords en enregistrant tous les bords dans une liste distincte. Les facettes sont définies ici comme des pointeurs sur la liste des bords. En plus du point de départ et fin, les deux facettes maximales associées pour chaque bord sont également stockées. L’ordre de spécification des pierres angulaires pour les bords détermine une orientation et détermine dans les facettes où à l’intérieur et où se trouve à l’extérieur.
Avantages et inconvénients [ Modifier | Modifier le texte source ]]
| Structure de données | Avantages | Désavantages |
|---|---|---|
| Liste de nœuds |
|
|
| Liste de bords |
|
|
En général, ce qui suit s’applique aux listes de nœuds et de bords que la recherche peut être effectuée très efficacement à partir d’une facette basée sur des objets subordonnés tels que les bords et les nœuds. Dans la direction opposée, cependant, il est opposé. Donc z. Par exemple, la recherche de toutes les facettes qui contiennent un certain coin ne sont toujours possibles que grâce à une recherche exhaustive.
Structures de données plus complexes [ Modifier | Modifier le texte source ]]
Bord ailé à Baumgart [ Modifier | Modifier le texte source ]]
Une structure de données qui peut être utilisée pour traiter de nombreuses requêtes est l’affichage de bord ailé selon Baumgart. En plus des informations sur la liste des bords, les mains sont stockées sur les bords qui se déclenchent du point de départ et du point final du bord actuel. En raison de l’orientation, chaque bord est autrefois positif (dans le sens des aiguilles d’une montre) et une fois négatif (dans le sens horaire).
Avec la structure de données à bord ailé, il est possible de s’interroger dans un temps constant que les nœuds ou les facettes appartiennent à un bord donné. Si une facette k bords, ces bords peuvent être recherchés l’un après l’autre dans une période linéaire (uniquement dans les réseaux polygonaux sans modifier la direction continue d’un polygone). D’autres demandes, en particulier celles basées sur un coin qui recherchent les bords ou les facettes dans lesquelles ce coin est contenu, sont beaucoup plus lents.
Doppelt Embreaked Edge List (demi-bord) [ Modifier | Modifier le texte source ]]
La structure de données à demi-bord est un peu plus sophistiquée que la liste des bords ailés. Il permet la plupart des opérations répertoriées dans le tableau suivant en temps constant, c’est-à-dire H. Temps constant par informations collectées. Si vous z. B. Tous les bords voisins à un point d’angle, l’opération est linéairement linéaire en ce qui concerne le nombre de bords voisins, mais constamment dans la période par bord. Half Edge ne fonctionne qu’avec une diversité à deux dimensions, i. H. Chaque bord est entouré exactement de deux facettes (il y a un semi-bord opposé pour chaque semi-bord), c’est-à-dire H. Les connexions en T, les polygones internes et les fractures ne sont pas autorisés.
Dans la structure à demi-bord, les bords, mais les semi-bords ne sont pas stockés. Les demi-bords sont dirigés et deux semi-edges appartenant (paire) forment un bord et un point dans la direction opposée.
Une autre structure de données est la liste de bords doublement connectée (DCEL).
Comparaison du temps de chargement [ Modifier | Modifier le texte source ]]
Le tableau suivant montre une comparaison de la durée asymptotique en fonction des nœuds, des bords et des surfaces des éléments existants. Il y a neuf requêtes possibles sur la structure, à savoir “quel coin, un bord ou une zone appartient au coin du bord ou de la zone”. Toutes les requêtes à l’exception des coins voisins d’un coin donné sont répertoriés dans le tableau. La comparaison montre à quel point les structures de données sont différentes des classes d’interrogation.
Mentionné ici:
- : Nombre de tous les bords
- : Nombre de bords d’une facette
- : Nombre d’arêtes qui appartiennent à un point
- : Nombre de toutes les facettes
Explication des demandes [ Modifier | Modifier le texte source ]]
| Demande | Liste de nœuds | Liste de bords | Bord ailé | Demi-bord |
|---|---|---|---|---|
| Caute → Points d’angle | Pas possible (il n’y a pas d’arêtes) | Lisible via les bords | Lire directement via l’entrée pour Edge | À propos de Semi -Edge → Vert et paire → Vert. |
| Canne → facettes | Pas possible (il n’y a pas d’arêtes) | lisible des bords | Vue directement depuis le bord | Déterminez les zones adjacentes via le bord → Face et bord → Paire → Face. |
| Bord → bords adjacents | Pas possible (il n’y a pas d’arêtes) | Pour les deux pierres angulaires: transporter “point d’angle → bord” | Voir la liste des bords | Voir la liste des bords |
| Point d’angle → bords | Étant donné que ce sont des polygones fermés, chaque facette (autant de bords que les points et les points) a des bords, ceux-ci doivent être déterminés pour chaque zone et vérifier si le coin donné est inclus | Passez juste tous les bords | Déterminez le bord de départ jusqu’au point, puis recherchez “prédécesseur à droite” jusqu’à ce qu’il n’y ait plus de bord là-bas, puis recommencez au bord de départ et exécutez-le dans une direction différente. | Obtenez le premier bord via Vert → Edge, puis obtenez le bord opposé et continuez à gauche. Faites-en longtemps jusqu’à ce qu’il n’y ait pas de bord successeur à gauche, puis recommencez avec Vert → Edge et cette fois courez à droite jusqu’à ce qu’il n’y ait pas de bord voisin. |
| Point d’angle → facettes | Passez simplement les bords pour toutes les facettes et voyez si le point d’angle est inclus. | Exécutez “Corner Point → Edge”, puis lisez la facette associée directement à partir de ces bords. | Déterminez simplement les bords du point et déterminez les zones associées dans une période constante | Voir la liste des bords |
| Facette → bords | Former tous les bords d’une facette par paires | lisible des facettes | Voir Half Edge | Commencez au bord de départ de la facette et courez vers la gauche. Le bord suivant appartient à la même facette, puis continuez dans la même direction de course. Si aucun successeur n’est trouvé pour la première fois, la direction de la course est inversée. Le successeur appartient à la même facette, puis continue dans cette direction, sinon la rupture. La direction de la course peut changer plusieurs fois. À un moment donné, vous arrivez au bord de départ. Alors vous pouvez vous arrêter. |
| Facette → pierres angulaires | Lisez simplement des facettes | Exécutez “Facet → Bords” et lisez les points clés associés en temps constant | Voir Half Edge | Exécutez “Facet → Bords” et lisez les points des bords, jetez les doubles points. |
| Facette → facette voisine | Déterminez tous les bords de la facette à vérifier et voyez pour chaque bord si les autres facettes contiennent également ce bord. | Exécutez “Facet → Bords”, puis lisez les facettes associées directement à partir des bords | Exécutez “facettes → bords” et lisez la zone adjacente pour chaque bord | Voir le bord ailé |
Résumé [ Modifier | Modifier le texte source ]]
Comme vous pouvez le voir, le bord ailé et la structure demi-bord des informations qu’il contient sont presque identiques. Par conséquent, ils ont presque les mêmes termes de recherche. Le demi-bord est un peu mieux dans les demandes les plus complexes. En raison du pointeur d’un point sur un bord de départ associé lors de la recherche de tous les bords d’un point, seuls ceux-ci doivent être touchés. La liste des nœuds est tout aussi bonne dès le départ et la liste des bords est aussi bonne que la liste des bords ailés, mais a besoin d’un peu plus d’espace de stockage, car le bord ailé n’a qu’à prendre une facette.
- ↑ un b Jens Neumann: Procédure pour la modélisation et la simulation ADHOC des systèmes de masse de ressort spatiale à utiliser dans des simulations de manutention basées sur la réalité virtuelle. Université technique de Berlin, Fraunhofer IRB Verlag, 2009, ISBN 978-3-8167-7954-4.
- ↑ Oliver Burgert: Formation du modèle II- Réseaux nodaux – Systèmes de planification médicale et de simulation. ( Mémento des Originaux à partir du 10 août 2007 Archives Internet ) Info: Le lien d’archive a été utilisé automatiquement et non encore vérifié. Veuillez vérifier le lien d’origine et d’archiver en fonction des instructions, puis supprimez cette note. (PDF) Université de Leipzig, 2005.
Recent Comments