# CS110 Chapter Notes - Chapter 4: Computational Geometry, Graham Scan

## Document Summary

This section is dedicated to exploring more custom functions that may come in handy in computational geometry. If a line segment is in clockwise direction, when traversing from the line segment to another line segment made up of the end of the former and the midpoint of polygon, one would turn right. Add the remaining (unused) line segments in the convex hull to the edge set. Repeat the following until edge set has only 3 elements (with i=0 and empty. If edge[i] and edge[i+1] are in anti-clockwise orientation, add edge[i] to. If they are in clockwise direction, form triangle from edge[i] and edge[i+1], add new resultant edge to new set, and add elements of edge from i+2 until the end; reset i=0, edge=new,new={} Form triangle from the remaining elements in edge set: format: triangle* triangulation(point*p,size_t n, graham scan algorithm with its auxiliary functions: 6: main auxiliary function, main triangulation function: