栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

清华计算几何大作业(二):CG2017 PA5-1 Dynamic Convex Hull(动态凸包)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

清华计算几何大作业(二):CG2017 PA5-1 Dynamic Convex Hull(动态凸包)

CG2017 PA5-1 Dynamic Convex Hull(动态凸包)
  • 1. 前置知识
  • 2. 思路分析
  • 3. 项目代码(待更新完整)
    • 1.1.1 Numerical Tests
    • 1.1.2 Convex Hull
    • 2.1 Tree
  • 4. 拓展(Follow-ups)
  • 5. 参考资料
  • 6. 免责声明

1. 前置知识
  • Graham Scan,详见前一节

  • 平衡二叉查找树(BBST),本系列特指红黑树

2. 思路分析

问题描述:PA5-1 Dynamic Convex Hull(动态凸包)

题目中涉及两种操作:

第一类:操作向点集中加入点。

第二类:操作查询某个点是否在凸包里(在凸包边界上也视作在凸包里)。

并且提示“第一类操作是计算时间开销的主要部分”和“可能需要实现合适的平衡二叉树”,所以我们先来分析凸包算法(Graham Scan)的时间复杂度。算法整体的时间复杂度为O( nlogn ),n为输入点集的个数。算法中的时间开销主要为两个部分:1)presorting,伪代码第一行,时间消耗为O( nlogn );2)伪代码第二行开始的Scan操作,时间消耗为O( n )。

现在我们如果每插入一个新的点,就运行一次Graham Scan(包括Presorting),假设插入第k个点,那么插入总的时间消耗为:

O( 1 * log1 + 2 * log2 + 3 * log3 + … + k * log k ) -> Eq1

假设总插入点的总数不大于n个,那么整体的时间复杂度为(把里面的因子放大到n):

Eq1 <= O( n * logn + n * logn + n * logn + … + n * log n ) = O ( n * n * logn )

整体的复杂度不尽人意,出现了二次项,那么我们可以思考这么一个问题:Graham Scan算法中的哪一步可以进行优化呢?其实这个答案也非常明确,就是Presorting,每次执行凸包算法,这个步骤必然消耗最高O( n * logn ),那么可以有什么方法对其进行简化么?没错,解决方案就是题目中的另一个提示:可能需要自己实现BBST,如果我们每次插入不是对所有点进行sort,而是利用BBST的有序性,只需O( logn )时间进行插入,后面就可以进行线性时间的Scan。

通过这样处理,那么在插入k次,第k + 1 次插入的的时间消耗为:log( k + 1 ) + k +1,因此总的时间消耗为:

O( k * logk + log( k + 1 ) + ( k + 1 ) + log( k + 2 ) + ( k + 2 ) + … + logn + n ) -> Eq2

同样进行放大处理:

Eq2 <= O( n * logn + log( n ) + ( n ) + log( n ) + ( n ) + … + logn + n ) = O ( n * logn )

从渐进的意义上,我们把原先的时间提升了一个数量级的n。分析完插入,那么查询操作的时间复杂度呢?这里我们使用to left test检查查询点是否都位于每条Extreme Edge 的左边或边上,如果不是,则不再凸包内部,反之则在。因为至多需要检查( n - 1 )条Extreme Edge,所以查询的时间复杂度为O( n )。

结合上面插入的时间复杂度,整个动态凸包的时间复杂度为(假设查询m次):

O ( n * logn ) + m * O( n )

另外,如果能把查询操作优化为O( logn ),可以将整体的时间复杂度降为:

max( n, m ) * O( logn )

但笔者不确定是否能把查询优化为O( logn ),有兴趣的童鞋可以自己探索一下哒~ 如果发现了相应的方法,请联系我的邮箱:402951678@qq.com。

因为这节作业和上一节的作业高度重合,所以不再提供可视化结果,如果有需要的童鞋,可以自己查看上一节里面的可视化程序代码,自己实现相应的功能。

3. 项目代码(待更新完整)

个人作业项目代码:Algorithm

※ 前一节使用的Graham Scan算法已经调整为支持动态凸包算法

1.1.1 Numerical Tests
DescriptionEntry method
toLeft testboolean toLeft( Vector base1, Vector base2, Vector point )
inCircle testdouble inCircle( Vector a, Vector b, Vector c, Vector p )
1.1.2 Convex Hull
DescriptionEntry methodFile
Graham’s ScanList grahamScan( List points )
Brute forceList slowConvexHull( List points )
Program ( including visualization )CG2017 PA5-1 Dynamic Convex Hull
2.1 Tree
DescriptionEntry File
Binary Search Tree ( put(), deleteMin(), deleteMax(), delete(), min(), max(), etc.)BinarySearchTree.java
Red Black Tree ( put(), deleteMin(), deleteMax(), delete(), min(), max(), etc. )RedBlackTree.java
Segment Tree ( Range maximum and minimum Query )SegmentTree.java
Priority QueueMyPriorityQueue.java
Doubly Linked Binary Search Tree ( With the ability delete / insert a node directly from / into the BST )DoublyLinkedBST.java
Doubly Linked Red Black Tree ( With the ability delete / insert a node directly from / into the R-B Tree )DoublyLinkedRBT.java
4. 拓展(Follow-ups)
  1. 考虑是否可以将查询操作从O( n )优化为O( logn )
  2. 使用其他凸包算法来实现动态凸包:Divide-And-Conquer,Jarvis March
  3. 实现更高维的动态凸包算法:3D Convex Hull,详见教材 11.凸包: 混合物(11. Convex Hulls: Mixing Things)

上一节:清华计算几何大作业(一):CG2017 PA1-1 Convex Hull (凸包)

下一节:CG2017 PA1-2 Crossroad (十字路口)

系列汇总:清华计算几何大作业思路分析和代码实现

5. 参考资料
  1. Computational Geometry: Algorithms and Applications
  2. 计算几何 ⎯⎯ 算法与应用, 邓俊辉译,清华大学出版社
  3. 计算几何 | Computational Geometry
6. 免责声明

※ 本文之中如有错误和不准确的地方,欢迎大家指正哒~
※ 此项目仅用于学习交流,请不要用于任何形式的商用用途,谢谢呢;


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948931.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号