Enumeration of Polygon Edges from Vertex Windings

Sean Barrett, April 2008 (a paraphrase of Efficient Polygon Edge Enumeration which was published in the Journal of Graphics Tools Volume 10, Number 2)

Abstract

Enumerating the pairs of vertices that define the edges of a polygon is typically done using a modulo operation or a comparison. It can usually be done with equally simple code that avoids both branches and division operations. This technique has been in use for a long time but remains unknown to most practioners.

Scenario

Given an array of vertices (and a count) describing a polygon as a winding, it is straightforward to enumerate the vertices; we can refer to each vertex by its index within the array. It is only slightly less straightforward to enumerate the pairs of vertices that define the edges:

int i,j;
for (i=0; i < n; ++i) {
   j = (i+1) % n;
   ... edge is <i,j> ...
}

(Here I omit any reference to the vertex array itself, since the the technique presented here is purely the generation of these indices.)

Typically, for example when clipping polygons, we do not require enumerating the edges in exactly this order. We require them in clockwise (or counter-clockwise) order, but which edge comes first does not matter. If this is the case, then an alternative, simpler and more efficient approach is possible.

Solution

The loop presented above generates the following sequences of edges for a quadrilateral (n=4):

i (trailing) j (leading)

0 1

1 2

2 3

3 0

i (trailing)	j (leading)
0	1
1	2
2	3
3	0

Here we can see explicitly that, in terms of the relationship between i and j, most of the cases are the same, and the only special case is the last one.

There is an interesting property of looping algorithms, however, which is that the first iteration through the loop can easily be special. By doing any updating after the body of the loop, the preparation for later iterations is done in this ending section, and the preparation for the first iteration is done before the body of the loop.

Therefore we instead enumerate the edge vertex pairs in an order amenable to this technique:

i (trailing) j (leading)

3 0

0 1

1 2

2 3

i (trailing)	j (leading)
3	0
0	1
1	2
2	3

Now the code can be made efficient and fairly simple:

int i,j;
i=n-1;
for (j=0; j < n; ++j) {
   ... edge is <i,j> ... 
   i=j;
}

This can be simplified further in languages like C which allow multiple expressions inside the for statement, and which provide a post-increment operation:

int i,j;
for (i=n-1,j=0; j < n; i=j++) {
   ... edge is <i,j> ... 
}

Finally, in the wild, you may see i still used as the primary loop iterator (going from 0 to 3 as it originally did), and j is changed to trail i instead of leading it, which amounts to reversing the variable names from the loop above:

int i,j;
for (j=n-1,i=0; i < n; j=i++) {
   ... edge is <j,i> ... 
}

Extensions

The algorithm extends immediately to bucket-brigading with more than two indices; for example, code for three indices, with i leading, would be:

int i,j,k;
j = n-1;
k = n-2;
for (i=0; i < n; k=j,j=i++) {
   .. triple is <i,j,k>
}

Additionally, there is a general principle here: if you don't care about the exact phase of an enumeration (i.e. you care about the order but not which comes first), and you have a single exceptional case to deal with, put the exceptional case first. (Note that the bucket-brigade approach above does not fit within that general principle, so there's still more to it than just that.)