最小包围盒和最大距离点对

xuzhendong528 · 发表于 2010-6-5 16:40:33

经典图书

最小包围盒和最大距离点对在实际生活中有很多运用。
譬如，最小包围盒指的是能包围一个多边形或者一些多边形的最小面积（可能周长）的这样的一个矩形，这个帖子我只是讨论二维的，所以说是矩形，
求得最小包围和就能合理利用材料，选择合适的截面。
在这个算法中，采用了“游标卡尺”的算法，所以运行速度很快，在求出一个形状的凸包之后，就能迅速得到最小矩形。O(n *log(n))的时间复杂度，
大量运算成为可能。
对于CAD本身来说，用getboundingBox得出的结果仅仅是平行与WCS的坐标系统的矩形，而且有时候很不准确，特别对于spline来说，有时候相差很大。
然而，WCS下的boundingBox一般来说不是最小矩形，如果要得到最小的，必须要旋转这个图形很多次才能得到结果，但这时一个费事费力的事情。
所以，我们有必要考虑一种算法。（至于其他CAD程序，有没有相似的功能，我不知道）
这些天通过几个比较晚的晚上，终于得出了算法。

用法：先输入命令 Test,
然后输入分弧精度---指的是对样条曲线或者弧形的分段数目,取值在100-2000比较合理,太大容易引起问题且也不能有效提高精度。
选择图形中的多边形或者样条曲线（可多条），然后你就可以看到结果了。最小面积包围矩形用用红线标出。
另外，你可以稍加修改，就可以用这个程序来计算最小周长包围矩形。
另外我附加了求最远距离的程序，和一个用Graham 扫描法求凸包的程序，这两个程序我写的自认为很简洁。仅仅短短的几行，就能达到很高的效率。
另外，我已经编写好了arx代码，基于这里只是讨论lisp，故不贴出源文件。
需要附加说明的是:
如你需要转载，请你说明帖子的来源和原创者。这是尊重我的劳动的起码要求，也是这个论坛的共享“人人为我，我为人人”的体现，而不是一味的索求源码。强烈鄙视拿这些代码卖钱的行为！
关于对这个问题的算法的分析和时间的复杂度的分析，不妨请你参考如下的帖子：

MinAreaRectangle.rar (4.15 KB, 下载次数: 40)