一种基于边界跟踪扫描线算法的芯片版图图像生成方法

本发明公开了一种基于边界跟踪扫描线算法的芯片版图图像生成方法，通过设计子图‑多边形数据结构，建立子图相邻多边形最大矩阵，利用本方法改进边界扫描线算法实现从完整的芯片版图快速切分子图，以及生成对应的二值图像；本发明的算法设计了子图外接框‑多边形外接框数据结构，快速定位哪些多边形大可能与子图相交。保存这些数据构建当前子图下包含的所有多边形最大的外接框，使得算法不需要计算多边形与子图的交点，减少了算法计算交点的时间消耗；还设计了一种边界跟踪的方式，改进扫描线算法，通过保存边界中每个点，在扫描某一行的时候，不需要计算扫描线与多边形边界的交点，进一步减少算法复杂度。