4种凸包算法及计算最大直径，最小包围盒效率比拼

XDSoft · 发表于 2014-11-15 21:56:34

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

4种凸包计算方法的效率测试

QQ截图20141115214801.png

33万个点，不计入采集点时候，纯计算时间如下：

选择对象: all
找到 330000 个

选择对象:

The time for Collecting points is :0.602665 Seconds.
There are 330000 points.
The time for CConvexHULL takes time:  is :0.762448 Seconds. 分治算法
The time for MelkmanHULL takes time:  is :0.355236 Seconds. Melkman算法
The time for GrahamScan takes time:  is :0.349669 Seconds.     扫描算法
The time for ChainHull takes time:  is :0.377123 Seconds.           双头链算法
The time for MaxDistance is :0.000451 Seconds.                      凸包最大直径
The time for MinAreaRectangle is :0.000418 Seconds.                最小包围盒
命令: z

XDSoft · 发表于 2014-11-15 22:02:38

最小包围圆

选择对象: all
找到 330000 个

选择对象:

The time for Collecting points is :0.625469 Seconds.
There are 330000 points.
The time for MEC problem is :0.031495 Seconds.

Highflybird · 发表于 2014-11-15 22:14:16

这个是凸包的维基说明：
http://zh.wikipedia.org/zh/%E5%87%B8%E5%8C%85
英文的更准确：
http://en.wikipedia.org/wiki/Convex_hull
算法说明：
http://en.wikipedia.org/wiki/Convex_hull_algorithms

csharp · 发表于 2014-11-15 22:15:54

高飞版主有个帖子高效凸包算法就是扫描法，按这个算法我在net也发过一个，从算法和结果数据保存，扫描是最快的

/db_自贡黄明儒_ · 发表于 2014-11-17 08:17:31

最小包围盒算法怎么时间这么短？求最小包围盒时难道不用上面的几种算法

XDSoft · 发表于 2014-11-17 08:41:59

/db_自贡黄明儒_ 发表于 2014-11-17 08:17
最小包围盒算法怎么时间这么短？求最小包围盒时难道不用上面的几种算法

最小包围盒和最大直径都是从算出凸包后，开始计时。所以上面没打红色的字。不能把它俩的时间和凸包去比，不是一个应用。

csharp · 发表于 2014-11-17 12:51:32

本帖最后由 csharp 于 2014-11-17 12:53 编辑

50W点求完凸包可能只剩两点，也可能3点，…数量会大大降低，再求最小矩形时用旋转只需要四分之一圆周，最理想情况可能一次就求出minrectang
凸包是很多应用的基础

账号		自动登录	找回密码
密码			立即注册

[发布] 4种凸包算法及计算最大直径，最小包围盒效率比拼

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

相关帖子

点评