Interactive Mouth Closing!
This applet uses an algorithm very similar to the O(kn) time algorithm used to cut ears from a simple polygon. The algorithm considers vertices that are concave instead of convex when searching for a mouth. As well, convex vertices are tested to see if they prevent the concave vertex from being a mouth.
1. i = 0
2. mouth not found = true
3. while mouth not found
4. if pi is concave then
5. if triangle formed by pi-1, pi, and pi+1 contains no convex vertex then
6. mouth not found = false
7. if mouth not found then
8. i = i + 1
9. return pi
The instructions are the same as those for the Ear Cutting Applet :
If you wish, you can see the source code. Classes written by Steve Robbins were also used. They are available on his homepage.
This page was last updated on Wednesday, December 10th, 1997.
© 1997 Ian Inc.