1

我在随机位置有多个圆圈（作为连接顶点的列表）。

当圆圈相交时，会创建封闭区域（就像在维恩图http://en.wikipedia.org/wiki/Venn_diagram中一样）

如何生成所有这些区域的单独多边形？目标是能够使用单独的多边形为每个区域着色，如下例所示：

在此处输入图像描述

在此处输入图像描述

迭代布尔交集操作是否可以实现通用解决方案？

编辑

下面的简单片段是一个[NodeBox](http://nodebox.net/code/index.php/Home)绘制相交椭圆的脚本。

oval(x0,y0,w,h)创建一个椭圆。

根据doc，路径上的布尔运算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)
4

1 回答 1

3

你说语言不可知，所以我会这样回答。您可以按照您的建议通过对多边形的布尔运算来获得您想要的东西。如果 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++ 中的一个大型通用库，因此有一些学习成本。用于商业目的的许可是棘手的。

于 2013-12-21T17:37:57.650 回答