How to check if a point (x,y) is inside a polygon in the Cartesian coordinate system?

This question already has an answer here: Point in Polygon aka hit test C# Point in polygon

Given a random polygon formulated with N line equations in the Cartesian coordinate system, is there any standard formula that is used to check for membership of a point (x,y)?

The simple solution is to get all the line formulas and check if point X is below this line, above that line and to the right of the other line, etc. But this will probably be tedious.

I should note that the polygon can be of any shape with any number of sides and may concave or convex.

For convenience I have already added these utility functions:

float slope(CGPoint p1, CGPoint p2)
{
    return (p2.y - p1.y) / (p2.x - p1.x);
}

CGPoint pointOnLineWithY(CGPoint p, float m, float y)
{
    float x = (y - p.y)/m + p.x;
    return CGPointMake(x,y);
}

CGPoint pointOnLineWithX(CGPoint p, float m, float x)
{
    float y = m*(x - p.x) + p.y;
    return CGPointMake(x, y);
}

Answers


If you have the vertices, you can compute the sum of the angles made between the test point and each pair of points making up the polygon. If it is 2*pi, then it is an interior point. If it is 0, then it is an exterior point.

Some code:

    typedef struct {
   int h,v;
} Point;

int InsidePolygon(Point *polygon,int n,Point p)
{
   int i;
   double angle=0;
   Point p1,p2;

   for (i=0;i<n;i++) {
      p1.h = polygon[i].h - p.h;
      p1.v = polygon[i].v - p.v;
      p2.h = polygon[(i+1)%n].h - p.h;
      p2.v = polygon[(i+1)%n].v - p.v;
      angle += Angle2D(p1.h,p1.v,p2.h,p2.v);
   }

   if (ABS(angle) < PI)
      return(FALSE);
   else
      return(TRUE);
}

/*
   Return the angle between two vectors on a plane
   The angle is from vector 1 to vector 2, positive anticlockwise
   The result is between -pi -> pi
*/
double Angle2D(double x1, double y1, double x2, double y2)
{
   double dtheta,theta1,theta2;

   theta1 = atan2(y1,x1);
   theta2 = atan2(y2,x2);
   dtheta = theta2 - theta1;
   while (dtheta > PI)
      dtheta -= TWOPI;
   while (dtheta < -PI)
      dtheta += TWOPI;

   return(dtheta);
}

Source: http://paulbourke.net/geometry/insidepoly/

Other places you can take a look at: http://alienryderflex.com/polygon/

http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

http://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem


Need Your Help

Rails - Could not find a JavaScript runtime?

javascript ruby-on-rails ruby-on-rails-3 node.js ruby-on-rails-3.1

I created a new Rails project using rails 3.1.0.rc4 on my local machine but when I try to start the server I get:

How to prevent downloading images and video files from my website?

html image video blocking

How to prevent downloading images and video files from my website? Is it possible?