求解简单多边形间包含关系的扫描线算法

A PLANE SWEEP ALGORITHM FOR DETERMINING THE ENCLOSURE RELATIONS AMONG SIMPLE POLYGONS

摘要: 对于任意给定的一簇互不相交的简单多边形，本文提出一种旨在确定簇中多边形之间包含关系的扫描线法，并对其正确性和复杂性作出分析。实践表明此算法是很有效的

Abstract: This paper presents a plane sweep algorithm for determing the enclosure relations among a family of non-intersection simple polygons. The correctness and complexities of the algorithm are analysed. The practice shows that the algorithm is very efficient.