Telling whether a point is in a simple polygon in O(n) time

This algorithm combines two other algorithms that have been developed to make a very fast way to tell whether a point is inside a simple polygon, even one with holes!

First you have your polygon:

There's been developed an algorithm to triangulate this region in Linear time, here... http://link.springer.com/article/10.1007%2FBF02574703

There are several ways this can be done, I'm not sure exactly which it would come up for for this polygon...

Now one simply checks whether the point in question is in any triangle of the triangulation which can be done like here in constant time:
http://www.blackpawn.com/texts/pointinpoly/

So overall the algorithm is n-2 constant time steps for checking whether the point is inside any of the triangles and linear time for the algorithm, which gives O(n) time.

I'm not completely familiar with the triangulation algorithm, but maybe there could even be optimizations for starting the triangulation somewhere near the point in question and of course you can stop once you've found a triangle it's inside of...