I am currently trying to implement a 3D convex hull algorithm that is based on the paper Convex Hulls of Finite Sets of Points in Two and Three Dimensions by F.P. Preparata and S.J. Hong, but I’ve run into some trouble understanding the “gift wrapping principle”.
So on page 91 of the paper (pg 5 of the pdf, last paragraph of 1st column) there is this passage:
The gift wrapping principle works as follows: Let C be a polyhedron with n vertices. Assuming a face f of C is given, select an edge of f. This edge and every vertex of C determine a plane; a new face of C belongs to the plane forming with f the largest convex angle.
Now this passage doesn’t make much sense to me and I was hoping someone out there could help me understand it. First, I always thought that in order to determine a plane you need two points in the plane and a normal vector with that plane. I’m assuming the two points in the plane come from the edge but how can any vertex be normal to a plane containing the points. Maybe I’m just not visualizing this correctly, but it doesn’t seem like that would work. Also the last sentence about a convex angle doesn’t really make sense either as of right now.
Any help with this would be appreciated
Best Answer
Comment was too short.
Plane is uniquely determined by three non-collinear points. Imagine a door, it behaves like a plane determined by two points (the hinges), however, if you add yet another point (e.g. hold it by hand), then the door cannot move (unless you hold it exactly at the rotation axis). The edge from the quoted passage is like the door rotation axis (the hinges are the two vertices that the edge connects), now you need a third point (one of $C$ obviously), and one such that all others are on one side of the door. Naturally, the solution is to open the door as wide as you need (i.e. use the largest convex angle).
I hope this helps $\ddot\smile$