How do I determine if a polyhedron is convex?

Question

I'm looking for an efficient algorithm that determines if a polyhedron is convex.

I started by checking that the Euler characteristic is 2. And I'm also checking that every face is convex. But that still doesn't catch a lot of cases.

Natoshanatron

Answer 1

I had another idea: For each face check that all the other vertices lie on the same side of that face.

You can check this by calculating the normal vector for each face (by cross-product) and then computing the dot-product for each vector from one vertex (of the face) to all the others. The signs must be the same.

The algorithms should both work, but the may differ in compute time.

Shandrashandrydan

Answer 2

Check this out: http://liam.flookes.com/cs/geo/

Basically:

• pick a point within the polyhedron
• send a ray from that point to each face
• ensure that the ray only intersects the chosen face

Featherveined

Great, thanks. Is the average of the vertices always interior to a convex polyhedron? – Natoshanatron

This point cannot be chosen at random and you will have false-positive, right? – Terceira

@ Charles: Yes, it is, given a convex body. @Terceira It can be chosen at random, but you must check the chord between the point P and the face A for intersection with all the planes of the faces. The chord P-A may intersect the plane of face B outside of face B. – Rascality

@Terceira yeah I think you're correct, random choices could give you false positives. – Featherveined

@DasKrümelmonster this does not make sense: you will always intersect more than one plane in any given polyedra. – Terceira

@Terceira With a ray or an (infinite) line yes. But not with a finite length chord (From center P to the center of the face) Or another way to put it: If the intersection between face B and the line it either 1) outside of A or 2) on the other side of the body then it may still be convex. (In a convex body, all the intersections will be like this) – Rascality

This method may fail for a pentagram. For example a pentagram extruded out of its plane and capped at the ends. – Cassel