最小包围盒和最大距离点对在实际生活中有很多运用。
譬如,最小包围盒指的是能包围一个多边形或者一些多边形的最小面积(可能周长)的这样的一个矩形,这个帖子我只是讨论二维的,所以说是矩形,
求得最小包围和就能合理利用材料,选择合适的截面。
在这个算法中,采用了“游标卡尺”的算法,所以运行速度很快,在求出一个形状的凸包之后,就能迅速得到最小矩形。O(n *log(n))的时间复杂度,
大量运算成为可能。
对于CAD本身来说,用getboundingBox得出的结果仅仅是平行与WCS的坐标系统的矩形,而且有时候很不准确,特别对于spline来说,有时候相差很大。
然而,WCS下的boundingBox一般来说不是最小矩形,如果要得到最小的,必须要旋转这个图形很多次才能得到结果,但这时一个费事费力的事情。
所以,我们有必要考虑一种算法。
这些天通过几个比较晚的晚上,终于得出了算法。为了增加讨论效果,我在这里先贴出arx文件,适用于2004-2006平台。至于LISP,以后在贴出。
速度之快,几乎是0秒。
用法: 先输入命令 Hull,
然后输入分弧精度---指的是对样条曲线或者弧形的分段数目,取值在100-2000比较合理,太大容易引起问题且也不能有效提高精度。
选择图形中的多边形或者样条曲线,然后你就可以看到结果了。最远距离用红线标出。
|