0

I have an ordered list of 3D points P1, ..., Pn that compose the vertices of a polygon. It is NOT assumed that the polygon is planar.

I need to determine whether a 3D point P is contained in the polygon (either on one of the edges or inside). Is it mathematically correct to proceed as follows?

  • Every sequence of 3 consecutive points Pi-1, Pi, Pi+1 define a planar triangle. I can use, e.g., the method described in Check whether a point is within a 3D Triangle to determine whether the point is in in the triangle.
  • A point P is contained in the polygon if it is contained in one of the triangles composing the polygon.

Corollary questions: If the above method is correct

  • Are there more efficient ways to compute this?
  • Can the above method be used to compute the area of the polygon? In other words, is the area of the polygon equal to the sum of the areas of the composing triangles?
Community
  • 1
Esteban Zimanyi
  • 103
  • Are you talking about polyhedra when saying non-planar 3D-polygon? I'm not sure how a list of 3D-vertices are sufficient to describe the complete shape of a piece-wise linear but non-planar surface in space. – M. Winter Mar 17 '17 at 08:31
  • You should point out how a "non planar polygon" is defined. If your definition is "a point is inside a polygon if it belongs either to its sides or to the triangles formed by three consecutive vertices" then your method is fine. But such a definition would be questionable even in the planar case. – Intelligenti pauca Mar 17 '17 at 08:46
  • I am not talking about polyhedra :-( Imagine x and y are latitude and longitude and z is altitude (as in terrain models). I need to determine whether a point P is in the surface of that 3D polygon or not. If not it is either on the air or below ground. – Esteban Zimanyi Mar 17 '17 at 08:48
  • I think a better definition could be "a point is inside a polygon if it belongs either to its sides or to the triangles formed by two fixed consecutive vertices and a third vertex chosen among the others". The problem is you are going to get different results when starting with two different vertices, if the polygon is not planar. – Intelligenti pauca Mar 17 '17 at 08:52
  • 1
    See also: http://stackoverflow.com/questions/12411209/triangulating-non-planar-polygons – Intelligenti pauca Mar 17 '17 at 08:55

1 Answers1

0

Theoretically, the term "non-planar polygon" itself is confusing since the word "polygon" already implies it is planar. I am going to assume that you actually meant that the polygon does not lie on the x-y plane but in the 3D space.

To check whether a 3D point lies in a planar polygon in the 3D space, the easiest way is to transform all polygon vertices and the 3D point to the coordinate system of the plane where the polygon lies. If the transformed 3D point still have a z value, then it is off the plane and will not be "contained" by the polygon. If the transformed 3D point lies on the plane, then you can check whether it lies within the polygon easily (see answer to this question)

BTW, your proposed method that checks whether the point lies in the triangle formed by 3 consecutive vertices of the polygon will not work when the polygon is non-convex.

Community
  • 1
fang
  • 3,570
  • How to transform the point to the coordinate system of the plane where the polygon lies ? I have used the method described in http://stackoverflow.com/questions/26369618/getting-local-2d-coordinates-of-vertices-of-a-planar-polygon-in-3d-space to transform the polygon but don't know how to transform the point in order to know if it still has a z value – Esteban Zimanyi Mar 19 '17 at 18:34
  • Transforming the point is the same as transforming vertices of the polygon. – fang Mar 19 '17 at 21:43
  • Using the notation in the question mentioned above, the coordinates for the vertices are transformed in 2D as follows

    local_coords = [(dot(p - loc0, locx), dot(p - loc0, locy)) for p in points]

    How I can obtain the Z coordinate for the point P to transform using the formula above ?

     – Esteban Zimanyi Mar 19 '17 at 21:51
  • The Z coordinate after transform can be computed as dot(p-loc0, normal) where normal is the unit normal vector of the plane. – fang Mar 22 '17 at 05:39