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

求包含所有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/

为了获得有效的解决方案,可以采用单调链方法( https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain )具体如下:

• 这些站点将多边形分割为两个链,在X上排序;

• 通过X上的比较合并两个上链和两个下链(这是mergesort过程);

• 使用与单调链方法(格雷厄姆行走的一种变体)相同的程序,从上链和下链拒绝反射部位。

总运行时间由以下因素决定:

• n+m比较,以找到极值点;

• n+m+2 h测试左边(有符号区域;h是结果的顶点数)。

因此,复杂度为O(n+m),这不是最优的,但对于您的目的来说可能已经足够好了(当多边形不重叠时,可以使用更复杂的O(Log(n+m)解决方案,但对于较小的多边形大小来说,不值得大惊小怪)。

在本例中,合并的结果只是链的串联,但可能会出现更复杂的情况。

找到这两个集的凸包可行,但以下方法可能更快,因为它只需要按顺序访问多边形顶点:

1. P 和 Q ,从每个顶点中拾取一个顶点 p1 和 q1

2. 在中搜索 Q 顶点 q2 相邻于 第一季度 p1-q1 到 p1-q2

3. 重复,直到达到一个点 qk

4. 现在,反转从 穿过P中的连续顶点,使旋转逆时针直到极限 pl 再次找到。

5. pm pn

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