PDA

View Full Version : point lies withn polygon


yellowFattyBean
11-18-2010, 10:00 AM
Hi

I need some help detecting if a point lies inside the boundary of a polygon. I have written a plugin to show if a point lies on a plane, but i need to make it so it will only be displayed if the point is within the surrounding vectors.

Is there perhaps something in the API which I can use to detect this. If not does anyone have a clue gow to tackle this mathematically.

r4inm4ker
11-19-2010, 12:30 AM
fire a ray from that point in arbitrary direction to check the number of intersection between the point and each edge of the polygon. If it's odd, then the point must be inside. otherwise it's outside.

That's how to do it, if i remember correctly.

schizofrantic
11-19-2010, 12:49 AM
You need to check if it's on the actual lines.


proc float distancePointToLine(float $p[], float $origin[], float $end[])
{
float $distance = 0;

vector $v = <<$end[0]-$origin[0], $end[1]-$origin[1], $end[2]-$origin[2]>>;

$v = `unit $v`;

vector $v2 = <<$p[0]-$origin[0], $p[1]-$origin[1], $p[2]-$origin[2]>>;

float $dot = `dot $v2 $v`;

if($dot==0)
return 0.0;

if($dot <0)
return getDistance($p, $origin);

return sqrt((`dot $v2 $v2` - ($dot * $dot))/(`dot $v $v`));
}


comes from my utility library I put online the other day. It has about any computational geometry problem you could want solved and a maya plugin to do a bunch of stuff. Most of it is C++ and requires installing plugin but it's open source so you can rifle through the code and figure out how to do various stuff.

http://nutils.sourceforge.net/

3Dmonkey
11-19-2010, 07:46 PM
Wow. Thanks for giving this away.
It all looks very helpful, especially with the plug-in source code included.

schizofrantic
11-19-2010, 09:59 PM
Wow. Thanks for giving this away.
It all looks very helpful, especially with the plug-in source code included.

I hope people get some good use out of it. If you find bugs or need help let me know, either here or on the project page.

yellowFattyBean
11-20-2010, 01:14 AM
Nice one guys, Thanks for your help.

I have just one more question.

When calculating the line-line intersection, how would I show an intersection between 2 specific points? If the line is infinite, then would it not intersect with all edges of the polygon at some point?

schizofrantic
11-20-2010, 03:39 AM
Nice one guys, Thanks for your help.

I have just one more question.

When calculating the line-line intersection, how would I show an intersection between 2 specific points? If the line is infinite, then would it not intersect with all edges of the polygon at some point?

I'm not sure what you mean exactly.

If you mean intersect line segment instead of line it is also in the code if you download it.

Reading back I think I misunderstood you, though.

To check if a point is on the polygon first you do a distances point to plane. Then you do a comparison of each line segment to see what side the point is on. As soon as you get a result that's not on the same side as the others you know it's not part of the polygon. If they all are on the same side you are ok.

The whole process is a little to convoluted to explain in a forum post but all of these are in the code but some of it only in the C++ code source so you would have to look through that a bit (in the ngeometry.h file).

uiron
11-22-2010, 06:43 AM
if you want to check if point P is on a triangle ABC, you could just just check if barycentric coordinates of that point sum up to 1.0:
area(ABC) = area(PAB)+area(PBC)+area (PAC)

basically that's 4 cross products for each triangle - area(ABC) = cross (AB,AC)/2

this also will work trying to do checks like "is it *almost* on that face?", you just need compare if results on both sides of the equation are equal enough.

so just loop that for every triangle on the face and you're set.

zoharl
11-24-2010, 09:22 PM
Orient the vector edges of the polygon to be ccw for example. Then test that your point is to the left of each vector (implies that it must be inside the poly). Do the test using cross product (check the sign of the signed area of the formed triangle) - look up in wiki.

uiron
11-25-2010, 06:44 AM
Orient the vector edges of the polygon to be ccw for example. Then test that your point is to the left of each vector (implies that it must be inside the poly). Do the test using cross product (check the sign of the signed area of the formed triangle) - look up in wiki.

would work in 2d math, but in 3D, this test results in testing if point exists in a tube, bounded by 4 planes.

zoharl
11-27-2010, 07:45 AM
Sorry, then I didn't understand the question. He didn't say polyhedra, he said polygon, and he said he knows how to detect if it's on a plane, which converts the problem to 2D. How would you define a point inside a polygon in 3D, anyway?

CGTalk Moderation
11-27-2010, 07:45 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.