多段线切割多边形

概述

多段线切割多边形,直观上来说首先就是求多段线与多边形之间的交点,然后利用这些交点与多边形顶点构成多边形,这样一个多边形就被切割成多个多边形。如下图所示:


多段线与多边形
切割后的多边形

主要过程

以下图所示的分割为例,做简短说明:


示例

难点

  1. 如何连接交点与顶点?如上图所示,切割的多边形为AB21,D34,E56,12C3456F;当我们求出交点之后,如何组织交点与顶点的连接很重要,一个解决方法是将多边形的边界与多段线组成有向边,依据他们的方向来进行组织连接;
  2. 剔除不合理的多边形?很明显,C23这个多变形不符合要求,因为它位于多边形的外侧,这个要去除掉;

过程

对于上述难点,本文主要是利用geos中构建多边形的方法来解决,尤其是难点1,具体的原理可参考直线切割凹多边形
1.获取带分割的几何图形,注意该几何图形是线形的,主要包括待切割的闭合环(如多边形的边界)以及分割线;

geos::geom::Geometry *tempG = _geos_geometry->getBoundary();
geos::geom::Geometry *tempG1 = tempG->Union(_asGeos(splitline));

2.构建多边形,在geos主要是Polygonizer类,获取所有分割的多边形,当然也包括类似C23这样不合理的多边形,下一步是剔除这些多边形;

geos::operation::polygonize::Polygonizer pz;
pz.add(tempG1);
std::vector< geos::geom::Polygon*> *result_geom = pz.getPolygons();

3.剔除不合理多边形,理论上来说,切割出来的多变如果被原始多边形包含就可以保留,调用geos中的Cover或Contains等拓扑计算便可以,但是在实际操作过程中有两个问题:
(1)拓扑计算不正确,每次返回值都是false,猜测可能是精度问题,因为如果坐标都是整型,可以返回正确结果;
(2)效率不高,相对于contain和within,建议在geos中优先使用cover或coverby。具体可参考九交模型
所以选取一个折中方案,如下所示:

//过滤掉不在多边形内部的切割面;
//不能直接用包含和覆盖直接判断,存在精度问题;
//利用切割面与原始多边形相交后的多边形面积与切割面的面积之比判断;
//比值在0.99~1.01之间;

4.最后得到的就是一个vector集合,数据类型是geos::geom::Polygon*

相关链接

GEOS库一些自己的见解和注意点
GEOS库学习之三:空间关系、DE-9IM和谓词

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言 多边形偏移 (polygon offset) 算法可能我们印象不深,不过用过 autoCAD 的同学应该有印...
    zyl06阅读 14,010评论 19 14
  • 引言 自从今年春天选修了计算机图形学课程,这朵乌云就在头顶盘旋不散。始终弄不明白计算机图形学到底在研究什么,所谓的...
    金戈大王阅读 61,393评论 35 61
  • 1. 矢量减法 设二维矢量 P = (x1,y1) ,Q = (x2,y2) 则矢量减法定义为: P - Q = ...
    潭潭_180阅读 6,738评论 0 1
  • 最近做的一个小算法,使用平行线填充一个多边形区域。用过 AutoCAD 的同学应该知道,可以选定一个区域,指定平行...
    zyl06阅读 10,010评论 0 2
  • 虽然已经一年多没有维护gbox这个图形库项目了,最近确实时间不够用。。。 今年的重点是把xmake彻底正好,至少在...
    waruqi阅读 5,309评论 0 50