Hey, @Xiphware
The work you presented is very interesting.
I have been working on a tool in ODK to generate N random points within a defined shape polygon. Of course, my first version of the tool was built on having only convex shapes and generating a set of random points depending on (the min-max lat-long) of all the points of the shape. This throw points in a square shape area and I use your algorithm to find if the point is inside the polygon.
This works of course but it is not perfect.
As of today, my tool can generate N random points within any convex shape, and if non-convex only up to 1 angle, the generated points will always be inside the polygon. I used the polygon decomposition method, angle detection, calculated haversine distances, and area calculations.
I am now working on the last version (which works with any shape), in which I already found the solution algorithm, but need to find work around the limitation of ODK. Once finished, will be sharing in on the ODK forum 
Happy to discuss more.