python - 将两个凸不相交的多边形合并为一个

Question

我需要以最小化结果面积的方式将两个凸的、不相交的多边形连接成一个连接的凸多边形，如下图所示:我正在寻找这样做的算法。如果有人为我提供相应的 python 实现，我也将不胜感激。

Answer 1

如果有两个不相交的多边形分别有say、m和n个顶点，那么你的问题可以这样想:

寻找包含所有 m+n 个点的最小面积的凸多边形。话虽如此，请在此处查看 QuickHull 算法: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/

希望这对您有所帮助。

附言我认为您可以在互联网上的任何地方找到这些算法的 Python 实现。 :)