Sorry, I know this is an idiot math question that I should know off of the top of my head: Calculating if a point is inside a polygon. Is there a nice fast way of doing this? I can obviously compare line by line of the polygon determing which side the point lies on but something tells me there is a better algorithm that I''m too dumb to remember at the current moment. Thanks, Sieggy

That is a pretty good idea, assuming the polygon is convex of course.

If you first convert the polygon to 2D it will be much faster though. The conversion is simply done like this

if( fabs(Normal.x) > fabs(Normal.y) && fabs(Normal.x) > fabs(Normal.z) ){  // Since the normal of the polygon is most aligned with  // the x-axis, the polygon's plane is most aligned with  // the y/z plane. So in further computations we simply   // ignore the x-component of all vectors} 

Now the edge normals can be easily computed by rotating the edge 90 degrees (xrot = -y, yrot = x).

You may get it even faster by computing the signed area of all triangles that you get if you draw an edge from the point of test to all vertices in the polygon. If any of the triangles' areas have opposite sign of the others the point is outside the polygon.

The signed area in 2D is computed like this:

Area = (x1*y2 - y1*x2)/2

where (x1,y1) and (x2,y2) are two of the edges in the triangle.

I hope I didn't get too technical with you. Please ask again if you have any trouble understanding what I just said.

- WitchLord

Edited by - WitchLord on 5/5/00 1:37:04 PM

Thanks but still a bit confused. I don''t quite follow your conversion of the triangle from 3d to 2d or the piece of code included. The normal is the direction the triangle is facing, correct? How can it be more aligned with a particular plane? Couldn''t it be theoretically more aligned with any plane depending on what direction the triangle was facing?

I also didn''t quite follow the 2d check either. I understand that you are creating a virtual triange between the point being tested and all the vertices in the triangle to be checked. However, what exactly are x1, x2, y1, y2? Points or line lengths in these two virtual triangles (since a single point and testing on a singe triangle would create 2 triangles if I understand this correctly)?

I''m actually interesting in the 2d portion (as this particular test is using already transformed vertices) but if you can expend more on both aspects as I''m trying to improve my math as much as possible.

Thanks again Witch Lord,

Sieggy

There''s some code I have at home that determines this, in convex polygons. Basically, you test to see what side of each line the point lies on.

PCMCIA - People Can't Memorize Computer Industry Acronyms
ISDN - It Still Does Nothing
APPLE - Arrogance Produces Profit-Losing Entity
SCSI - System Can't See It
DOS - Defunct Operating System
BASIC - Bill's Attempt to Seize Industry Control
IBM - I Blame Microsoft
DEC - Do Expect Cuts
CD-ROM - Consumer Device, Rendered Obsolete in Months
OS/2 - Obsolete Soon, Too.
WWW - World Wide Wait
MACINTOSH - Most Applications Crash; If Not, The Operating System Hangs

That''s easy enough, however I was intrigued by what WitchLord was pointing towards. Hopefully he''ll explain a little more on what he was thinking in his post.

Thanks, though. I appreciate it. :-)

Sieggy

Hello, I'm glad you were intrigued. I'm sorry I was too brief to be understandable.

I'll start with the 3D to 2D conversion. The normal is the direction that the polygon is facing yes. What the conversion does is that it checks which of the three axes (x, y and z) that the normal is more aligned to. In other words which axis the normal has the smallest difference with. (Damn, this was hard to explain ) Ok, here's an example: Let's say the polygons normal is (0.1, 0.4, 0.91) in this case the normal is more aligned to the z-axis than either y or x since the z component is the largest. Because the normal is almost parallel with the z-axis, the polygon must be almost parallel to the x/y-plane which is perpendicular to the z-axis.

The reason why I make this test is that I want to conserve as much of the polygons area as possible in order to keep as high acurracy as possible. In the example above I can now throw away the z-component of the point to be tested and the vertices of the polygon, this is the same as parallel projecting the coordinates onto the x/y plane. You of course need to make this test for any polygon that you are testing, but since it only requires two compares to determine the largest component of the normal it is a fairly fast test.

Now for the 2D test. Let's say you have your polygon converted into 2D and described with 4 vertices (V0,V1,V2,V3). The point we wish to determine if it is inside or outside is named P.

We can now for each edge in the polygon create a triangle

T0 = P,V0,V1
T1 = P,V1,V2
T2 = P,V2,V3
T3 = P,V3,V0

Now compute the edges that contain the point P

E0 = V0 - P
E1 = V1 - P
E2 = V2 - P
E3 = V3 - P

The signed area for a 2D dimensional triangle is computed as:

Area = (U.x * V.y - U.y * V.x)/2;

Where U and V are two of the triangles edges. Depending of the vectors position relative each other the sign of the area will be either negative or positive.

(This is actually derived from the formula for the crossproduct which is LengthOf(CrossProduct(U,V)) = LengthOf(U)*LengthOf(V)*sin(SmallestAngleBetween(U,V)) )

Compute the signed area for all the triangles:

Area0 = (E0.x*E1.y - E0.y*E1.x)/2;
Area1 = (E1.x*E2.y - E1.y*E2.x)/2;
Area2 = (E2.x*E3.y - E2.y*E3.x)/2;
Area3 = (E3.x*E0.y - E3.y*E0.x)/2;

Now because the sign is depending on the order of the vectors we know that if any of the areas have different sign than the others the point must be on the outside of the polygon.

SumSign = Sign(Area0) + Sign(Area1) + Sign(Area2) + Sign(Area3);

if( SumSign == 0 // SumSign == 4 )
{
// All signs are the same, the point is inside the polygon
}

Sign(a) is a function that returns one if the sign of a is negative and zero if it is positive.

I hope I was more clear this time.

You may get something more out of reading this thread: fast ray/triangle intersection test.


- WitchLord



Edited by - WitchLord on 5/5/00 4:53:51 PM

Thanks WitchLord!

Thanks for the explanation, it makes more sense to me now. I''m going to play with it some tonight. I guess that''s another one that I owe ya!

Sieggy

One of these days I''m going to collect all the debts.

- WitchLord