将两个凸的非相交多边形合并为一个

Question

我需要将两个凸的非交叉多边形合并为一个连接的凸多边形，以最小化所产生的面积，如下图所示：​​我正在寻找一个这样做的算法。如果有人向我提供相应的python实现，我也将不胜感激。

Answer 1

如果存在具有这样说，m和n个顶点分别，那么你的问题可以被认为是两个不相交的多边形：

查找包含所有的M +的面积最小的凸多边形n分。话虽如此，看看QuickHull Algorithm这里：http://www.geeksforgeeks.org/quickhull-algorithm-convex-hull/

此外，你也可以检查出这些算法。

贾维斯的算法：http://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/

而且，格雷厄姆的扫描：http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

希望这有助于。

P.S.我想你可以在互联网上的任何地方找到这些算法的python实现。 :)

Answer 2

发现两组的凸包的工作，但下列方法可能更快，只需要访问的多边形顶点顺序：

1. 鉴于多边形P和Q，从每一个挑一个顶点p1和q1。

2. 在Q搜索顶点q2邻接q1使得从p1-q1到p1-q2旋转是顺时针的（这可以使用easyly矢量叉积进行检查）。

3. 重复上述步骤直到您到达点Q其中Q中的两个连续顶点生成并逆时针旋转。

4. 现在，将从p1行进的过程翻转到P中的相邻顶点，使得旋转逆时针旋转直到再次找到极值pl。

5. 从2开始重复，直到不再有可能。您现在有两个点pm和pn，它们是两个顶点，红色区域的一边与上图中的黑色多边形相交。

6. 现在再次重复算法，但改变方向，从顺时针到逆时针，反之亦然，以便找到红色区域另一侧的顶点。

7. 剩下的唯一工作是从已经找到的两个红色区域边和多边形中的区段生成最终的多边形。

Answer 3

对于一个有效的解决方案，你可以按照如下适应单调链法（https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain）：

• 两个多边形，找到最左边和最右边的网站（在领带的情况下，使用最高/最低）;

• 这些网站将多边形分成两个链，这些链按X排序;

• 合并两个上部和两个下部链，并在X上进行比较（这是mergesort的合并）;

• 使用与单调链方法（格雷厄姆步行的变体）相同的程序拒绝来自上部和下部链的反射位点。

总运行时间将由

• N + M比较管辖寻找极端点;

• n + m合并比较;

• n + m + 2 h LeftOf测试（有符号区域; h是结果的顶点数）。

因此，复杂度为O（N + M），这是不是最佳的，但很可能是你的目的不够好（更复杂的O（日志（N + M）的解决方案，能够把多边形没有重叠，但不值得忙乱对于小多边形尺寸）。

在该示例中，合并的结果是链的只是级联的，但可能会出现更复杂的情况。

最后的评论：如果你保留所有的polygo ns作为两个单调链的连接，可以省去上述过程的第一步。