Computational Geometry

Computational geometry refers to the general branch of algorithms and ideas meant for geometry: shapes, lines, points, and other geometric figures. From the study of computational geometry, we have many tools that are useful for programming.

Vectors

Vectors are extremely useful in computational geometry. Vectors are defined extremely broadly in the mathematical world, but for these algorithms, we can define a vector to be a collection of numbers. These numbers represent data in multi-dimensional space (for example, 2-D or 3-D). Vectors have directions and magnitudes (the length of the line segment represented by the vector).

Cross Product

Dot Product

Other Tricks

Area of a Polygon

Distance from a Point to a Line

Whether a Point Is on a Line

Whether Two Points Are on the Same Side of a Line

Whether a Point Is in a Polygon

Line / Line Segment Intersection

Algorithms

The following are some more complex algorithms that use tools from computational geometry. Geometric duality is an interesting concept that turns many problems that do not seem to be geometry-related into geometry problems.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License