36:
447:
is a point set triangulation of a set of two-dimensional points together with elevations for each point. Lifting each point from the plane to its elevated height lifts the triangles of the triangulation into three-dimensional surfaces, which form an approximation of a three-dimensional
752:
of a point set is a partition of the convex hull of the points into pseudotriangles—polygons that, like triangles, have exactly three convex vertices. As in point set triangulations, pseudotriangulations are required to have their vertices at the given input points.
704:) underlying a computation. In this case, the triangles must form a subdivision of the domain to be simulated, but instead of restricting the vertices to input points, it is allowed to add additional
708:
as vertices. In order to be suitable as finite element meshes, a triangulation must have well-shaped triangles, according to criteria that depend on the details of the finite element simulation (see
394:
687:
642:
459:
into triangles meeting edge-to-edge, again with the property that the set of triangle vertices coincides with the set of vertices of the polygon. Polygon triangulations may be found in
575:
316:
243:
214:
426:
602:
526:
546:
499:
340:
283:
263:
185:
604:
such that they cover the entire surface, the intersection on any pair of subsets is either empty, an edge or a vertex and if the intersection the intersection
163:
Different types of triangulations may be defined, depending both on what geometric object is to be subdivided and on how the subdivision is determined.
53:
705:
863:
811:
468:
100:
911:
836:
786:
432:(for points in general position, the set of simplices that are circumscribed by an open ball that contains no input points) and the
119:
748:
The concept of a triangulation may also be generalized somewhat to subdivisions into shapes related to triangles. In particular, a
72:
79:
444:
57:
360:
433:
86:
721:
472:
68:
647:
607:
732:
463:
and form the basis of several important geometric algorithms, including a simple approximate solution to the
350:
155:
In most instances, the triangles of a triangulation are required to meet edge-to-edge and vertex-to-vertex.
46:
725:
429:
774:
693:
479:
452:
551:
292:
219:
190:
770:
407:
93:
749:
717:
464:
404:
of any dimension or not at all and such that the set of vertices of the simplices are contained in
471:
is an adaptation of the
Delaunay triangulation from point sets to polygons or, more generally, to
580:
504:
343:
17:
884:
859:
832:
807:
782:
531:
484:
144:
into triangles, and by extension the subdivision of a higher-dimension geometric object into
141:
802:
Berg, Mark
Theodoor de; Kreveld, Marc van; Overmars, Mark H.; Schwarzkopf, Otfried (2000).
401:
713:
354:
325:
268:
248:
170:
905:
709:
701:
285:
intersect in a common face (a simplex of any lower dimension) or not at all, and any
712:); for instance, some methods require that all triangles be right or acute, forming
887:
736:
697:
148:. Triangulations of a three-dimensional volume would involve subdividing it into
460:
440:
397:
286:
35:
400:
of the points into simplices such that any two simplices intersect in a common
319:
149:
892:
853:
133:
456:
145:
436:(the point set triangulation minimizing the sum of the edge lengths).
428:. Frequently used and studied point set triangulations include the
29:
735:
of a space generally refer to simplicial complexes that are
413:
366:
806:(2 ed.). Berlin Heidelberg: Springer. pp. 45–61.
779:
Triangulations, Structures for
Algorithms and Applications
389:{\displaystyle {\mathcal {P}}\subset \mathbb {R} ^{d}}
265:-dimensional simplices such that any two simplices in
650:
610:
583:
554:
534:
507:
487:
410:
363:
328:
295:
271:
251:
222:
193:
173:
804:
Computational geometry: algorithms and applications
60:. Unsourced material may be challenged and removed.
689:is an isometry of the plane on that intersection.
681:
636:
596:
569:
540:
520:
493:
420:
388:
334:
310:
277:
257:
237:
208:
179:
716:. Many meshing techniques are known, including
831:. European Mathematical Society. p. 510.
548:homeomorphic to a non degenerate triangle in
27:Subdivision of a planar object into triangles
8:
682:{\displaystyle f_{\alpha }f_{\beta }^{-1}}
637:{\displaystyle T_{\alpha }\cap T_{\beta }}
670:
665:
655:
649:
628:
615:
609:
588:
582:
561:
557:
556:
553:
533:
512:
506:
486:
412:
411:
409:
380:
376:
375:
365:
364:
362:
327:
302:
298:
297:
294:
270:
250:
229:
225:
224:
221:
200:
196:
195:
192:
172:
120:Learn how and when to remove this message
762:
696:, triangulations are often used as the
501:is a set of subset of compact spaces
7:
731:In more general topological spaces,
58:adding citations to reliable sources
852:Basener, William F. (2006-10-20).
535:
488:
469:constrained Delaunay triangulation
342:. That is, it is a locally finite
25:
18:Triangulation (advanced geometry)
570:{\displaystyle \mathbb {R} ^{2}}
311:{\displaystyle \mathbb {R} ^{d}}
238:{\displaystyle \mathbb {R} ^{d}}
209:{\displaystyle \mathbb {R} ^{d}}
34:
827:Papadopoulos, Athanase (2007).
45:needs additional citations for
829:Handbook of Teichmüller Theory
445:triangulated irregular network
421:{\displaystyle {\mathcal {P}}}
1:
855:Topology and Its Applications
353:, i.e., a triangulation of a
346:that covers the entire space.
69:"Triangulation" geometry
455:is a subdivision of a given
434:minimum-weight triangulation
597:{\displaystyle f_{\alpha }}
521:{\displaystyle T_{\alpha }}
473:planar straight-line graphs
928:
781:. Vol. 25. Springer.
480:triangulation of a surface
396:, is a subdivision of the
912:Triangulation (geometry)
858:. Wiley. pp. 3–14.
722:Chew's second algorithm
541:{\displaystyle \Sigma }
494:{\displaystyle \Sigma }
351:point-set triangulation
683:
638:
598:
571:
542:
522:
495:
430:Delaunay triangulation
422:
390:
336:
312:
279:
259:
239:
210:
181:
140:is a subdivision of a
694:finite element method
684:
639:
599:
572:
543:
523:
496:
453:polygon triangulation
423:
391:
337:
313:
280:
260:
240:
211:
182:
648:
608:
581:
552:
532:
505:
485:
408:
361:
326:
293:
269:
249:
220:
216:is a subdivision of
191:
171:
54:improve this article
750:pseudotriangulation
726:Ruppert's algorithm
720:algorithms such as
718:Delaunay refinement
678:
644:is not empty then
465:art gallery problem
885:Weisstein, Eric W.
771:De Loera, Jesús A.
679:
661:
634:
594:
567:
538:
518:
491:
418:
386:
344:simplicial complex
332:
322:many simplices in
308:
275:
255:
235:
206:
177:
865:978-0-471-68755-9
813:978-3-540-65620-3
775:Santos, Francisco
700:(in this case, a
335:{\displaystyle T}
278:{\displaystyle T}
258:{\displaystyle d}
180:{\displaystyle T}
152:packed together.
130:
129:
122:
104:
16:(Redirected from
919:
898:
897:
870:
869:
849:
843:
842:
824:
818:
817:
799:
793:
792:
773:; Rambau, Jörg;
767:
714:nonobtuse meshes
688:
686:
685:
680:
677:
669:
660:
659:
643:
641:
640:
635:
633:
632:
620:
619:
603:
601:
600:
595:
593:
592:
576:
574:
573:
568:
566:
565:
560:
547:
545:
544:
539:
527:
525:
524:
519:
517:
516:
500:
498:
497:
492:
427:
425:
424:
419:
417:
416:
395:
393:
392:
387:
385:
384:
379:
370:
369:
341:
339:
338:
333:
318:intersects only
317:
315:
314:
309:
307:
306:
301:
284:
282:
281:
276:
264:
262:
261:
256:
244:
242:
241:
236:
234:
233:
228:
215:
213:
212:
207:
205:
204:
199:
186:
184:
183:
178:
167:A triangulation
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
927:
926:
922:
921:
920:
918:
917:
916:
902:
901:
888:"Triangulation"
883:
882:
879:
874:
873:
866:
851:
850:
846:
839:
826:
825:
821:
814:
801:
800:
796:
789:
769:
768:
764:
759:
746:
651:
646:
645:
624:
611:
606:
605:
584:
579:
578:
555:
550:
549:
530:
529:
508:
503:
502:
483:
482:
406:
405:
374:
359:
358:
324:
323:
296:
291:
290:
267:
266:
247:
246:
223:
218:
217:
194:
189:
188:
169:
168:
161:
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
925:
923:
915:
914:
904:
903:
900:
899:
878:
877:External links
875:
872:
871:
864:
844:
837:
819:
812:
794:
787:
761:
760:
758:
755:
745:
744:Generalization
742:
741:
740:
733:triangulations
729:
706:Steiner points
690:
676:
673:
668:
664:
658:
654:
631:
627:
623:
618:
614:
591:
587:
564:
559:
537:
515:
511:
490:
476:
449:
437:
415:
383:
378:
373:
368:
357:set of points
347:
331:
305:
300:
274:
254:
232:
227:
203:
198:
176:
160:
157:
128:
127:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
924:
913:
910:
909:
907:
895:
894:
889:
886:
881:
880:
876:
867:
861:
857:
856:
848:
845:
840:
838:9783037190296
834:
830:
823:
820:
815:
809:
805:
798:
795:
790:
788:9783642129711
784:
780:
776:
772:
766:
763:
756:
754:
751:
743:
739:to the space.
738:
734:
730:
727:
723:
719:
715:
711:
707:
703:
702:triangle mesh
699:
695:
691:
674:
671:
666:
662:
656:
652:
629:
625:
621:
616:
612:
589:
585:
562:
513:
509:
481:
477:
474:
470:
466:
462:
458:
454:
450:
446:
442:
438:
435:
431:
403:
399:
381:
371:
356:
352:
348:
345:
329:
321:
303:
288:
272:
252:
230:
201:
174:
166:
165:
164:
158:
156:
153:
151:
147:
143:
142:planar object
139:
138:triangulation
135:
124:
121:
113:
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: –
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
891:
854:
847:
828:
822:
803:
797:
778:
765:
747:
737:homeomorphic
710:mesh quality
478:A Euclidean
162:
154:
137:
131:
116:
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
461:linear time
441:cartography
398:convex hull
287:bounded set
757:References
150:tetrahedra
80:newspapers
893:MathWorld
672:−
667:β
657:α
630:β
622:∩
617:α
590:α
536:Σ
514:α
489:Σ
448:landform.
372:⊂
146:simplices
906:Category
777:(2010).
355:discrete
320:finitely
134:geometry
110:May 2024
692:In the
457:polygon
94:scholar
862:
835:
810:
785:
467:. The
96:
89:
82:
75:
67:
245:into
159:Types
101:JSTOR
87:books
860:ISBN
833:ISBN
808:ISBN
783:ISBN
724:and
698:mesh
577:via
443:, a
402:face
136:, a
73:news
528:of
439:In
289:in
187:of
132:In
56:by
908::
890:.
451:A
349:A
896:.
868:.
841:.
816:.
791:.
728:.
675:1
663:f
653:f
626:T
613:T
586:f
563:2
558:R
510:T
475:.
414:P
382:d
377:R
367:P
330:T
304:d
299:R
273:T
253:d
231:d
226:R
202:d
197:R
175:T
123:)
117:(
112:)
108:(
98:·
91:·
84:·
77:·
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
