算法创建封闭区域的多边形 [英] Algorithm to create polygons of enclosed areas

问题描述

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

在圆相交，禁渔区创建（就像在维恩图的http：// EN。 wikipedia.org/wiki/Venn_diagram ）

我如何生成所有这些领域的独立多边形？的目标将是能够以色每个区域有独立的多边形像在本实施例

是一个通用的解决方案可能与反复的布尔交集操作？

修改

下面的简单文档片断是 [NodeBox]（http://nodebox.net/$c$c/index.php/Home）脚本绘制椭圆相交

椭圆形（X0，Y0，W，H）创建一个椭圆形。

按照 DOC ，在路径布尔操作，如 P [19] .difference（第[17]）会给出一个平的结果（由无数的直线段）。

的路径的坐标可以被添加或改变。

 尺寸（500，500）

p值= []
S = 54
NOFILL（）
中风（0）
对于k中的xrange（10）：
    瓦特= 10 + K * S / 2
    W2 = 10 + K * S
    H = 10 + K * S
    H2 = 10 + K * S
    p.append（椭圆形（宽/ 2  -  W / 2，高度/ 2  -  H / 2，W，H，画出= FALSE））
    p.append（椭圆形（宽/ 2  -  W2 / 2，高度/ 2  -  H2 / 2，W2，H2，画= FALSE））


CP = P [19] .difference（第[17]）。相交（对[18]，平整度= 0.3）

对于PI中的电话号码：
    drawpath（PI）的

填充（颜色（1,0,0））
drawpath（CP）
 

解决方案

您说的语言无关，所以我会回答这个问题的方式。你可以得到你想要的多边形布尔运算为你建议。如果F是一组不相交的多边形和P是一个新的多边形重叠一个或多个F，那么，你想要做到这一点：

 设p = P
对于F中的每个多边形˚F
  由F-p换上f和相交（F，P）。
  集P = P-F
结束
加上p来˚F
 

我们的想法是使用新的多边形p来分割现有的平的多边形F中成份与对共享和不与对共享的，然后从对删除重叠与原来多边形本身并继续。当你这样做，有什么剩下的p是，曾与F中任何事情没有重叠的部分，所以我们增加了一个新的多边形F。

因此​​，为了处理随机收集圆形的多边形，在开始使用F含有它们中的一个（这当然是一个平面集合！）并添加更多的，一次一个，直到完成。

在实践中，这是令人眼花缭乱比定制算法效率较低。一个标准的方法来处理这​​样的问题是扫线技术。想象一下，一条垂直线由左到右在圈子sweepling。由于倒是一个圆圈，它开始建设一个多边形。当它接触的交点，一个多边形关闭，二继续，并且一个新的打开（在一般情况下）。当它到达一个圆的righmost点，相关的多边形关闭。阿封闭多边形被从扫描行中删除，并加入到输出列表。扫描线算法不概念上困难，但实现是繁琐的特殊情况下，丰富（尤其是用于线平行于所述清扫器和当一个多边形的一个顶点位于上的另一边缘，虽然一般的技术工作的这些输出是的仿真简单）。

广义的安排是计算几何的用来形容这类问题的一个术语。广义的安排行，段和/或多边形的集合（正常arrangments只是套系）。例如，的CGAL库广义安排可以做的正是你的问题高效率的置疑。 CGAL是在C ++中一个大的，一般libarary，因此有一定的学习成本。许可用于商业用途是棘手的。

I have multiple circles (as list of connected vertices) at random positions.

When the circles intersect, closed areas are created (just like in a venn diagram http://en.wikipedia.org/wiki/Venn_diagram)

How do I generate separate polygons of all of these areas? The goal would be to be able to color every region with a separate polygon like in this example:

Is a general solution possible with iterative boolean intersection operations?

EDIT

The following simple snipped is a [NodeBox](http://nodebox.net/code/index.php/Home) script that draws intersecting ellipses.

oval(x0,y0,w,h) creates an ellipse.

According to the doc, boolean operations on paths like p[19].difference(p[17]) will give a "flat" result ("made up of numerous straight line segments").

Coordinates of a path can be added or changed.

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)    

解决方案

You said language agnostic, so I'll answer that way. You can get what you want with boolean operations on polygons as you propose. If F is a set of non-intersecting polygons and P is a new polygon that overlaps one or more of F, then, you'd want to do this:

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

The idea is to use the new polygon p to split existing "flat" polygons in F into parts shared with p and not shared with p, then remove that overlap with the original polygon from p itself and continue. When you've done that, what's left of p is the part that had no overlap with anything in F, so we add that as a new polygon to F.

So to handle a random collection of circular polygons, you start with F containing one of them (which is certainly a flat collection!) and add more, one at a time, until done.

In practice, this is blindingly less efficient than a custom algorithm. A standard way to handle problems like this is the sweep line technique. Imagine a vertical line sweepling from left-to-right over the circles. As it "touches" a circle, it starts building a polygon. When it touches an intersection, one polygon closes, two continue, and a new one opens up (in the general case). When it reaches the righmost point of a circle, the associated polygon closes. A "closed" polygon is removed from the sweep line and added to an output list. Sweep line algorithms are not conceptually difficult, but implementation is fiddly with special cases abounding (particularly for lines parallel to the sweeper and when a vertex of one polygon lies on an edge of another, though a general technique for working these out is simulation of simplicity).

"Generalized arrangement" is a term of computational geometry used to describe problems like this. A generalized arrangement is a collection of lines, segments, and/or polygons (normal arrangments are just sets of lines). For example, the CGAL library for generalized arrangements can do exactly your problem with high efficency. CGAL is a big, general libarary in C++, so there are some learning costs. Licensing for commercial purposes is tricky.

这篇关于算法创建封闭区域的多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！