Tag Archives: winding rules

Fill Rules

Fill Rules in TikZ

Filling shapes (or any path for that matter) in TikZ can be done with the \fill command. This requires very little thought on our part when it comes to filling simple shapes, e.g. circles or squares but it gets a little more complicated once we draw shapes with intersecting paths or holes. This is a difficult problem because we don't always know where the "inside" of a shape lies--this is not as simple as it sounds. To do this, we must understand the types of polygons there are as well as the rules for filling them with color.

Types of Polygons

We can divide polygons into two types: standard polygons and general polygons. Standard polygons are include circles, squares and triangles. These shapes have no holes and their paths don't self-intersect unlike general polygons.

Filling Shapes
The circle, square and triangle are basic polygons. Their paths do not intersect and the shape does not have a hole unlike the general polygon below.

Filling Shapes

There are two rules we can use to fill fhapes in TikZ:

  • Even-Odd Parity Rule
  • Non-zero Winding Rule

Both rules are algorithms that are used to determine whether a given point falls within an enclosed curve. To determine the "insideness" of a point, we draw a ray from the point we wish to determine to infinity in any direction. With the even-odd rule, we count the number of times the ray crosses a path segment. If the number is odd then the point lies on the inside of shape. If it is even then it lies on the outside.

Unlike the even-odd rule, the non-zero winding rule relies on knowing the stroke direction for each part the ray crosses. The number of intersections is scored and given a winding number. If the path is clockwise, or runs left to right, we subtract 1 from the score. If the path is counter-clockwise, or runs from right to left, we add one to the score. If the total winding number is zero then our point lies on the outside but if the winding number is not zero then the point lies on the inside. We will see how both rules differ and why.

Even-Odd Parity Rule

Fill Rules
We construct rays, both inside and outside, going through our shape of interest to determine if a point lies on the inside or ourside.

For a standard polygon, the shapes shown on top, it is easy to see where the outside lies but let's construct a few rays (shown in black) that lie outside and see what we get. For the circle, square, and triangle, the ray crosses the shape's path twice. This sum is even and we can conclude that the point lies on the outside of those shapes.

Now we construct some rays (shown in red) that lie on the inside. We see that they all cross the shape's path once. This makes the sum of path crossings odd and we conclude that the point lies on the inside of the shape.

But what happens with the general polygon below? We see that the black ray crosses the general polygon's path four times--an odd sum. This point lies on the outside of the shape. When we look at the red ray we see it crosses the shape's path once and we conclude that point lies on the inside.

Now let's look at the blue ray as it goes out from the hole. There is some doubt whether that point lies on the inside or outside of this shape but we can apply the even-odd rule. We see that the blue ray crosses the shape's path two times, an even number of times, which means the point lies on the outside of the shape and we don't color this area.

Fill Rules
Filling shapes with the Even-Odd Parity Rule

So we see how we can implement the even-odd rule in TikZ and how it works. But how exactly does the Non-Zero Winding Rule differ and will the results be the same? As you have probably guessed, the answer is no. After all, why have two different rules that do the exact same thing?

Non-Zero Winding Rule

Fill Rules
With the non-zero winding rule we need to consider the direction the path goes.

The non-zero winding rule is different from the even-odd rule in that we must consider the direction the path takes as the ray crosses it. We draw the direction of the winding path so we can determine whether a point lies on the inside or outside of a shape.

Fill Rules
We use our rays to determine whether a point lies on the inside or outside of a shape.

We do the same thing with the Even-Odd Parity Rule with one exception--if the path runs counter-clockwise as we cross it, we add one and subtract one if it runs clockwise.

For the circle, the first path crossing runs from left-to-right so we subtract one. As we continue our ray, the next crossing runs from right-to-left and we add one. The sum of our path crossings is zero and we conclude, like in the case of the even-odd rule, the point lies on the outside.

We see that for the circle, square, and triangle, the results are the same for the even-odd rule. Things are a little different for the general shape seen below. While the red and black rays yield the same result, the blue ray gives us something very different. The first crossing of the blue ray goes from left-to-right, we subtract one. The next crossing also goes from left-to-right, we again subtract one. The sum of our crossings is -2. The point lies on the inside and we fill the "hole" with color.

Fill Rules
We see the different effect of the Non-Zero Winding Rule on general polygons.

Path Matters

Fill Rules
In the case of general polygons, the even-odd parity rule (shown left) gives a different result from the non-zero winding rule (shown right).

We see the even-odd parity rule and the non-zero winding rule give different results for general polygons. This doesn't mean this is always the case. Path direction in the non-zero winding rule is the determining factor for the results we get.

We can create a general polygon with a hole where one shape lies inside the other and where their paths do not intersect. We can use TikZ code to specify the path directions of the innermost and outermost shapes. On the left, the outermost square's path curves around in a clockwise direction but its innermost square curls in a counterclockwise direction. We see with the general polygon on the right, both the inner and outer squares both curl clockwise.

Fill Rules
We can construct a general polygon with non-continuous paths. The difference is that the left inner square's path is counter-clockwise while the one on the right rotates in the clockwise direction.

We know that the even-odd rule will leave the hole unfilled in both cases as we are just counting path crossings but if we were to use the non-zero rule, on both shapes? We see that the outcome depends on path direction. The shape on the left with a counter-clockwise inner square produces the same result as the even-odd rule but the hole is filled when the inner path goes in a clockwise direction.

Fill Rules
The non-zero winding rule can produce different results for the same shape. This is due to the path differences of the inner rectangle.

Conclusion

Filling shapes with color doesn't have to be a complex operation if you understand the two fill rules and how they work. Generally, the even-odd parity rule won't fill a hole but whether the non-zero winding rule does depends on the path direction of the hole. Once we understand that, drawing and coloring shapes in TikZ becomes very easy.