海量数据多边形布尔运算的区域分割算法

研究了一种大数据量的2维多边形,称为海量数据多边形,其边界由直线段和圆弧段组成,顶点很多,形状复杂。本文设计并实现了海量数据多边形之间的布尔运算算法。首先用区域划分的方法快速求解出两多边形的交点,然后判断各交点的出点、入点性质,最后沿着多边形的边界跟踪,并根据并、交、差的不同要求切换跟踪路线,直到形成封闭的回路。运算结果仍为2维多边形。该算法从实用的角度出发,避开繁琐的数学推理,易于程序实现,在实际应用中显著提高了布尔运算的效率。

Area Partitioning Algorithm of Boolean Operations on Highly Complicated 2D Polygons

In this paper,Boolean operations on a kind of highly complicated 2D polygons having a large amount of data is concerned.Each polygon is composed of line segments and arc segments,which has a great number of vertices and is of a complicated geometric shape.This algorithm of Boolean operations is introduced specially for these 2D polygons.By area partitioning,the algorithm calculates the intersection points of two polygons.Then it determines the crossing condition at the position of each intersection point,and traces the edges of polygons to form a closed cycle according to the requirement of union,intersection or subtract operation.The results are also 2D polygons.The algorithm is designed from the aspect of practicality,avoiding the complex mathematic reasoning.It can be coded conveniently and improves the efficiency of Boolean operations greatly in practice.