Skip to content

Instantly share code, notes, and snippets.

@pwolfert
Last active August 29, 2015 14:10
Show Gist options
  • Save pwolfert/134d6dda882309bf2c5f to your computer and use it in GitHub Desktop.
Save pwolfert/134d6dda882309bf2c5f to your computer and use it in GitHub Desktop.
Winding Number Rule

The Winding Number Rule

This is a really interesting algorithm that I came across while looking through the java.awt.geom.GeneralPath source code. It's used primarily to determine whether a given point is inside the shape bounded by a curve, and it's known as the winding number rule. I think the term winding rule normally refers to the non-zero winding number rule algorithm, but I'm actually going to discuss the even-odd rule and use that in impementation because it's simpler conceptually.

Basically, a point is inside the curve if its winding number is odd; if it's even, the point lies outside the curve (even if it's completely enveloped by the curve, which is important).

See Wikipedia's article on Winding Numbers. Nice explanation here too

In order to properly test the function that implemented this, I had to understand how it worked. I've included a terrible photo of my whiteboard. It turns out if you shift the shape so that the point in question is the origin, it makes intersection calculations really simple because you can just test for x or y intercepts.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment