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://ncf-china.com/) Powered by Discuz! X3.2