Computational Geometry Basics

In minutes

Computational geometry is about algorithms in a geometric setting that are efficient and numerically stable. As we will see, these extra requirements rule out some approaches that readily come to mind.

In this post, we will focus on the 2D setting. We cover two problems with numerous applications, testing whether two line segments intersect, and computing the convex hull of a set of points. We start with an important operation that underlies both: checking whether one point is clockwise of another. This also has numerous applications other than the two we focus on.

In the previous paragraph, by “application” we mean both direct practical applications and indirect ones. By indirect ones, we mean more advanced computational geometry problems in which the covered algortithms play an important role.

A Key Basic Operation

Let’s start here; we’ll soon see why. Given three points p, q, and r, we want to know whether, in going from p to q to r, is there a left turn at q, a right turn at q, or neither.

Figure: In going from p0 to p1: to p2 we make a right turn, to p3 we make a left turn

This operation, let’s call it turn_type(p, q, r), has a number of uses.

Here is one:

Line Segment Intersection Testing