1
$\begingroup$

I have a 3D polygon based on a set of faces. Each face lies in a single plane, and I know the normal for each face (as well as the points that create the face). I also know that each normal points "outward".

I need to figure out which faces contribute to the polygon being concave (if any).

For some reason I'm having a hard time conceiving this...

I first thought I might be able to simply check the dot-product of each neighbouring normal, and simply see which ones are < 0. But I guess this method would fail because the dot product between normals doesn't share information about whether two faces "face" eachother or not. In fact, I think I could even think of cases where the dot product of the normals is not consistent (i.e. some dot products >0 and some <0), and the polygon would still be convex.

For the 2D case I guess I could traverse the polygon in the order it was defined and just check the angles from one face to the next. In this case, the edges that contribute to the polygon being concave would be the faces that create an angle of larger than 180 degrees with their previous face.

I'm not even sure if this would even work in a 3D case.

Any pointers?

  • 0
    Your polygon will be convex iff the sum of the face angles at each vertex does not exceed $2\pi$ (the difference between $2\pi$ and this sum is a discrete version of Gaussian curvature).2011-04-13

2 Answers 2

2

I'll also use the word polytope. I interpreted the question as: how can I test whether the given polytope is convex?

A convex polytope is the intersection of half-spaces which are given by the planes containing its faces. You know the normal vectors to these planes and a point in each plane, so you can find their equations. Then you can apply the following test: for each plane, do all the vertices of the polytope lie on the same side of the plane? If so, the polytope is convex, and if not then I guess it is not.

  • 0
    Good point, I like it and it makes sense. I'll consider this question answered then. Thanks to all who replied!2011-04-13
2

If I understand correctly, you're working with polyhedra. As far as I know, it's unusual to call these "3D polygons"; the general term is neither "polygon", nor "polyhedron", but "polytope", so a polyhedron is a 3D polytope.

You first need to define what you mean by "which faces contribute to the polyhedron being concave". One possible interpretation, which Alex adopted in the comment, is that you're looking for the faces that aren't part of the convex hull. Another interpretation is that you're looking for the faces that have an edge at which the polyhedron is not convex; that would be a subset of the faces in the first interpretation.

Under the first interpretation, as Alex wrote, you can compute the convex hull, and all faces not on the convex hull will be the ones you're looking for.

Under the second interpretation, for each pair of adjacent faces, you can take any point that's on the one face but not on the other, and check which side of the other face it's on (by taking the dot product of the normal of the other face with the difference between the point and any point on the other face).

  • 0
    Apologies for my bad terminology and definitions. I was actually looking for the faces in the interpretation defined by Alex. It's hard for me to explain why exactly, because this mathematical problem is only a small part of a larger project I'm trying to implement. But I really appreciate your help, so I'm giving you an upvote, cause your described method might actually come in handy later on. Thanks!2011-04-13