矩形包围盒碰撞检测

最近在项目当中遇到一个需求,也是一个我们平常十分常见的操作,那就是框选操作,但是对于正常元素来说,我们只需要计算框选框是否包裹了当前的目标元素就可以知道当前元素是否选中,但是项目中的元素会存在旋转的情况,所以计算起来就会有些复杂了,所以就抽了些时间深入的了解了一下,也在这里记录记录

最终代码可见 转向包围盒(OBB) 这个在线示例

排序算法

之前我们介绍过了在平常经常会遇到的 查找算法,今天我们就在来看看另一类比较常见而且非常重要的算法,那就是『排序算法』,排序算法在所有的算法当中应该算是应用最为广泛的一类算法

散列表查找

之前我们在 查找算法 的章节当中介绍了一些比较常见的查找算法,比如对于数组 a[],如果我们要在其中查找 key 关键字的记录,可以使用顺序表查找的方式,一个一个挨着排查,也可以使用有序表的一些查找方式,比如二分,插值等

但是如果序列是无序的呢,针对于无序序列,我们之前也介绍过了 二叉排序树 的方式来进行查找,但是二叉排序树的生成过程比较复杂,那么有没有一种针对不太复杂的无序序列,使用起来更为简便的形式呢,那就是我们今天所要介绍的『散列表查找』

平衡二叉排序树

在上一节当中,我们介绍了 二叉排序树 以及它的查找和删除等操作,但是它其实是存在一定问题的,至于到底是什么问题,下面我们慢慢来看

二叉排序树

我们在上一章的 查找算法 当中介绍了算法的分类和一些比较常用的算法,比如二分,插值等等,但是它们的使用都需要一个前提条件,那就是『元素必须是有序的』,那么如果对于无序列表,我们又需要怎么来进行处理呢?这也就是我们今天将要介绍到的『二叉排序树』

查找算法

在本章当中,我们将会介绍一类在平常开发过程当中经常会使用的算法,那就是查找算法,关于查找算法肯定不需要多说,都是耳熟能详的,什么顺序、二分之类的就算是没有用过应该也听闻过,那么今天我们就来简单的总结整理一下查找算法的分类和一些比较常用的算法

关键路径

在上一章当中我们研究了 最短路径 的相关算法,它们是迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd),本章我们就来了解一下关键路径的一些相关算法,这也是图结构相关内容的最后一部分,但是在展开之前,我们需要先来了解一些前置知识,它们就是『拓扑序列』和『拓扑排序』

最短路径

在之前的 普里姆算法和克鲁斯卡尔算法(最小生成树算法) 章节当中我们曾提到过,介绍这两个算法是为了我们接下来将要介绍的最短路径和关键路径做一些铺垫,那么今天我们就来正式的来了解一下什么是最短路径,以及它涉及到的两种算法『迪杰斯特拉算法(Dijkstra)』和『弗洛伊德算法(Floyd)』

普里姆算法和克鲁斯卡尔算法

本章我们来看两个关于图的算法,也算是为我们接下来将要介绍的 最短路径关键路径 做一些铺垫,它们分别是『普里姆算法』和『克鲁斯卡尔算法』,它们的目的都是生成『最小生成树』,它们两者的实现原理是比较相似的,只不过一个通过边,而另一个主要是通过顶点来实现的,下面我们就一个一个来进行介绍

图的遍历

在之前的章节当中,我们介绍了 图结构图的存储结构,所以可以得知 图的存储结构 主要有五种方式,有两种使用较多的『邻接矩阵』和『邻接表』,另外还有三种使用较少的『十字链表』,『邻接多重表』和『边集数组』,本章我们主要来看一下图的遍历

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×