计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (32): 170-175.

• 图形、图像、模式识别 • 上一篇    下一篇

一种等值线图的任意复杂多边形窗口裁剪算法

赵红波1,张  涵2   

  1. 1.安阳师范学院 物理与电气学院,河南 安阳 455000
    2.安阳工学院 计算机科学与信息工程学院,河南 安阳 455000
  • 出版日期:2012-11-11 发布日期:2012-11-20

Algorithm for contour clipping against general polygon window

ZHAO Hongbo1, ZHANG Han2   

  1. 1.College of Physics & Electrical Engineering, Anyang Normal University, Anyang, Henan 455000, China
    2.College of Computer Science and Information Engineering, Anyang Institute of Technology, Anyang, Henan 455000, China
  • Online:2012-11-11 Published:2012-11-20

摘要: 给出了一种新的海量等值线图任意多边形窗口的快速裁剪算法。计算裁剪多边形的外包围盒并创建网格结构,利用网格结构对等值线进行快速预裁剪,通过链式结构对等值线进行细节裁剪得到最终裁剪结果。通过建立行链式结构可以实现以行扫描的方式快速判断点的内外属性,而且还能减少线段求交运算次数,基本能确定实际相交的线段时才进行求交运算。经过大量的实验,证明该算法非常高效且稳定。另外,新算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。该算法程序实现简单且符合工程需求。

关键词: 等值线, 包围盒, 链式结构, 行扫描, 线段求交

Abstract: This paper presents a new fast algorithm for contour clipping against general complex polygon windows. The new algorithm builds the bounding box of the clipping polygons and creates the grid structure. And the algorithm uses the grid structure to pre-clip the contours quickly. Through linked structure to clip the contours, it could get the final clipping result. This paper can realize the method of row scanning to judge the inside and outside attribute by building the linked structure and reduce the counts of segments intersection. Through many experiments, the new algorithm is proved to be very effective and stable. Additionally, the algorithm can resolve various special cases which contain complex nested polygons and overcome the constraint conditions presented by previous algorithms. The algorithm can be implemented by programs easily, and can accord with requirements of the project.

Key words: contours, bounding box, linked structure, row scanning, segments intersection