如何组合复杂的多边形?

给定两个多边形:

POLYGON((1 0, 1 8, 6 4, 1 0)) POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5)) 

我怎样才能计算联合(组合多边形)?

替代文字http://blogs.msdn.com/blogfiles/davidlean/WindowsLiveWriter/SQL2008SpatialSamplesPartn2onnGeometricS_C45F/STUnion_2.png

戴夫的例子使用SQL服务器来产生联盟,但我需要在代码中完成相同。 我正在寻找一个math公式或代码示例的任何语言,公开实际的math。 我试图制作将国家dynamic地结合到地区的地图。 我在这里问了一个相关的问题: 分组地理形状

这是一个非常好的问题。 我前段时间在c#上实现了相同的algorithm。 该algorithm构造了两个多边形的一个共同的轮廓(即构造一个没有孔的联合)。 这里是。


目标

第1步。创build描述多边形的graphics。

input:第一个多边形(n个点),第二个多边形(m个点)。 输出:graphics。 顶点 – 多边形的交点。

我们应该find交集。 迭代两个多边形中的所有多边形边[O(n * m)]并find任何交点。

  • 如果找不到交点,只需添加顶点并将其连接到边。

  • 如果find任何交点,按长度排列它们的起点,添加所有顶点(起点,终点和交点),并将它们(已按sorting顺序)连接到边界。 图形

步骤2.检查构build的graphics

如果在创buildgraphics时没有find任何交点,则有以下条件之一:

  1. Polygon1包含polygon2 – 返回polygon1
  2. Polygon2包含polygon1 – 返回polygon2
  3. Polygon1和Polygon2不相交。 返回polygon1和polygon2。

第3步。find左下angular的顶点。

find最小的x和y坐标(minx,miny)。 然后find(minx,miny)和多边形点之间的最小距离。 这一点将是左下angular的一点。

左下角

第4步。构build共同的轮廓。

我们开始从左下angular开始遍历图表,并继续下去,直到我们回到原点。 一开始,我们将所有的边缘都标记为未访问。 在每次迭代中,您应该select下一个点并将其标记为已访问。

要select下一个点,请select逆时针方向上内angular最大的边。

我计算了两个vector:当前边的vector1和下一个未访问边的vector2(如图所示)。

对于我计算的vector:

  1. 标量产品(点积)。 它返回一个与vector之间的angular度相关的值。
  2. vector产品(交叉产品)。 它返回一个新的向量。 如果这个vector的z坐标是正的,标量乘以逆时针方向的直angular。 否则(z坐标是负的),我计算vector之间的夹angular作为标量积的360度angular。

因此,我得到了最大angular度的一个边(和一个对应的下一个顶点)。

我将结果列表添加到每个通过的顶点。 结果列表是联合多边形。 矢量

备注

  1. 这个algorithm允许我们合并多个多边形 – 迭代地应用多边形对。
  2. 如果你有一条由许多贝塞尔曲线和线组成的path,你应该首先将这个path平坦化。

你需要确定哪些点在里面 。 删除这些点后,可以将一组“外部”点插入另一个点。 您的插入点(例如右侧图片中的箭头所在的位置)是您必须从input集中删除点的位置。

这是一个充满挑战但很好理解的主题,通常以“多边形的规则化布尔运算”为名。 你可以看看这个MathOverflow的答案 ,其中包括下图(来自Alan Murta的剪辑库 ),粉红色的联盟是OP的组合


BooleanOps


好问题! 我以前从来没有尝试过,但现在我会采取一些措施。

首先:你需要知道这两个形状重叠的地方。 为此,您可以查看Polygon A中的每个边,并查看它与Polygon B中的相交点和边的位置。在此示例中,应该有两个交点。

然后:使联合形状。 您可以取A和B中的所有顶点以及交点,然后排除最终形状所包含的顶点。 为了find这些点,看起来好像你可以findB内的A的任何顶点,以及A内的B的任何vertext。

尝试gpc 。

这里描述了我见过的使用BSP树的解决scheme。

基本上,它描述了在多边形B内 (包括部分边,并使用BSP树计算)的多边形A的边的并集的交集。 然后,可以定义A / B为〜(〜A / \〜B),其中〜代表倒转多边形的绕组,/表示联合和/ \表示相交。

在分组国家时,我希望没有重叠 – 你可以采取一个相当天真的algorithm,寻找共享顶点 – 一个简单的视图将是遍历一个多边形上的点,看看它是否在任何其他多边形,并共享相同的下一个或前一个点,以查看是否有匹配。 然后只是删除共享顶点来创build你的联盟

我今天需要解决这个问题,并find了这个lib的解决scheme: http : //www.cs.man.ac.uk/~toby/alan/software/ 。

它有很多语言实现,包括Java,Obj-C,C#,Lua,python等。