# Dr. Abhishek Dutta

## 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.

#### 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.

Written by abhishekdutta

July 23, 2017 at 7:38 am