Computational Geometry
Ongoing work
Computational Geometry (CG) is “the algorithmic study of geometric problems” [Skiena 1998]
 Point location
 Collinearity of three points in a plane
 …
Point location
Deals with the following query: In which region does a given point p(x,y) lie in a 2D plane containing polygon regions.
 https://en.wikipedia.org/wiki/Point_location
 http://www3.cs.stonybrook.edu/~algorith/files/pointlocation.shtml
Collinearity of three points in a plane
 If three points lie in a line, they form a degenerate triangle whose area is 0
 From the three given points, create two vectors emanating from same point.
 Imagine that these two vectors are the adjacent edges of a parallelogram, then the area of parallelogram is equal the vector cross product of the two adjacent edges.
 The diagonal of this parallelogram divides it into two triangles whose area is equal to the area of triangle formed by the three given points.
 Source: An excellent story on how Brian Hayes stumbled on this algorithm is presented in Chapter 33: Writing Programs for “The Book” of this book.
References
 The Computational Geometry Algorithms Library, http://www.cgal.org, Accessed on 23 July 2017.

Skiena, Steven S. The algorithm design manual: Text. Vol. 1. Springer Science & Business Media, 1998.
Advertisements