Skip to main content
gamedev.net
🔒 Locked

Point inside Polygon problem

Started by Antonym May 27, 2009 at 2:33 PM 4 replies 2.8k views
Original Post
Antonym
Antonym
I want to know if a given point is inside a polygon. That I am able to do, my problem is that I need the point to be counted even if it's slightly outside the polygon(On the edge or something like that). The method I use to find out of the point is inside the polygon is the following. Take the point and test it against each of the polgyon's edges. If the sum of the angles is 2pi then the point is outside. By calculating the normal of each edge I am able to drag the point a little bit inward and fix my problem, however, if the polygon is too small and/or too thin then the point will cross the polygon entirely :S. Edit: Nevermind problem solved, figured out that instead of moving the point I could move the edge, silly me. 

bool PlayState::InsidePolygon(b2Vec2 *polygon, int n, b2Vec2 p)
{
   int i;
   double angle=0;
   b2Vec2 p1,p2;

   for(i=0;i<n;i++){
	   b2Vec2 edge = polygon[(i+1)%n] - polygon;
	   b2Vec2 normal = b2Cross(edge, 1.0f);
	   normal.Normalize();
	   normal.x *= .2;
	   normal.y *= .2;

	   b2Vec2 newPoint = p - normal;

	   p1.x = polygon.x - newPoint.x;
	   p1.y = polygon.y - newPoint.y;
	   p2.x = polygon[(i+1)%n].x - newPoint.x;
	   p2.y = polygon[(i+1)%n].y - newPoint.y;
	   angle += Angle2D(p1.x,p1.y,p2.x,p2.y);
   }

   if (abs(angle) < b2_pi)
      return false;
   else
      return true;
}

double PlayState::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 > b2_pi)
      dtheta -= b2_pi*2;
   while (dtheta < -b2_pi)
      dtheta += b2_pi*2;

   return(dtheta);
}
[Edited by - Antonym on May 27, 2009 4:35:26 PM]
Atrix256
Atrix256
A point has no size so either it's inside or outside or on a line.

Unless you are using integer math you should almost never have a point be on a line (:

What are you needing to know this test for?

BTW another way to test if a point is inside a polygon is to shoot a ray in any direction and count how many lines of the polygons it intersects. if it's odd, you know the point is inside the polygon.

That might be a simpler / more reliable test, im not sure if your test works for concave shapes (my apologies if it does!)
Zakwayda
Zakwayda
A bit of advice: Don't use the sum-of-angles test for point-polygon inclusion! :) There are other ways to perform the test that are more robust, and far more efficient.

Also, just to be clear, will the polygons always be convex? (I'm assuming so because of the test you're using, but it might be useful to clarify this, just in case.)
grhodes_at_work
grhodes_at_work
jyk speaks wisely. The angle summation approach is the worst performer by a potentially large margin! Please see the following page for a good overview of several strategies:

Point in Polygon Strategies by Eric Haines

With a convex polygon, you can potentially find a more highly optimized approach. Michael Abrash's talk on rasterization with Larrabee last March at GDC (paper available online) has a good overview of this, though it's embedded in a bunch of other stuff and is focused on triangles rather than more general convex polygons, so might be tricky to extract specifically the point in polygon stuff.

Also, you may wish to go read Christer Ericson's presentation on robust geometry over at:

Numerical Robustness (for Geometric Computations)

(His real-time collision detection book also has a good discussion of this.)
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net
Antonym
Antonym
It does work with concave polygons. Thanks I'll take a look.
Antonym
Antonym
This has to work with cocave polygons too.

The reason I am doing this is because I am tracing an image and creating a polygon based on it. I am then going through the image's pixels and testing which ones are inside the polygon, whichever aren't are alphaed out. As it is this algorithm will leave the edges out reducing the geometry each time I want to repeat the process.

I replaced the angle summation algorithm for a crossing one. The solution that worked with the angle summation one doesn't work with this one(offseting the edges) I presume this is because by only offseting the edges gaps are left in the geometry? How could I fix this problem?

Thanks

Edit: Nevermind problem fixed by offseting all edges prior to use. 

bool PlayState::InsidePolygon(b2Vec2 *polygon, int n, b2Vec2 p){	int counter = 0;	int i;	double xinters;	b2Vec2 p1,p2,edge;		p1 = polygon[0];	for (i = 1; i <= n; i++) {		p2 = polygon[i % n];					if (p.y > std::min(p1.y,p2.y)) {			if (p.y <= std::max(p1.y,p2.y)) {				if (p.x <= std::max(p1.x,p2.x)) {					if (p1.y != p2.y) {						xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;						if (p1.x == p2.x || p.x <= xinters)							counter++;					}				}			}		}				p1 = p2;	}  if (counter % 2 == 0)    return(false);  else    return(true);}


[Edited by - Antonym on May 29, 2009 10:45:33 PM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.