A fast concave polygon decomposition algorithm based on point visibility

摘要

As one of the fundamental problems in computational geometry; polygon convex decomposition is used in many fields. Most of the algorithms now available for this subject are for global searching, while the local searching ones are rarely studied. The global searching algorithms waste so much time that they can not meet the needs of all engineering situations. The most classical local searching method is Rogers algorithm, which has been limited in actual usage because of its conspicuous drawbacks. A new local searching algorithm is proposed in this paper based on the polygon point visibility. The local geometrical characters of concave points are fully utilized in the algorithm. The cutting line is extended from concave point to one of the visible points which are carefully searched from the visible point list of this concave point by using weight function, or to the intersectional point which is located on the visible edge and the bisector of the concave angle. The presented algorithm has been applied in the plant design system of PDSOFT Piping software. The results obtained by this method are excellent.