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

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 vertexcs ; 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-lilling algorithm , ihns 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.