创建封闭区域的多边形的算法
同步
我在随机位置有多个圆（作为连接的顶点列表）。
当圆相交时，将创建封闭区域（就像在维恩图中http://en.wikipedia.org/wiki/Venn_diagram一样）
如何为所有这些区域生成单独的多边形？我们的目标是能够使用一个单独的多边形为每个区域着色，如下例所示：
迭代布尔交集运算是否可能提供通用解决方案？
编辑
以下简单的片段是[NodeBox](http://nodebox.net/code/index.php/Home)绘制相交椭圆的脚本。
oval(x0,y0,w,h) 创建一个椭圆。
根据文档，在类似路径上的布尔运算p[19].difference(p[17])将给出“平坦”结果（“由许多直线段组成”）。
可以添加或更改路径的坐标。
size(500, 500)
p = []
s = 54
nofill()
stroke(0)
for k in xrange(10):
w = 10+k*s/2
w2 = 10+k*s
h = 10+k*s
h2= 10+k*s
p.append( oval(WIDTH/2 - w/2, HEIGHT/2 - h/2, w, h, draw=False))
p.append( oval(WIDTH/2 - w2/2, HEIGHT/2 - h2/2, w2, h2, draw=False))
cp = p[19].difference(p[17]).intersect(p[18], flatness = 0.3)
for pi in p:
drawpath(pi)
fill(color(1,0,0))
drawpath(cp)
基因
您说的语言不可知，所以我会这样回答。您可以根据建议对多边形进行布尔运算来获得所需的内容。如果F是一组不相交的多边形，而P是一个新的与F重叠的一个或多个多边形，则您需要这样做：
Let p = P
for each polygon f in F
Replace f by f-p and intersect(f, p).
Set p = p-f
end
add p to F
想法是使用新的多边形p将F中现有的“平面”多边形拆分为与p共享但不与p共享的部分，然后从p自身中删除与原始多边形的重叠并继续。完成此操作后，p剩下的就是与F中任何内容都不重叠的部分，因此我们将其添加为F中的新多边形。
因此，要处理圆形多边形的随机集合，请从F开始，其中包含其中一个（当然是平面集合！），然后一次添加一个，直到完成。
实际上，这比自定义算法效率低得多。处理此类问题的标准方法是扫线技术。想象一下一条垂直线，从左到右掠过圆圈。当它“接触”一个圆时，它开始构建多边形。当它碰到一个相交点时，一个多边形关闭，两个继续，然后打开一个新的多边形（通常）。当其到达圆的最高点时，关联的多边形关闭。从扫描线中删除了一个“封闭”多边形，并将其添加到输出列表中。扫掠线算法从概念上讲并不困难，但是在特殊情况下（尤其是与扫掠器平行的线以及一个多边形的顶点位于另一个多边形的边缘时）尤其容易实现简化的模拟）。
“广义排列”是用于描述此类问题的计算几何学术语。广义排列是线，线段和/或多边形的集合（正常排列只是线的集合）。例如，用于通用排列的CGAL库可以高效地解决您的问题。CGAL是C ++中的一个大型通用库，因此存在一些学习成本。用于商业目的的许可非常棘手。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
创建多边形的算法
- 2
在区域（多边形）上创建标记链接
- 3
多边形分解算法
- 4
多边形分解算法
- 5
获取通过移动多边形创建的多边形
- 6
由减去的多边形创建的多边形
- 7
凸多边形内的区域
- 8
填写内部多边形的外部区域
- 9
必应地图中的多边形区域
- 10
在多边形区域之间填充
- 11
计算多边形不重叠的区域
- 12
用素面查找多边形区域
- 13
按区域过滤 shapefile 多边形
- 14
计算多边形中点数的算法
- 15
R：多边形合并算法
- 16
点多边形算法说明
- 17
计算多边形中点数的算法
- 18
形成凸多边形的算法
- 19
确定多边形背面的算法
- 20
从一组相邻三角形创建多边形的算法
- 21
如何在Altair图表上绘制封闭的多边形
- 22
封闭多边形的开放式街道地图
- 23
Python Turtle图形填充非封闭多边形
- 24
查找二维多边形的封闭点
- 25
用pyglet绘制多边形会创建不需要的重叠区域
- 26
算法创建正方形内n个角的多边形（HTML5-Canvas）？
- 27
从多边形SqlGeographys创建MultiPolygon SqlGeography
- 28
如何创建多边形div
- 29
从详细的shapefile创建新的多边形
我来说两句