# Find out which faces of a 3D polygon cause it to be concave

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?

-
For a polygon $P$, you could use a convex hull algorithm to get the convex hull $C(P)$, then $P - C(P)$ would be the set of points you are looking for. – Alex Becker Apr 13 '11 at 8:27
Wow that's actually a really good suggestion. Just one thought: Wouldn't this be very time complex? – Tovi7 Apr 13 '11 at 8:33
For the 2-d case the complexity is $n\text{log}n$ for optimal algorithms. I don't know about higher dimensions though. – Alex Becker Apr 13 '11 at 8:41
@Alex, the same complexity applies for 3d. – lhf Apr 13 '11 at 9:46
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). – yasmar Apr 13 '11 at 15:43

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.

-
That would be a really good way, yes. I'm giving you an upvote for that, but also temporarily leaving this question open cause this seems like a really heavy operation. It involves me checking every point for every half-plane. I was hoping I could use some sort of advantages by utilizing the knowledge of which faces are adjacent to eachother, as well as their precalculated normals somehow, so that for each plane I would only have to check the neighbouring planes. For this reason, I'm leaving the question open temporarily. – Tovi7 Apr 13 '11 at 10:35
@Tovi7, @mac: There's no need to check every point against every plane. I forgot to put "adjacent" in my answer, but that's what I meant (I've added it now). Checking one point against one face for each pair of adjacent faces is enough. If that doesn't detect any concavity, then the polyhedron is convex; it can't be non-convex globally without being non-convex locally at some edge. – joriki Apr 13 '11 at 11:03
Good point, I like it and it makes sense. I'll consider this question answered then. Thanks to all who replied! – Tovi7 Apr 13 '11 at 11:09

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).

-
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! – Tovi7 Apr 13 '11 at 10:31