• ### Announcements

#### Archived

This topic is now archived and is closed to further replies.

# Need a couple algorithms...

## Recommended Posts

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!

##### Share on other sites
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.

Toom

Edited by - toom on January 25, 2001 1:47:34 PM

##### Share on other sites
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

##### Share on other sites
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

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627638
• Total Posts
2978330

• 10
• 12
• 22
• 13
• 34