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

维普资讯 ●经验交流● ￡ ～ 一 种基于加减法求交和顶点类型的 凹多边形水平扫描填色算法 1p l、 苏州大学I学院计算机 I程系 钱汉臣 摘 要 ：本文给出7一种只用加、减运算就能求水平线与凹多边形边界交点的方法。并根 据顶点类型定义 ，将凹多边开j顶点分成 “水平顶点”、 “极点”、 “拐点”三类 ，设计7基 于三类顶点的边界存储结构 ．建立 了凹多边形水平扫描填色算法 ，解决 了当交点为顶点 时可能产生 的 。交点对”不配对的 问题 。 0 关键词：曼边彤，生垦．±堕兰!，极点，拐点，交点对。侄圾 Y2)，且 YI~Y2．则斜率为： 一 、 概述 K 一 多边形填色问题 ，是图象综合的基本 问题之 若某根水平扫描线 yl与浚边交点为 (xl， 一 。 在屏幕坐标系中，通常采用的方法有 “扩散 y1)，按 Y正向变化的下一根水平扫描线 yl+1 法”、 “边界判别法”、 “水平扫描法”等。 与该边交点为 (x2，yl+1)，则该边斜率也可以 “扩散法”基于递归技术 ，但 当多边形由于 写成 ； 精度取舍而不完全封闭时，常会造成扩散色 外 一 一 溢 ”。 “边界判别法”是通过一定的判别方法．只 所 以得迭代公式： 对边界内的点进行填色。但在处理复杂多边形 J 卅亡 时，其判别法的复杂性也高 。 【y2=yl+ 1 “水平扫描法”是求出水平扫描线与边界的 若从该边端点 xl—X1．yl—Y1起 ，就可以 交点，在 “交点对”间填色。但若为凹多边形时， 利用只有加、减运算的迭代公式快速地求出各水 扫描线通过顶点的实际交点数 ，有可能造成交点 平扫描线与各边的所有交点，从而避免了乘除运 一 数为奇数．这将会使色彩漏填或外填 、 、 、、 本文提出的凹多边形扫描算法，不仅能用 算。为了确保 x2在 四舍五入取整后得到的屏幕 加、减法快速地求交点 ．且能根据顶点的类型定 坐标 x2在1／k~0 j时也能不断地增加 ，xl+1／ 义．将凹多边形顶点分成三类 ： “水平顶点”、 k的实型值要保存 。设m：t／k，则求交点的迭代 极点”、“拐点”，解决了当交点为顶点时可能产 公式可修改为：