A DECOMPOSITION ALGORITHM FOR ARBITRARY POLYGONS USING MONOTONE CHAIN

This paper presents a new decompsition algorithm for an arbitrary polygon. The concept of monotone chain in computational geometry is extended at first and used to decompose the inner and outer loops of an arbitrary polygon. Second, the nonregular vertices are sorted.At last,the decomposition between monotone chains finish the whole arbitrary polygon decompsition process. The algorithm's time complexity is O(NlogN).This alogrithm is used to shade solids models using GL on a SGI Indigo workstation.