Orkin Man 122 Report post Posted January 25, 2001 I need I couple of algorithms for the project I''m working on. 1. I need an algorithm that will tell me weither or not a polygon (not a triangle, a polygon) lies within, weither partially or totally, an area defined by a list of planes. 2. I need an algorithm that will tell me weither or not any part of a polygon is within a specified distance of a point. Thanks in advance for any help! 0 Share this post Link to post Share on other sites

Toom 122 Report post Posted January 25, 2001 The first problem is exactly what frustum culling is all about, so perhaps my little article on the topic may be of some use.Basically you need to calculate the distance of each point from each plane. The sign tells you which side of the plane it's on.Given the four numbers that define a plane (A, B, C, and D) you can calculate the distance of a point P from that plane like this: distance = A * Px + B * Py + C * Pz + D So by testing all of the points in your polygon against all the plane equations you should be able to determine if it's entirely within or partially within.The second problem is easier I think. Here's some pseudo code (untested, making it up as I go along here):Calculate the distance if the point from the plane of the polygonIf it's within your range then return TRUEFor each vertex that defines the polygon: Calculate the distance of the vertex from the point If it's within your range then return TRUEReturn FALSE The distance between the point and a vertex is calculated like this: distance = sqrt( (Vx - Px)^2 + (Vy - Py)^2 + (Vz - Pz)^2 ) However sqrt() is slow, so leave it out and compare the result to RANGE^2 instead of RANGE. Should have the same result.ToomEdited by - toom on January 25, 2001 1:47:34 PM 0 Share this post Link to post Share on other sites

Osku 122 Report post Posted January 26, 2001 Toom : I''m not sure if your second answer is accurate. The point can be an arbitrary distance away from the polygon even if it is near the plane of the polygon, and the point could be even within the polygon even if it isn''t near a vertex. I not sure how to calculate this but I don''t think your answer was the right one.Regards, Osku 0 Share this post Link to post Share on other sites

Toom 122 Report post Posted January 26, 2001 Doh. You are correct of course.Perhaps something like this:Calculate the distance of the point from the plane of the polygonIf it''s outside your range return FALSECalculate the position on the plane that is perpendicular to the pointIf this new point is within the polygon return TRUEFor each vertex that defines the polygon: Calculate the distance^2 of the point from the vertex If it''s within your range^2 return TRUEReturn FALSE Toom 0 Share this post Link to post Share on other sites