任意邻近多边形合并算法

冰点123 发布于 09/01 20:01
阅读 288
收藏 0

将两个相邻或相交的任意多边形合并成一个多边形算法该如何做? 类似下图的样子

加载中
0
冰点123
冰点123

有没有大神帮支个招?

 

0
tcxu
tcxu
  1. 何谓多边形合并?
  2. 是否已知所有任意多边形的顶点坐标?
  3. 要合并两个相离最近的多边形,是否允许平移/转动/变形它们,或者添加额外的线段?
  4. .....

 

冰点123
冰点123
多边形顶点都已知,存在相交,相离,包含等情况,多边形不能旋转平移,相交的以最外层交点为连接点合并,相邻的以最近的点融合,完全包含的就是直接使用最外层的多边形
0
edien8wing
edien8wing

两个图形是否是矢量,矢量的话能确定A节点1234 B节点1234,排列组合 A1B1 A1B2 ...的距离,排序获得最小的两个距离就是最近的连线 

冰点123
冰点123
回复 @edien8wing : 看一下我下面补的另一个图,这个用距离判断就不行
edien8wing
edien8wing
回复 @冰点123 : 距离和凹凸无关。
冰点123
冰点123
矢量的,是不是还要考虑凹多边形的情况?
0
冰点123
冰点123

如果用距离判断,下面这种就会出错,黄线是实际应该融合的点

0
edien8wing
edien8wing

那就多加一条判断:不与任何其他已有线段相交

0
冰点123
冰点123

还是不行,排除相交的,计算后发现会有一个多边形多个点到另一个多边形的距离最短

0
tcxu
tcxu
  1. edien8wing   所述,排序获得两个图形中距离最小的两个点: A,B, 并连接 A 和 B。
  2. 再尝试将每个点的两个邻接(adjoining)点分别与对方的两个邻接点相连,最后采纳不与现存边相交的连线结果。

如上图,A 的邻接点是 A_1、A_2。 B 的邻接点是 B_1、B_2。先连接 A、B。再尝试连接相邻点。结果:只有 A_2 —— B_1 可用。

返回顶部
顶部