一种基于加减法求交和顶点类型的凹多边形水平扫描填色算法

本文给出了一种只有加减运算就能求大平线线与凹多边形边界交点的方法，并根据顶点类型定义，将凹多边形顶点分成“水平顶点”、“极占”、“拐点”三类。设计了基于三类顶点的边界存储结构；建立了凹多边形水平扫描填色算法，解决了当交为顶点时可能产生的“交点对”不配对的问题。

A HORIZONTAL SCAN COLOR FILLING ALGORITHM BASED ON FINDING CROSSING WITH ADDITION AND SUBTRACTION AND VERTEX TYPE FOR CONCAVE POLYGONS

This paper gives an algorithm of crossings between horizontal lines and the boundaries of a, concave polygon by means of mere addition and subtraction. According to the definition of vertex, it divides: three types of concave vortexes: Horizontal Vertex, Maximum Vertex and Turning Vertex, upon which it builds up a storage structure for their boundaries and establishes the concave-horizontal-scan-color-filling algorithm, thus presenting a method to deal with the problem of a "crossing pair" with one crossing missing in the case of vertex itself being the crossing.