基于扫描线法的数字线划图中多边形相交检测算法

摘要

cqvip:针对数字线划图中多边形相交检测问题,提出了一种基于扫描线法的检测算法。该算法将多边形按节点拆分成多个线段,根据多边形节点绘制扫描线,获得扫描线与线段的交点,通过分析交点顺序及从属多边形,检测出相交多边形。算法效率高、数据处理能力强、利于编程实现,算法复杂度跟多边形节点数量正相关,适合处理数字线划图中大批量简单多边形的相交检测。