投稿

计算几何课堂：几何寻路之旅

1.2万

48

2021-07-29 13:58:20

未经作者授权，禁止转载

正在缓冲...

因为几何寻路之旅所涉及的算法很多，所以我出了一个系列教学视频，讲解了下面相关的四个算法和两个代码实现问题： 1. 单调多边形拆分； 2. 三角拆分； 3. 对偶图 + BFS； 4. 漏斗算法； 5. DCEL； 6. 项目代码解析；如果大家有任何的问题和建议，都可以给我留言，我会第一时间给大家回复，谢谢大家啦~ 相关代码，文章和参考资料：https://blog.csdn.net/fengkeyleaf/article/details/119207436

fengkeyleaf 发消息

经常二次元，偶尔敲代码

一口气玩到凌晨两点，太上头了！

这游戏太上头了

1.1 背景介绍

09:43

2.1 什么是单调多边形

03:37

2.2 例子：单调多边形

06:27

2.3 五种顶点类型

06:48

2.4 例子：5种顶点类型

06:55

2.5（拓展）证明：去除split和merge vertex一定为单调多边形

06:19

2.6 如何拆解split和merge vertex

09:53

2.7 伪代码讲解

10:36

2.8 例子：单调多边形拆分

16:12

2.9（拓展）如何处理水平边

09:30

3.1 艺术画廊问题（Art Gallery Problem）

07:43

3.2（拓展）证明：拆分成n-2个三角形

11:49

3.3（拓展）三染色问题（3-coloring Problem）

12:40

3.4 三角拆分算法思路

07:17

3.5 伪代码讲解

04:47

3.6 例子：三角拆分

09:06

4.1 BFS复习

08:34

4.2 生成对偶图

06:33

4.3 例子：在对偶图中进行BFS

01:39

5.1 什么是漏斗？

02:40

5.2 例子：漏斗算法 & 伪代码讲解

09:59

5.3（拓展）如何判断漏斗的大小

07:43

5.4（拓展）左右顶点究竟是什么？

05:02

5.5（拓展）证明：导航边两端顶点类型相反

04:17

5.6（拓展）例子：寻找左右顶点

04:04

5.7（拓展）apex和左右顶点共点的处理方法

11:45

6.1 DCEl是什么？

13:45

6.2 例子：DCEL

06:35

6.3 基本操作

05:20

6.4 如何合并边

08:38

6.5 如何计算两边夹角

10:21

7.1 如何实现DCEL基本数据结构

08:37

7.2 如何实现DCEL的操作

07:21

7.3 数据预处理

09:44

7.4 如何实现单调多边形拆分

09:13

7.5 三角拆分预处理

04:50

7.6 如何实现三角拆分

09:47

7.7 如何生成对偶图

03:55

7.8 实现在对偶图中的BFS

05:03

7.9 如何实现漏斗算法

13:03

顶部