NCF参数化建筑论坛

标题: 拓展思路——纯gh的2维凸包算法 [打印本页]

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

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

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

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

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

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

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

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

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

总之，这是很有意思的一次尝试，也应该可以作为深入学习代码前的热身运动吧。最后gh的文件见附件，象征性收费，不过相信帖子已经讲到如此详细坛友们也不用再看电路图了（我其实很遗憾在论坛里这样细致的帖子少之又少，是各位高手觉得话讲穿了没意思吗？），分享学习心得，用诚意打动斑竹，呼唤加分加照度。

作者: mars1912 时间: 2011-5-6 18:45
沙发，学习了......

作者: rainake 时间: 2011-5-6 19:55
很想知道最新版0.8.0010中依然存在bug吗

作者: panhao1 时间: 2011-5-7 00:08
效率有点低~~~~~~

作者: 绝顶山河 时间: 2011-5-7 01:14
谢楼主分享心得

作者: Benno 时间: 2011-5-7 23:08
好东西，很强大啊，学习学习

作者: leeanwi 时间: 2011-5-7 23:11
haohaohaohaoahao

作者: 子小弓虽 时间: 2011-5-8 00:44
期待更多凸包的建筑实例~~~

作者: ADoKevin 时间: 2011-5-12 02:16
观摩学习一下。。。。。

作者: superzhou30 时间: 2011-5-13 15:10
支持支持。。。谢谢分享、、、

作者: ccc159 时间: 2011-5-19 10:18
很有意思收藏先

作者: iamyyc 时间: 2011-5-19 13:06
我是GH初学者，求师傅~不过还是先要赞一个

作者: wawa 时间: 2011-5-20 14:31
quite good!

作者: ly2164 时间: 2011-5-20 23:38
学习学习ing

作者: 不懂 时间: 2011-5-23 14:20
效率有点低

作者: wawa 时间: 2011-5-26 09:55
it is interesting

作者: neamon 时间: 2011-5-28 08:03
菜鸟路过，学习了

作者: superzhou30 时间: 2011-5-28 08:32
学习学习....

作者: 歪歪的地盘 时间: 2011-5-29 16:19
学了~~~~~牛啊

作者: rocketfeng 时间: 2011-5-30 01:20
真好，很详细的帖子

作者: 关典为 时间: 2011-5-30 18:55
thanks，好好学习啊

作者: imlaen 时间: 2011-6-2 12:25
好看~ 不错

作者: mqcjackson 时间: 2011-6-2 13:48
很麻烦的样子，学习了，如果不画外面的辅助图形就更好了

作者: Ender 时间: 2011-6-4 03:47
支持楼主！！！！！！！

作者: janty 时间: 2011-6-7 22:19
的确很不错的尝试

作者: xh0914 时间: 2011-6-13 18:54
支持，下来学习下

作者: qingxiangxixi 时间: 2011-6-16 22:46
看起来有点烦琐，我对电池不熟，不知道是否还有更简洁的办法达到目的。

作者: mengn619 时间: 2011-6-24 23:31
数学大人呀。。。。

作者: dye 时间: 2011-6-28 21:09
学习下、。。。。。。。。

作者: lcwewei 时间: 2011-6-30 12:28
很有启发意思。支持

作者: nice 时间: 2011-7-1 13:16
顶{:3_47:}楼主比一些装B 的人实在多了

作者: hyl2099 时间: 2011-7-6 11:22
不怎么明白，收藏起来以后再看。

作者: qeqe123 时间: 2011-7-7 19:13
我是GH初学者，求师傅~不过还是先要赞楼主一下

作者: qeqe123 时间: 2011-7-7 19:20
支持了~学习了~ 加了个油~

作者: 123453786 时间: 2011-7-12 11:50
图挂了！！！

作者: Zeff-2011 时间: 2011-7-13 09:47
新版本好像没有BUG吧……

作者: xiuyipin10 时间: 2011-7-16 08:21
这个机器恐怕得选好的

作者: wwqqddssgg 时间: 2011-7-17 00:03
为啥看不到图片呢，郁闷

作者: mumu7 时间: 2011-7-22 13:53
辛苦了！感谢分享！

作者: xielanmin 时间: 2011-7-22 20:28
想说图挂了先收藏嘻嘻

作者: tremulous 时间: 2011-7-28 12:19
学习一下，谢谢楼主分享！！！！！

作者: lsfy 时间: 2011-7-30 09:12
学习了，谢谢楼主

作者: samonaiya 时间: 2011-8-2 12:02
这样的帖子确实挺少的

作者: yugohuang 时间: 2011-8-3 17:15
多谢共享多谢共享

作者: 阳1234阳 时间: 2011-8-3 18:03
怎么看不见图呢

作者: SPARK_XG 时间: 2011-12-14 23:49
好好学习一下

作者: 385186489 时间: 2011-12-15 09:34
什么东西，看不懂

作者: s.k. 时间: 2011-12-15 10:20
弱弱问一句，凸包的含义是……

作者: 丞丞 时间: 2012-1-31 08:09
谢谢楼主分享。。。。

作者: wzlcff 时间: 2012-5-22 21:27
什么是凸包啊？

作者: yosean 时间: 2012-5-23 02:29
下来研究下初学者研究别人的方案就像拆解模型一样有趣

作者: sona 时间: 2013-5-11 21:12
谢谢LZ，学习了~

作者: usherhsx 时间: 2013-5-15 03:03

菜鸟路过，学习了

作者: 左手◆23年 时间: 2014-2-15 14:20
相当的给力，感谢楼主分享！

作者: lzeaf 时间: 2014-3-27 23:48
学习了！！！！！！！！！

作者: liyuqun 时间: 2014-4-20 18:56
支持，下来学习下

作者: 不要长徒 时间: 2014-11-28 11:59
学习了~~~~~

欢迎光临 NCF参数化建筑论坛 (http://bbs.ncf-china.com/)