MAC0331

Computational Geometry

Implementation of geometric algorithms

• Detection of segments intersection

• Polygon triangulation Lee & Preparata

• Convex polygon partition Hertel & Mehlhorn (using Lee & Preparata triangulation algorithm)

• Convex hull using gift wrapping and Graham algorithms

Gift wrapping:

Graham: