Recently my team needed to find out if a point was inside a given polygon and, as usual, we found some code on the internet that did what we wanted. And, as usual, there wasn't much explanation as to what it was doing. Here's the code (after we converted it to Ruby): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def contains_point? (point) c = false i = -1 j = self .size - 1 while (i += 1 ) < self .size if (( self [i].y <= point.y && point.y < self [j].y) || ( self [j].y <= point.y && point.y < self [i].y)) if (point.x < ( self [j].x - self [i].x) * (point.y - self [i].y) / ( self [j].y - self [i].y) + self [i].x) c = !c end end j = i end return c end end So, you know, it works and I'm grateful to somebody for posting it but we had no idea how it works. So we wrapped 2 tests around it (one where the point is not in the polygon and another where it is...
Comments