如何组合复杂的多边形？
给定两个多边形：
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任何交点，则有以下条件之一：
- Polygon1包含polygon2 – 返回polygon1
- Polygon2包含polygon1 – 返回polygon2
- 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：
- 标量产品（点积）。 它返回一个与vector之间的angular度相关的值。
- vector产品（交叉产品）。 它返回一个新的向量。 如果这个vector的z坐标是正的，标量乘以逆时针方向的直angular。 否则（z坐标是负的），我计算vector之间的夹angular作为标量积的360度angular。
因此，我得到了最大angular度的一个边（和一个对应的下一个顶点）。
我将结果列表添加到每个通过的顶点。 结果列表是联合多边形。 
备注
- 这个algorithm允许我们合并多个多边形 – 迭代地应用多边形对。
- 如果你有一条由许多贝塞尔曲线和线组成的path，你应该首先将这个path平坦化。
你需要确定哪些点在里面 。 删除这些点后，可以将一组“外部”点插入另一个点。 您的插入点（例如右侧图片中的箭头所在的位置）是您必须从input集中删除点的位置。
这是一个充满挑战但很好理解的主题，通常以“多边形的规则化布尔运算”为名。 你可以看看这个MathOverflow的答案 ，其中包括下图（来自Alan Murta的剪辑库 ），粉红色的联盟是OP的组合 ：
好问题！ 我以前从来没有尝试过，但现在我会采取一些措施。
首先：你需要知道这两个形状重叠的地方。 为此，您可以查看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等。
