一种任意复杂程度二维多边形的求交算法

Intersection of Two Highly Complicated Planar Polygons

对于由直线段和圆弧段组成的大数据量二维多边形,作者提出一种多边形之间求交点的算法。该算法通过区域划分,把一个大规模的求交点运算分解为多个小规模的求交点运算,计算每个区域内的交点,然后对交点集进行整理,去除重复交点。该算法从实用的角度出发,避开繁琐的数学推理,便于理解,便于编程实现。算法明显地提高了求交点的效率,缩短了运算时间,并在实际应用中取得良好的效果。

The planar polygon to be processed is composed of lines and arcs. By means of area partitioning, the whole operation of finding intersection points is subdivided into a set of small-scale problems. All the valid intersection points are sorted to remove duplicated ones. The algorithm is simple and robust.