Geek Answers Handbook

How to determine if a polyhedron is released?

I am looking for an efficient algorithm that determines if a polyhedron is released.

I started by checking that Euler's characteristic is 2. And I also check that every face is convex. But this still does not catch many cases.

+5
source share
2 answers

I had a different idea: for each face, check that all the other vertices lie on one side of this face.

You can verify this by calculating the normal vector for each face (from the cross product), and then calculating the point product for each vector from one vertex (face) to all the others. Signs must be the same.

Algorithms should work, but they may differ during the calculation.

+4
source

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

Basically:

  • select a point inside the polyhedron
  • send a ray from this point to each face.
  • make sure the beam only crosses the selected face
+5
source

More articles:


All Articles