Geometric Meaning behind the algorithm (slope of the line + ray casting)

Question

I'm trying to dissect the classic algorithm for finding if a point is inside a (simple) polygon.

Please see:

http://erich.realtimerendering.com/ptinpoly/

and

https://stackoverflow.com/questions/11716268/point-in-polygon-algorithm

I got the algorithm to work and got to know where the left hand side of the comparison came from. I also understood why the need of having the Y coordinates to show different signs.

That is, that:

(verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )

But I still can't add a geometric meaning to it. After toying with the equation I realized that the "ray casting" logic test came from the following inequation:

verty[j] - vert[i] / vertx[j] - verty[i] < testy - verty[i] / testx - vertx[i]

where the authors solved for testx (where testx is the point to be tested if it is contained inside the polygon).

from the last equation if see that it is the coefficient m from the slope line equation being compared in both sides. but why test both equations to see if one is less than the other?

Besides that when we solve for testx where is the "ray casting" occuring? and why at just one side of the inequation?

Answer 1

What's happening is a ray is being cast to the right (in the positive $x$ direction) and we're counting edge crossings. The first condition is a bit of a cryptic way to say "if the $y$-coordinate of starting and ending points are both above or below the test $y$-coordinate then we definitely don't cross an edge". The next condition is calculating the $x$-coordinate of the intersection of the horizontal line going through testy and the edge, i.e. the line joining the start and end vertices. It then checks if testx is less than that $x$-coordinate. If so, that means we're going to cross an edge going from left to right.