DS&A

Polygons

A polygon is any shape made of straight-line segments. Polygons are especially important in computer graphics and games, since they’re used in vector image formats and 3D models.

Polygon

The simplest way to represent a polygon is a list of points:

Alternatively, we could define a class called Polygon to hold a list of points.(1) Before working with a library or API, it’s important to check if there are any extra requirements — some require the points to be listed clockwise or anticlockwise, and sometimes the first point has to be repeated at the end of the list.(2)

Operations

As with any other type, a polygon isn’t just data — here are some operations a polygon might support:

• Create a polygon with a given list of points.
• Iterate over the points, in sequence.
• Iterate over the edges (pairs of adjacent points), in sequence.
• Get the area.
• Test whether the polygon contains a given point.
• Test whether the points are listed clockwise or anticlockwise.
• Get the minimum bounding rectangle.
• Translate the polygon by a given vector.

Point-in-polygon

Let’s consider the problem of testing whether a polygon contains a point.

• Problem: test whether a polygon contains a given point.
  • Input: a polygon, represented as a list of points.
  • Input: a point.
  • Output: a Boolean indicating whether the point is in the polygon.

This is considerably more challenging than the same problem for a rectangle. Humans can just look at the point and see whether or not it’s in the polygon — but an algorithm has to work with numbers alone. This is the kind of problem which, if it comes up, the best thing to do is use an existing algorithm rather than try to write a new one.

That said, it’s worth trying to understand a solution, to practice thinking about problems from the computer’s perspective.

Consider the model below:

Imagine firing a laser beam out from the red point. The laser beam may pass in and out of the polygon several times; count how many edges it passes through:

• If the number is even, the laser beam started outside the polygon.
• If the number is odd, the laser beam started inside the polygon.

This is called the even–odd rule. It works because each time the laser beam passes through an edge, it flips between “out” and “in”; the laser beam definitely ends up “out”, so if it flips an even number of times then it must have started “out”.

That means we can split the problem into subproblems:

• Subproblem: Iterate over the edges in the polygon.
• Subproblem: Test whether the laser passes through a given edge.
• Subproblem: Count the number of edges the laser passes through.
• Subproblem: Determine whether that number is odd or even.

Each of these subproblems can be solved computationally, using the x and y coordinates of the points. There are some tricky details to get right if you actually want to implement it yourself — but I don’t recommend doing this.

Footnotes

1. This is worthwhile if we want to store additional data, such as colour or line width.
2. This makes it easier to iterate over a polygon’s edges.

• Tags: 
• geometry, data structures, algorithms