拓展思路——纯gh的2维凸包算法

shinsai · 发表于 2011-5-6 11:43:14

凸包也是个经典话题了吧。gh里的convex hull电池自从我在使用中遇到bug后，就对其失去了信任，后来便想尽各种办法绕开这个电池。其实自己动手做，锻炼思考的能力，不算是困难的事情。这个帖子也算是自己做个小小总结，并且我相信做法（纯gh)绝对不止我这一种。那么如何用gh电池实现2维凸包？一步步来，我们先看一个简单的例子：

登录/注册后可看大图

现在这里有六个点，顺序可能是随机乱点的，要用它们作控制点生成一个闭合曲线，不理好点序就不对了，也就是说，这里还没有“包”，只是“凸”的问题。这些点本身顺序是不对的，似乎也难以找到内部的线索去整理它们，那么我可不可以利用外力？如果有一个外部的有序的对象作为参考，然后将这些点按照外部的顺序去整理一下，便该能达到目标。循此思路，我就着各点向外一些先作了一个相似的多段线图案：

登录/注册后可看大图

以原始无序点向着外围有序点的最小距离为线索，找到离外围每个点最近的内部点，这样把得到的六组单个点再拍平一下顺序就可以得到整理，问题得到了初步解决。然而，若是应对大量成组数据，手工画多边形就捉襟见肘了。但是从这个方法里得到了启发，我可以将手工画的多边形转为生成的外围圆，方法很简单，找到所有点的中心点，再指定一个能涵括所有点的半径即可：

登录/注册后可看大图

我把每个原始点都投到了圆上，好处是可以得到一些t值，这些t值显然是有序的，用它们可以轻松为我的原始点排序，至此，“凸”的问题算是得到了较为满意的解答。现在我们可以把问题上升到一般化，将“包”的问题也加进来。我任意点了24个点如下：

登录/注册后可看大图

如果过两两点连线，可以得到一个线图，这个线图中最外围的多边形框就是我们想要的东西：

登录/注册后可看大图

接下来怎么进行呢？简单地说，就是必须把复杂问题转化为简单问题，既然我已经知道了怎么做“包”，如果可以把包在多边形框内部的点都投到多边形框上，问题就能回到上一步：

登录/注册后可看大图

于是就可以继续借助在外围做圆的方法，先把所有点都投到圆上，然后连接每个投影点与对应的原始点，得到24条切割线，用这些线切割此前两两点连线得到的线图中的线，得到的交点中，容易发现距离投影点最近的点就是我们需要的点：

登录/注册后可看大图

在这24个交点里，如果是作为多边形框的原始角点得到的交点，很明显既是角点本身！这么一来就简单了，只需要通过布尔运算抽出原始点与交点里重合的点就能得到凸包多边形的角点：

登录/注册后可看大图

然后就只要重复上一步“凸”的动作，再一次把角点投到圆上，拿到t值，整理点序，问题即告完满解决：