一种平面区域几何划分的自适应算法

A Self-adaptive Algorithm for Geometric Division of Planar Region

给定一个任意形状的平面区域,使用若干条折线段将该平面区域划分为子区域。当折线段存在不完全贯穿平面区域或包含于区域之中时,提出一种自适应算法,将其延长至最近边界以切割区域,并识别子区域输出。通过记录线段与交点的拓扑关系,并对部分线段进行延长处理,以形成记录全部端点间拓扑关系的网状结构,最终通过最小转角法搜索最佳路径输出全部子区域。实验结果表明,该方法能快速、无重复输出所有子区域,效果良好。

Given a planar region of any shape, divide it into sub-regions by a number of fold line segments. While fold line segments are through it incompletely or contained by it, an self-adaptive algorithm is proposed, to extend lines to the nearest border to cutting area com- pletely, then recognize and output the sub-regions. Base on the record of topological relations between the line segments and the intersec- tions, extend the line segments which are through region incompletely, then to form a mesh structure which record of topological relations between all endpoints. Finally, recognize and output sub-regions through the Minimum-Angle method to search the optimal path. The exper- imental results show that the method could output all sub areas quickly and non-repeatly, had good effect.