7. Computational Geometry I

Introduction

Be aware of:

Floating point errors
- Nearly-parallel lines
- Very thin/long rectangles
- Points very close together
Special cases
- Coincident points
- Intersecting lines
Degenerate cases
- Zero area triangles

This course simplifies this by using integer cartesian grids and avoiding division, square roots, trig etc.

Sidenote - basic matplotlib example:

import matplotlib.pyplot as plt
vertices = [(0,0), (1,2), (2,4)]
vx, vy = zip(*vertices) # Unzip the array into x and y components
axes = plt.axes()
axes.plot(vx, vy, color="blue", marker="o")
plt.show()

Points, Vectors & Lines

Definitions

Point:

Position in space
$(x, y)$ tuple
Uppercase, non-bold, non-italic letters

Vector:

Difference between two points
$(dx, dy)$ tuple
The vector from $A$ to $B$ is $v = (b_x-a_x, b_y-a_y )$
Lowercase, bold, italic letters
Position vector
- Vector from origin to some given point

Basic Operations

Points:

Subtract to get displacement vector
Linear/affine sum:
- $P(\alpha) = (1-\alpha)A + \alpha B$
- Indivisible, two operation operand
- Points on the line between A and B
- $P(0) = A$
- $P(1) = B$
The linear sum is the equation of the line: use this instead of $y = mx + c$ as it does not work with vertical lines

Vectors:

Addition, subtractions
Multiplication by scalar
Addition to a point to get another point
Magnitude: $|v|^2=\sqrt{v_x^2+v_y^2}$
Dot product
Signed triangle area

Vector Operations

Dot Product:

$p \cdot q = p_x q_x + p_y q_y=|p\|q|\cos{\theta}$
$p \cdot q > 0$ when the angle is acute: angle in $(0,90)$ or $(270,360)$
$p \cdot q = 0$ when they are perpendicular

Signed Area/Turn Direction

The area of parallelogram is:

p_x q_y-p_y q_x=|p\|q|\sin{\theta}

This is equivalent to the magnitude of the cross product where $p$ , $q$ are two edge vectors for vectors $B$ and $C$ respectively, relative to the point $A$ .

The area of triangle is half of this.

The area is positive if $b$ is ‘counterclockwise’ to $c$ , centered around $a$ and zero when the points are collinear (parallel).

Checking if $P$ is on the line $(A,B)$ :

Check if signed area 0
To check if it is on the line segment (i.e. Between $A$ and $B$ ):
- $|P,A| \le |A,B|$ and $|P,B|<|A,B|$
- Where $|X,Y|$ is the distance between the points $X$ and $Y$

Turn Direction:

Just check the sign of the signed area (unless the area is zero)

Line Segment Intersection:

Two line segments $AB$ and $CD$ intersect iff $C$ and $D$ are on opposite sides of the line $AB$ and vice-versa
True if isCCW(A,B,D) != isCCW(A,B,C) && isCCW(C,D,A) != isCCW(C,D,B) (where the first argument is the origin)

Degenerate cases:

One point on the line
Sharing a point
All four points collinear

Simple Polygons

By convention, vertices are in counter-clockwise order.

Convex Polygons:

Every interior angle less than 180 degrees
- Strictly less than for strictly convex polygon
Every counter-clockwise traversal turns left at every vertex (or goes straight)

Point Inclusion Test

Convex Polygon

For a convex polygon, a point is in a polygon (PiP) if it is on the left side of every edge for an anticlockwise traversal of the polygon:

all([isCCW(vertex[i], vertex[(i + 1) % len(vertex)], P) for i in range(len(vertex))])

Simple Polygon

Create a semi-infinite horizontal line starting from $P$ going either left or right
The point is inside the polygon iff it intersects the polygon an odd number of times
The line only needs to extend to past the maximum $x$ value for the polygon’s edges

Special cases:

The line goes through a vertex
- On the ‘inside’: count 0 or 2 times
- Otherwise: count 1 time
Goes along an edge

The correct way to solve this is to:

Ignore horizontal edges
If edge directed upwards, count the start vertex as an intersection
If edge directed down, count the end vertex as an intersection

The hacky solution: all vertices are on an integer grid, so simply move $P$ up by a very small amount (e.g. $10^{-8}$ ).

Improvements:

Find the rectangle that encompasses the polygon
- If its not in the rectangle, then it can’t be inside

Convex Hull Problem

For a finite set of points, the convex hull is the smallest convex polygon enclosing all points. The convex hull:

Is unique
Contains every point in the set
has $(x_{min}, ?)$ , $(x_{max}, ?)$ , $(?, y_{min})$ and $(?, y_{max})$ as vertices of the convex hull

Naïve solution:

Construct all possible edges using pairs of points
For every other point, check if it lies on the left side of the edge. If so, it belongs to the convex hull
$O(n^3)$

Gift Wrap Algorithm

Start from the point with the minimum $y$ coordinate (or max $y$ , or min/max $x$ )
- Choose the left-most one if multiple points have the same minimum
Select the ‘rightmost’ point from the perspective of the current point $A$
- Pick any point $B$
- For all points $C$
  - Check if $C$ is to the right of $AB$
  - If so, $B = C$
- The current $B$ is part of the convex hull. Repeat until a closed loop is formed
Worst case $O(n^2)$
Normal case $O(mn)$ , where $m$ is the number of vertices in the convex hull

Graham-Scan Algorithm

An $O(n\log{n})$ algorithm. First construct a simple closed path that includes all points:

Point $0$ will have the minimum $y$ value, and so is guaranteed to be on the convex hull
Create a line centered around point $0$ and pointing right
Rotate the line anticlockwise. When a vertex is found, add them to the list - we are essentially sorting the vertices by angle
Connect the vertices in the sorted list to create the simple closed path
Not all vertices will be on the convex hull, so the concavities need to be filled in

Sorting without calculating angles

We don’t need to know the angle: only the ordering. This can be done using isCCW, Python’s built in sort function (which will be $n\log{n}$ ), and from functools import cmp\_to\_key or by defining a SortKey class with a custom __lt__ operator and converting the point to that class in the sort function’s key lambda.

Consider edge cases:

$P_1$ or $P_2$ are the anchor
Several points colinear with $P_0$ (i.e. on a straight line)
- Don’t worry about them

Concavities:

$P_0$ and $P_1$ always on the convex hull
$P_2$ may not be

Initialize a stack with $[P_0, P_1, P_2]$ :

Check if the next point, $n$ , is on the left edge of the line connecting $P_{n-2}$ and $P_{n-1}$
If so, add the point to the stack
Otherwise, pop from the stack until this is true

Complexity:

Step 1: find the point with the minimum $y$ Y value: $O(n)$
Step 2: sort operation: $O(n\log{n})$
Step 3: initialize hull
Step 4: generate the convex hull
- Not $O(n^2)$ as although the nested while loop may run several times, it can only remove previously added elements, so you can only ever pop $n$ elements
- Hence, it is $2n \in O(n)$