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.