Algorithm for decomposing simple polygon into convex parts
Xiang Gao · Journal of Yanshan University · 2004
In this paper , through analyzing the structure characteristic of the convex polygon which produced by decomposing, we review the properties of the decomposing line, find that there is a internal relation between the two endpoints of the decomposing line, one of the two endpoints is a concave point of the simple polygon, and another endpoint is in the continue sequences of the point which is visual to the concave point, so we defined the concepts Visual Link (VL) and Visual Degree (VD) in order to describe the internal relation. Based on this, a simple and effective decomposing algorithm using the structure characteristic of decomposing line is presented, and the algorithm avoid combined phenomenon which has been produced by other algorithms. Many instance indicate that, the algorithm runs very efficiently and makes fewer numbers and better aspect ratio of the resulting convex polygon, so it fits to use in practice.