   Point Containment Test - Simple Polygon
  Problem:I have an ordered (clockwise) list [1...n] points that define the boundary of a simple polygon. I want to test if a given query point is inside or outside the polygon. The polygon can be non-convex.Can anyone point me towards a solution to this problem that is easy to implement and has good performance?I have a point containment test for a convex polygon implemented (using SAT) and I realize that if I had a good algorithm for busting a simple polygon into a set of convex polygons, then I would be done.I am working on a 2D space combat game and I want to define "nebula" regions where ships move slower. I realize that I could just define the regions as a set of convex polies, but am interested in implementing a more robust solution for a class project.   
  Check the Forum FAQ for a link to an ACM website on point-in-polygon tests.   ;  It's sometimes frowned upon to give complete solutions to problems like this on these forums, but I happen to have a function lying around that does exactly what you're wanting, so I'd feel somewhat remiss in not posting it. Here it is:bool PointInPoly2::PointInPoly(const Vector2& p, const std::vector<Vector2>& v){    bool inside = false;    for (int j = 0, i = v.size()-1; j < v.size(); i = j++) {   if (v.x >= p.x || v[j].x >= p.x) { // At least one endpoint >= px  if (v.y < p.y) { // y1 below ray if (v[j].y >= p.y) { // y2 on or above ray, edge going 'up'if ((p.y-v.y)*(v[j].x-v.x) >= (p.x-v.x)*(v[j].y-v.y)) {    inside = !inside;} }  } else if (v[j].y < p.y) { // y1 on or above ray, y2 below ray, edge going 'down' if ((p.y-v.y)*(v[j].x-v.x) <= (p.x-v.x)*(v[j].y-v.y)) {inside = !inside; }  }   }    }    return inside;}The algorithm is straightforward and is exactly what you'll find if you google for 'point in non-convex poly'; the idea is simply that a ray fired in any direction from a point will cross an even number of edges if the point is outside the poly, and an odd number if inside. The ray direction is chosen to be the positive x axis so as to simpify the computations and avoid certain robustness issues.Let me know if you have any questions or problems with the code.   