To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Constrained Delaunay triangulation

From Wikipedia, the free encyclopedia

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges,[1][2] unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

YouTube Encyclopedic

  • 1/3
    Views:
    2 161
    7 647
    16 227
  • Test: Constrained Delaunay Triangulation
  • Constrained Delaunay Triangulation
  • Mod-08 Lec-19 Delaunay Triangulation.

Transcription

Definition

The input to the constrained Delaunay triangulation problem is a planar straight-line graph, a set of points and non-crossing line segments in the plane. The constrained Delaunay triangulation of this input is a triangulation of its convex hull, including all of the input segments as edges, and using only the vertices of the input. For every additional edge added to this input to make it into a triangulation, there should exist a circle through the endpoints of , such that any vertex interior to the circle is blocked from visibility from at least one endpoint of by a segment of the input. This generalizes the defining property of two-dimensional Delaunay triangulations of points, that each edge have a circle through its two endpoints containing no other vertices. A triangulation satisfying these properties always exists.[1]

Jonathan Shewchuk has generalized this definition to constrained Delaunay triangulations of three-dimensional inputs, systems of points and non-crossing segments and triangles in three-dimensional space; however, not every input of this type has a constrained Delaunay triangulation according to his generalized definition.[2]

Algorithms

Several algorithms for computing constrained Delaunay triangulations of planar straight-line graphs in time are known.[1][3] The constrained Delaunay triangulation of a simple polygon can be constructed in linear time.[4]

Applications

In topographic surveying, one constructs a triangulation from points shot in the field. If an edge of the triangulation crosses a river, the resulting surface does not accurately model the path of the river. So one draws break lines along rivers, edges of roads, mountain ridges, and the like. The break lines are used as constraints when constructing the triangulation.

Constrained Delaunay triangulation can also be used in Delaunay refinement methods for mesh generation, as a way to force the mesh to conform with the domain boundaries as it is being refined.

References

  1. ^ a b c Chew, L. Paul (1989), "Constrained Delaunay triangulations", Algorithmica, 4 (1): 97–108, doi:10.1007/BF01553881, MR 0983658, S2CID 189918468
  2. ^ a b Shewchuk, Jonathan Richard (2008), "General-dimensional constrained Delaunay and constrained regular triangulations. I. Combinatorial properties", Discrete & Computational Geometry, 39 (1–3): 580–637, doi:10.1007/s00454-008-9060-3, MR 2383774
  3. ^ Wang, Cao An; Schubert, Lenhart K. (1987), "An optimal algorithm for constructing the Delaunay triangulation of a set of line segments", in Soule, D. (ed.), Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, ACM, pp. 223–232, doi:10.1145/41958.41982, S2CID 18490297
  4. ^ Chin, Francis; Wang, Cao An (1999), "Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time", SIAM Journal on Computing, 28 (2): 471–486, doi:10.1137/S0097539795285916, hdl:10722/47094, MR 1634357, S2CID 28966377

External links

  • [1] Open Source implementation.
This page was last edited on 22 June 2023, at 02:24
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.