%0 Journal Article
%T A New Polygon Filling Algorithm Based on Pertinence Between Point and Its Abutting Sides<br>基于顶点与邻边相关性的多边形填充算法
%A MA Hui
%A LU Guo-dong
%A TAN Jian-rong
%A <br>马辉
%A 陆国栋
%A 谭建荣
%A 吴良
%J 中国图象图形学报
%D 2004
%I 
%X Present polygon filling algorithms including scanline algorithm, seed filling algorithm and the algorithms based on the two classical filling theories, are analyzed and compared in this paper. A new filling algorithm is put forward, which is based on thorough analysis of the relations between point and its abutting sides. This new filling algorithm divides all points of a polygon into five types at firstly, and transforms the polygon into unit areas which are simple triangles and trapeziums by the line passing the points. Using the characteristics of bevel edges, the unit areas filling can replace the multiplication-division with the addition-subtraction. It decreases the time and complexity of filling the whole polygon. This paper explains the design of the algorithm and how it is going on, and also presents the data structures storing the information of points and unit areas. In the end, some experimental results show that the new algorithm has a high efficiency and a good stability.
%K polygon
%K fill algorithm
%K pertinence between point and its abutting sides<br>多边形
%K 填充算法
%K 运算速度
%K 新算法
%K 扫描线
%K 求交
%K 复杂度
%K 顶点
%K 加减运算
%K 梯形
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=D06194629680C940ACE75262F54B9D85&aid=D1B6BFE0624E58EB&yid=D0E58B75BFD8E51C&vid=9CF7A0430CBB2DFD&iid=708DD6B15D2464E8&sid=F4C7ED9FD9D7FC69&eid=2AF38D6ACB828704&journal_id=1006-8961&journal_name=中国图象图形学报&referenced_num=1&reference_num=6