Computational Geometry Lecture Notes

Lecture Notes for Introduction to Computational Geometry (Com S 418/518) Yan-Bin Jia, Iowa State University Point Set Triangulation Outline: I. Height interpolation II. Existence and complexity of a triangulation III. Legal Triangulation Textbook: Computational Geometry: Algorithms and Applications (3rd ed.) by M. de Berg et al., Springer-Verlag, 2008.

I. Terrain Terrain: 2-dimensional (2D) surface in 3D space such that every vertical line intersects in 1 point. Terrain (?) ? ? :? 2 ? ? ? (?) ? Domain Height ? 2 ? 2 ? = ?2+ ?2 , ? 2cos?cosh ,2sin?cosh Landscape Paraboloid (terrain) Catenoid (Com S 477/577) (not a terrain) (https://github.com/Gruftikus/lltool)

Height Interpolation Sample the value of at a finite set ? = {?1,?2, ,??} ? of points. Task: Approximate (?) for every ? ?\?. ?? ? ? ?1 Na ve approach: ? = (??) where |? ??| |? ??| for all ?? ? (i.e., ?? is the closest to ? among all points in ?). ?(log?) using the Voronoi diagram of ? for fast location of ??. Not natural (stairlike) Not continuous

Better Interpolation Determine a triangulation of ?. Lift every sample point to its height. Point Polyhedral terrain ? ? Triangulation What is the height at ?? How to triangulate ?? Which triangulation is the most appropriate for approximating a terrain?

Barycentric Interpolation ? Point ?3 ?2 ?1 ?1 ? ?1: area of ??2?3 (facing ?1) ?2: area of ??3?1 (facing ?2) ?3: area of ??1?2 (facing ?3) ?3 ?2 ? = ?1+ ?2+ ?3: area of ?1?2?3 ? =?1 ??1+?2 ??2+?3 ? =?1 ? ?1 +?2 ? ?2 +?3 ??3 ? ?3 ?1 ?,?2 ?,?3 Barycentric coordinates of ?: ?

II. Triangulation of a Planar Point Set A planar subdivision ? is maximal if no (straight) edge connecting two vertices can be added without destroying its planarity. A triangulation of a point set ? = {?1,?2, ,??} is the maximal planar subdivision whose vertex set is ?. ?3 ?4 ?1 ?2 ?5 ?6 ?7 ?8

Existence of a Triangulation Every bounded face of such a planar subdivision with vertex set ? is a polygon. Point Any polygon can be triangulated! Union of bounded faces is the convex hull of ?. Unbounded face is the complement of the convex hull (i.e., the remaining region in the plane).

Complexity of Triangulation Assumption The ? points in ? are not all collinear. Point Theorem Any triangulation of ? has 2? 2 ? triangles and 3? 3 ? edges. # points from ? on its convex hull Proof? is a triangulation with ? triangles. ??= #edges ??= #faces = ? + 1 Count edges in two different ways: 1. Every triangle has three edges. The unbounded face has ? edges. 2. Every edge is incident to two faces. 3? + ? = 2?? ??= (3? + ?)/2

Complexity (contd) Euler s formula: Point ? ??+ ??= 2 ??= ? + 1 ? = 2 ? + ?? 1 ??= (3? + ?)/2 ? = 2? 2 ? ??= (3? + ?)/2 ??= 3? 3 ?

III. Angle Vector ?: triangulation with ? triangles which have 3? angles. Point Order these angles into an angle vector: ? ? = ?1,?2, , ?3? ?1 ?2 ?3? ? is another triangulation with angle vector: ? ? = ?1 ,?2 , ,?3? ? ? > ?(? ) if there exists ? with 1 ? 3? such that for all ? < ? and ??> ?? (lexicographical order) ??= ?? ? is angle optimal if ? ? ?(? ) for all triangulations ? .

Thales Theorem Point ? ? circle ? ? ? ? ? ? Four angles subtended by the arc ??: ??? > ??? = ??? > ???

Illegal Edge An edge ? = ???? is incident to two triangles. Point ?? ?? edge flip ?2 ?4 ?2 ?? ?? ?3 ?5 ? ?1 ?6 ?4 ?1 ?3 ?6 ?5 ?? ?? ?? ?? ?6,?4,?1,?3,?2,?5 ?4 ,?3 ,?5 ,?2 ,?6 ,?1 min 1 ? 6??< min 1 ? 6?? ? is an illegal edge if = ?4 = ?6 We can locally increase the smallest angle by flipping edges.

Edge Flip ? ? Point ?? ?? ?2 ?4 ?2 ?? ?? ?3 ?5 ? ?1 ?6 ?6 ?4 ?1 ?3 ?5 ?? ?? ?? ?? Triangulation ? (after flipping ?) Triangulation ? (before flipping ?) It can be shown that ? ? > ? ? . Computing ?1,?2, , ?6 and ?1 is unnecessary! ,?2 , ,?6

Determining an Illegal Edge ? Theorem Edge ???? is illegal iff ?? lies in the interior of circle ? determined by ??,??,??. ? ? ?? Proof ( ) Let ? and ? be the triangulations of the 4 points ??,??,??,?? before and after the flip. ?? ?? ?????? ??????> ??? ?? subtended by > ?? subtended by ???? ?????? and ?????? are not the smallest angle in ?. arc arc ???? = ?????? ??????> ????? Similarly, ?????? and ?????? are not the smallest angle in ? .

Contd ? We need only consider the remaining eight angles, four from each triangulation. ? ? ?? ? ? ? ?? ?????? ?????? < ?? ?????? ?????? < ?? = ????? < ????? = ?????? ?????? two inscribed angles subtended by arc ??? Thus, the minimum angle in ? is less than the minimum angle in ? . ?????? = ????? ?????? < subtended by arc ??? ( ) Omitted.

Special Case and Legal Triangulation ??,??,??,?? are cocircular. Point ?? ?? Both ???? and ???? are legal! ?? ?? A legal triangulation has no illegal edge.

Generating a Legal Triangulation LegalTriangulation(?) Point 1. while ? contains an illegal edge ???? 2. do let ?????? and ?????? be the two triangles adjacent to ???? 3. remove ???? 4. add ???? 5. return ? ?? ?? ?? ?? Angle vector ?(?) increases in every iteration. #triangulations is finite. The while loop will terminate with a legal triangulation. Too slow!