CODEWITHSUNDEEP
c#convexpolyhedra
Charles Taylor
Charles Taylor

Reputation: 696

How do I determine if a polyhedron is convex?

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.

Upvotes: 5

Views: 2076

Answers (2)

DasKrümelmonster
DasKrümelmonster

Reputation: 6060

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.

Upvotes: 4

Buddy
Buddy

Reputation: 11038

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

Upvotes: 5

Related Questions