Geom

Computational Geometry

• The Algorithmist

Basics

Lines

• y = mx + b
• ax + by + c = 0

Circles

• (x-a)**2 + (y-b)**2 = r**2 ((a, b) is center)
• Circumference: C = 2 * pi * r
• Arc length: s = (theta / 360) * C
• pi radians = 180 degrees (look for degree-to-radian conversion functions in the stdlib)
• Length of chord: l = 2 * r**2 * (1 - cos(theta))
• Area: A = pi * r**2
• Area of sector: a = theta / 360 * A
• The area of a Segment of a circle can be found by subtracting the area of the corresponding Sector with the area of an Isosceles Triangle with sides: r, r, and Chord-length

Triangles

• Area: 1/2 * b * h
• Perimeter p is the sum of the sides
• Semiperimeter s is 1/2 * p
• Heron's Formula: A = sqrt( s × (s − a) × (s − b) × (s − c) )
• Radius of inscribed circle: r = A / s
• Radius of outscribed circle: R = (a × b × c) / (4 × A)
• Law of Cosines: c**2 = a**2 + b**2 − 2 × a × b × cos(γ)
• Law of Sines: (a / sin(α)) = (b / sin(β)) = (c / sin(γ))

Rectangles

• Trapezoid Area: A = 0.5 × ( w1 + w2 ) × h

Great-Circle Distance

The distance between two points on the surface of a sphere. The points are specified by their Latitude and Longitude. Latitude and Longitude are given by (φ, λ). In most programming languages, trig functions take radians.

• d = r * Δσ
• Δσ = arccos( sin(φ_1) * sin(φ_2) + cos(φ_1) * cos(φ_2) * cos(Δλ) )
• Δλ = λ_2 - λ_1

Polygons

The area A of an n-sided polygon (either convex or concave) with n pairs of vertex coordinates given in some order (clockwise or counter-clockwise) is:

         | x1  y1 |
         | x2  y2 |
     1   | x3  y3 |
A  = - * | .   .  | = 1/2 * (x1y2 + x2y3 + y3y4 + ... + xny1
     2   | .   .  |         -x2y1 - x3y2 - x3y4 - ... - x1yn)
         | .   .  |
         | xn  yn |

Code:

struct point { int x, y; } // a point has two members

int determinant(vector<point> P) { // default: integer computation
    int result = 0, x1, y1, x2, y2;
    for (int i = 0; i < P.size(); i++) {
        x1 = P[i].x; x2 = P[(i + 1) % P.size()].x;
        y1 = P[i].y; y2 = P[(i + 1) % P.size()].y;
        result += (x1 * y2 - x2 * y1);
    }
    return result;
}

// area is half of the determinant and the result may be a non-integer
double area(vector<point> P) { return fabs(determinant(P)) / 2.0); }

Testing if a polygon is convex (repeat this for each set of three consecutive points):

int turn(point p, point q, point r) {
    int result = (r.x - q.x) * (p.y - q.y) - (r.y - q.y) * (p.x - q.x);
    if (result < 0) return -1; // P->Q->R is a right turn
    if (result > 0) return  1; // P->Q->R is a left turn
    return 0; // P->Q->R is a straight line, i.e. P, Q, R are collinear
}

// Note: sometimes, we change the ’> 0’ to ’>= 0’ to accept collinear points
bool ccw(point p, point q, point r) { return (turn(p, q, r) > 0); }

Other

Graham Scan (Convex Hull)

• Convex hull
• Convex hull algorithms
• Graham scan

Pseudocode (using ccw from above):

let N           = number of points
let points[N+1] = the array of points
swap points[1] with the point with the lowest y-coordinate
sort points by polar angle with points[1]

# We want points[0] to be a sentinel point that will stop the loop.
let points[0] = points[N]

# M will denote the number of points on the convex hull.
let M = 1
for i = 2 to N:
    # Find next valid point on convex hull.
    while ccw(points[M-1], points[M], points[i]) <= 0:
          if M > 1:
                  M -= 1
          # All points are collinear
          else if i == N:
                  break
          else
                  i += 1

    # Update M and swap points[i] to the correct place.
    M += 1
    swap points[M] with points[i]

Intersections

Segment Intersection

Objects

Divide And Conquer