Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2012 | OriginalPaper | Buchkapitel

14. Triangle Mesh Generation: Delaunay Triangulation

verfasst von : Jakob Andreas Bærentzen, Jens Gravesen, François Anton, Henrik Aanæs

Erschienen in: Guide to Computational Geometry Processing

Verlag: Springer London

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

In this chapter, the generation of triangle meshes from points is illustrated via the Delaunay triangulation. Apart from Delaunay triangulation being the most common triangulation method, the aim is also to give an overview of the typical issues of point triangulation in general. As such the aspects of numerical accuracy and constraint triangulation are also covered. Central constructive proofs of Delaunay triangulation are covered along with the connection to Voronoi diagrams and convex hulls. The aim is that the student should be able to complete an exercise in performing Delaunay triangulation after this chapter; as such the flip algorithm is covered in some detail, as well as the geometric primitives in circle and left of. These primitives are the foundation of many triangulation algorithms. The arguably most efficient algorithm for 2D Delaunay triangulation, the divide and conquer algorithm, is also presented.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Convex Hulls
Nächstes Kapitel 3D Surface Registration via Iterative Closest Point (ICP)
Fußnoten
1
If l goes through another point, replace p′ with that.
 
2
Actually, of these six edges the three new ones will be locally Delaunay. To see this, note that before the insertion of the point the triangle t j is Delaunay, and thus has an empty circumcircle. It is seen that a circumcircle of one of the new edges can be constructed completely within this old circumcircle (e.g., by shrinking the old circumcircle), whereby the new edges are locally Delaunay at the outset.
 
3
Both papers contain further references to the subject.
 
4
Note that the center of a Delaunay triangle’s circumcircle need not necessarily be located within that triangle.
 
Literatur
1.
Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Computing in Euclidean Geometry. Lecture Notes Ser. Comput., vol. 1, pp. 23–90. World Scientific, River Edge (1992) CrossRef
2.
Edelsbrunner, H.: Geometry and Topology for Mesh Generation. Cambridge Monographs on Applied and Computational Mathematics, vol. 7, p. 177. Cambridge University Press, Cambridge (2006). 978-0-521-68207-7; Reprint of the 2001 original MATH
3.
4.
5.
Guibas, L., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 74–123 (1985) MATHCrossRef
6.
Guibas, L.J., Knuth, D.E., Sharir, M.: Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica (New York) 7(4), 381–413 (1992) MathSciNetMATHCrossRef
7.
Pion, S., Devillers, O.: Efficient exact geometric predicates for Delaunay triangulations. In: 5th Workshop on Algorithm Engineering and Experiments (ALENEX 03) (2003)
8.
Shewchuk, J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geom. 18, 305–363 (1997) MathSciNetMATHCrossRef
9.
de Berg, M., van Kreveld, M., Overmars, M., Schwarzkopf, O.: Computational Geometry. Algorithms and Applications, p. 365. Springer, Berlin (1997) MATHCrossRef
10.
11.
Gold, C.M., Mioc, D., Anton, F., Sharma, O., Dakowicz, M.: A methodology for automated cartographic data input, drawing and editing using kinetic Delaunay/Voronoi diagrams. In: Studies in Computational Intelligence, vol. 158 (2009). doi:10.​1007/​978-3-540-85126-4
Metadaten
Titel
Triangle Mesh Generation: Delaunay Triangulation
verfasst von
Jakob Andreas Bærentzen
Jens Gravesen
François Anton
Henrik Aanæs
Copyright-Jahr
2012
Verlag
Springer London
Buch
Guide to Computational Geometry Processing

Print ISBN: 978-1-4471-4074-0

Electronic ISBN: 978-1-4471-4075-7

Copyright-Jahr: 2012

DOI
https://doi.org/10.1007/978-1-4471-4075-7_14

Premium Partner

    Bildnachweise