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