Computational Geometry Cheatsheet

2D Points and Vectors

2D Vector

Vector Between Two 2D Points

Norm of a 2D Vector

Euclidean Distance Between Two 2D Points

For two pointsandin a plane:

2D Manhattan Distance

2D Dot Product

For two vectorsand:

Distance from a Point to a Line

For a pointand a line represented by:

3D Points and Vectors

3D Vector

Vector Between Two 3D Points

Norm 3D

Distance Between Two 3D Points

For two pointsand:

3D Dot Product

For two vectorsand:

3D Cross Product

For two vectorsand:

The cross product generates a vector perpendicular to the two given vectors, useful for normal calculations on surfaces.

Normalization

Normalization of a Vector

A normalized vector has a magnitude of 1 and is calculated by dividing each component by the magnitude of the vector:

Important for working with directions in graphics.

Angle Between Two Vectors

For two vectorsand:

2D Polygons

Perimeter of a Polygon

whereare the lengths of the sides.

Or by its coordinates

Area of a Polygon

For a polygon with vertices:

where

Convexity of a Polygon

A polygon is convex if all internal angles are less thanor if there are no points that can be found outside of the polygon by drawing a line between any two points of the polygon.

Point Inside a Polygon

Given a polygonand a point, the crossing algorithm counts how many times a line projected fromto infinity crosses the sides of the polygon.

• If the number of crossings is odd,is inside the polygon
• If even, it is outside.

2D Transformations

Translation

For a pointtranslated by a vector:

Rotation

To rotate a pointaround the origin by an angle:

Scaling

To scale a pointwith factorsand:

3D Transformations

Scaling

Non-Uniform Scaling

Rotation Around theAxis

Rotation Around theAxis

Rotation Around theAxis: