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.
Function FindMouth(P)
1. i = 0
2. mouth not found = true
3. while mouth not found
4. if
p_{i} is concave then
5. if triangle formed by
p_{i-1}, p_{i}, and
p_{i+1}
contains no convex vertex then
6. mouth not found =
false
7. if mouth not found then
8. i = i + 1
9. return p_{i}
End FindMouth
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 10^{th}, 1997.
© 1997 Ian Inc.