Not logged in, Join Here! or Log In Below:  
 
News Articles Search    
 

 Home / 3D Theory & Graphics / Determining if a point is in a convex poly Account Manager
 
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.
 
Kilbert

May 29, 1999, 04:02 AM

Hey, I'm having trouble coming up with a method of finding out if a point is located inside a convex polygon(2d) and a polyhedron(3d). A normal rectangle is easy with just top-left and bottom-right points, but add more points or move them some and it gets hard.

I know how to detect whether or not a point is on one side or on the other side of a plane. I'm currently thinking that if I went through all the planes and tested the point that I want to test with the plane's verts. i could figure it out, or would normals come into play some?

later,
Kilbert

 
Conor Stokes

May 29, 1999, 10:32 AM



Kilbert wrote:
>>Hey, I'm having trouble coming up with a method of finding out if a point is located inside a convex polygon(2d) and a polyhedron(3d). A normal rectangle is easy with just top-left and bottom-right points, but add more points or move them some and it gets hard.
>>
>>I know how to detect whether or not a point is on one side or on the other side of a plane. I'm currently thinking that if I went through all the planes and tested the point that I want to test with the plane's verts. i could figure it out, or would normals come into play some?
>>
>>later,
>>Kilbert

Well last I remember, a plane had infinite coordinate area, and would probably not be best
tested that way. Indeed there is an easier way, involving the normal ABC and guess what?

The scalar D comes into it as well. Here is what you do. You take a dot product between the
point and the normal ABC. And then we test D against that value. Eg if D=Dotproduct, then the
point is on plane. Less than D it is to one side, and greater than D to the other.

Conor Stokes

 
Bryan Moodie

May 29, 1999, 11:44 PM

Hi Kilbert,

As long as all of your plane normals point outwards, then if the point is
on the negative side of all of the planes, then it is inside.
So if the plane equation is Ax+By+Cz+D=0, and p.n + D < 0 for every
plane, then it is inside.
(where p is the point (x,y,z), and n is the plane normal (A,B,C))

For 2d, it is pretty much the same. Find a 'normal' for each line, and
treat it in the same way as for 3d. The 'normal' is either (y0-y1, x1-x0)
or (y1-y0, x0-x1), depending on whether the polygon is clockwise or not.
Then calculate D using D=-p.n
OR
You can test using the dot product between the normal and a vector from the
surface to the point. This is what I have used:

Here is some code from an Edge class. The Edge class has members 'p' and 'q'
for the start and end of the Edge.

bool Edge::vertexInside(Vertex *v){
// vertexInside() returns true if the vertex is on the "inside" / anticlockwise
// side of the edge.

// ( nx, ny ) is a vector perpendicular to PQ (anticlockwise)

Coord nx= -(q->getY() - p->getY());
Coord ny= (q->getX() - p->getX());

// ( dx, dy ) is a vector from a point on the line (P) to the vertex

Coord dx= (v->getX() - p->getX());
Coord dy= (v->getY() - p->getY());

// The sign of the dot product indicates which side the vertex is on

return (dx*nx + dy*ny) > 0;
}

I hope this is of some use to you,
See ya,
Bry

 
Kilbert

May 31, 1999, 12:53 AM

i'll give that a try. i prolly would of came to that, but most programmers are lazy and the books promote code reuse. wonder who thought of that? couldn't of been a corporate guy.

thanks,
Kilbert

 
Steph

May 31, 1999, 03:50 AM


Another way to test if a point is inside a 2d polygon (convex or not) is to count
the intersections between the polygon edges and a horizontal semi-line starting
at the point to test and going to the left or the right of it.
if(intersection_count&1) the point is inside else the point is outside.
And most of the intersection just don't have to be calculated.

Steph




Kilbert wrote:
>>Hey, I'm having trouble coming up with a method of finding out if a point is located inside a convex polygon(2d) and a polyhedron(3d). A normal rectangle is easy with just top-left and bottom-right points, but add more points or move them some and it gets hard.
>>
>>I know how to detect whether or not a point is on one side or on the other side of a plane. I'm currently thinking that if I went through all the planes and tested the point that I want to test with the plane's verts. i could figure it out, or would normals come into play some?
>>
>>later,
>>Kilbert

 
This thread contains 5 messages.
 
 
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.