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