将两个凸不相交的多边形合并为一个
Joining two convex nonintersecting polygons into one
我需要将两个凸的、不相交的多边形连接成一个连接的凸多边形，以最小化结果面积，如下图所示：我正在寻找一种算法来执行此操作。如果有人为我提供相应的 python 实现，我也将不胜感激。
如果有两个不相交的多边形分别有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/
而且，Graham 的扫描：http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
希望对您有所帮助。
P.S。我认为您可以在 Internet 上的任何地方找到这些算法的 python 实现。 :)
找到两组的凸包是可行的，但以下方法可能更快，因为它只需要按顺序访问多边形顶点：
给定多边形P和Q，从每个多边形中挑选一个顶点p1和q1。
在Q中搜索与[=13=]相邻的顶点q2，使得从p1-q1到p1-q2的旋转是顺时针的（这可以使用矢量叉积轻松检查）。
重复直到你到达一个点qk，其在Q中的两个相邻顶点生成逆时针旋转。
现在，反转从 p1 穿过 P 中相邻顶点的过程，使得旋转是逆时针方向，直到再次找到极端 pl。
从 2 开始重复，直到无法再前进。您现在有两个点 pm 和 pn，它们是上图中红色区域的一侧与黑色多边形相交的两个顶点。
现在再次重复该算法，但改变方向，从顺时针到逆时针，反之亦然，以便找到红色区域另一侧的顶点。
唯一剩下的工作是根据已经找到的两个红色区域边和多边形的线段生成最终的多边形。
为了获得有效的解决方案，您可以按如下方式调整单调链方法 (https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)：
对于两个多边形，找到最左边和最右边的站点（如果是平局，分别使用 highest/lowest）；
这些站点将多边形分成两条链，在 X 上排序；
合并上下两条链，在X上进行比较（这是mergesort的pass）；
使用与单调链方法（格雷厄姆步法的变体）相同的程序拒绝上下链的反射位点。
总 运行 时间将由
n + m 次比较找出极值点；
n + m 次比较合并；
n + m + 2 h LeftOf tests (signed area; h is the number vertex of the result).
因此，复杂度为 O(n + m)，这不是最优的，但很可能足以满足您的目的（当多边形不重叠时，更复杂的 O(Log(n + m) 解决方案是可能的，但不值得为小多边形尺寸大惊小怪。
在示例中，合并的结果只是链的串联，但可能会出现更复杂的情况。
结语：如果将所有多边形保留为两个单调链的串联，则可以省去上述过程的第一步。
我需要将两个凸的、不相交的多边形连接成一个连接的凸多边形，以最小化结果面积，如下图所示：
如果有两个不相交的多边形分别有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/
而且，Graham 的扫描：http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
希望对您有所帮助。
P.S。我认为您可以在 Internet 上的任何地方找到这些算法的 python 实现。 :)
找到两组的凸包是可行的，但以下方法可能更快，因为它只需要按顺序访问多边形顶点：
给定多边形
P和Q，从每个多边形中挑选一个顶点p1和q1。在
Q中搜索与[=13=]相邻的顶点q2，使得从p1-q1到p1-q2的旋转是顺时针的（这可以使用矢量叉积轻松检查）。重复直到你到达一个点
qk，其在Q中的两个相邻顶点生成逆时针旋转。现在，反转从
p1穿过 P 中相邻顶点的过程，使得旋转是逆时针方向，直到再次找到极端pl。从 2 开始重复，直到无法再前进。您现在有两个点
pm和pn，它们是上图中红色区域的一侧与黑色多边形相交的两个顶点。现在再次重复该算法，但改变方向，从顺时针到逆时针，反之亦然，以便找到红色区域另一侧的顶点。
唯一剩下的工作是根据已经找到的两个红色区域边和多边形的线段生成最终的多边形。
为了获得有效的解决方案，您可以按如下方式调整单调链方法 (https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)：
对于两个多边形，找到最左边和最右边的站点（如果是平局，分别使用 highest/lowest）；
这些站点将多边形分成两条链，在 X 上排序；
合并上下两条链，在X上进行比较（这是mergesort的pass）；
使用与单调链方法（格雷厄姆步法的变体）相同的程序拒绝上下链的反射位点。
总 运行 时间将由
n + m 次比较找出极值点；
n + m 次比较合并；
n + m + 2 h LeftOf tests (signed area; h is the number vertex of the result).
因此，复杂度为 O(n + m)，这不是最优的，但很可能足以满足您的目的（当多边形不重叠时，更复杂的 O(Log(n + m) 解决方案是可能的，但不值得为小多边形尺寸大惊小怪。
在示例中，合并的结果只是链的串联，但可能会出现更复杂的情况。
结语：如果将所有多边形保留为两个单调链的串联，则可以省去上述过程的第一步。