首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    关于包围,你需要知道的那些事

    本文将讲讲解二维中的包围。 三维的包围是一脉相承的,理解了二维也就懂了三维。 包围(bbox, bounding box)指的是包围图形的一个矩形。...这个 AABB 刚好紧密包裹住椭圆,所以这个包围同时也是 MBR(最小外接矩形)。...AABB 并不要求紧密包裹图形,所以并不是一定是最小外接矩形(MBR)。 对此,如果想提高 AABB 的精度,可以用几何算法去求 MBR 作为图形的 AABB。...但涉及到平面几何,不同图形的算法不一样。像是椭圆大概要用到蒙日圆,多边形则求变换后顶点的坐标值的最大最小 x y 值。...此时我们需要的是上图这种包围多边形,勉强叫做有 transform 的 box 吧。 因为是线性形变,包围多边形是平行四边形,依旧是凸多边形,所以还是可以分离轴定理 算法来计算碰撞。

    36110

    计算空间物体包围球的两种算法实现

    概述 在进行二维空间几何运算的之前,往往会用包围进行快速碰撞检测,从而筛掉一些无法碰撞到的可能。而在三维中,比较常用的就是包围球了。当然,如何计算包围球是一个问题。 2....详论 2.1. naive算法 一个最简单的思路就是,计算空间顶点在X、Y、Z方向上的最大值和最小值,那么就可以得到8个顶点组成的包围。...取包围球中心为包围盒中心点,而包围球半径有的人认为可以取中心点到八个顶点的最大距离——这样其实并不严密。...如下图所示: 如果点P在我们的之前得到的包围球之外,那么延长点P与球心O的直线与球相较于T点,很显然,新的直径应该是点T与点P的一半: 图片 具体的算法代码实现: void BoundingSphere...其他 理论上来说,ritter算法的实现要优于naive算法,能够得到更加贴合的包围球。当然理论只是理论,具体的实现还要看最终的效果。

    75620

    粗略的物体碰撞预测及检测

    二维场景中的AABB包围具备特点(下图中的所有坐标系均采用右手直角坐标系): 表现形式为四边形,即用四边形包围物体。 四边形的每一条边,都会与坐标系的轴垂直。 ?   ...三维场景中的AABB包围特点: 表现形式为六面体。 六面体中的每条边都平行于一个坐标平。 ?   ...其中,为了更明显的展示AABB包围的特点,在最右侧展示了一个OBB(Oriented Bounding Box)包围,也称作有向包围。...AABB包围与OBB包围的最直接的区别就是,AABB包围是不可以旋转的,而OBB包围是可以旋转的,也就是有向的。   ...三维物体的AABB包围的八个顶点依旧可以用两个顶点来标识,如下图所示。 ? 球体碰撞预测及检测   球体是碰撞检测中最简单的数学模型,我们只需要直到两个球体的球心和半径就可以进行检测。

    2.8K81

    粗略的物体碰撞预测及检测

    二维场景中的AABB包围具备特点(下图中的所有坐标系均采用右手直角坐标系): 表现形式为四边形,即用四边形包围物体。 四边形的每一条边,都会与坐标系的轴垂直。...[44012494.jpg]   三维场景中的AABB包围特点: 表现形式为六面体。 六面体中的每条边都平行于一个坐标平。...[31070002.jpg]   其中,为了更明显的展示AABB包围的特点,在最右侧展示了一个OBB(Oriented Bounding Box)包围,也称作有向包围。...AABB包围与OBB包围的最直接的区别就是,AABB包围是不可以旋转的,而OBB包围是可以旋转的,也就是有向的。   ...三维物体的AABB包围的八个顶点依旧可以用两个顶点来标识,如下图所示。

    1.9K60

    图形遍历效率低?试试 R 树

    为实现这个能力,我们计算图形树上的每个图形的包围:一个用 minX,minY、maxX、maxY 表达的一个矩形,它刚好包围住图形。...包围的作用是简化碰撞算法,一些复杂的图形,比如贝塞尔曲线,如果要严格意义上判断碰撞,是要进行复杂的计算的,在有大量图形的场景下,性能非常糟糕。...所以业内常用矩形包围的碰撞来简化,这种算法非常简单高效,可直接用来替代原本复杂精细的碰撞检测,或是在进行复杂碰撞算法前先做一层过滤,避免无谓的复杂运算。...和其他索引树类似,R 树的叶子节点是数据节点,保存有图形信息和它的最小包围矩形(MBR)。 最小包围矩形其实就是包围。...为此,我们需在每次图形物理属性改变的时候,重新计算包围,并更新 R 树。

    30610

    Canvas 性能优化:脏矩形渲染

    脏矩形:改变某个图形的物理信息后,需要重新渲染的矩形区域,通常为目标图形的当前帧和下一帧组成的包围包围包围图形的最小矩形。通常用作低成本的碰撞检测。...脏矩形渲染简单来说,就是计算被改变的目标图形两帧所产生的包围(脏矩形),将该区域清空,然后将和脏矩形发生相交的所有图形在这个区域内重绘。...对于前面移动红球的场景,具体逻辑为: 计算红球在当前帧和下一帧所形成的包围,这个包围就是脏矩形; 遍历绿球的物理信息,计算它们的包围,取出和脏矩形发生相交的绿球; 将脏矩形区域清空; 将脏矩形设置为裁剪区域...这个算法用于两帧红球形成的包围,也就是脏矩形。...以及计算绿球的包围

    1.3K10

    随机增量算法 - 最小圆覆盖

    文章整理自网络 简介 随机增量算法是计算几何的一个重要算法,它对理论知识要求不高,算法时间复杂度低,应用范围广大。...最小圆覆盖问题 题意描述 在一个平面上有n个点,求一个半径最小的圆,能覆盖所有的点。 算法 假设圆O是前i-1个点得最小覆盖圆,加入第i个点,如果在圆内或边上则什么也不做。...(因为最多需要三个点来确定这个最小覆盖圆,所以重复三次) 遍历完所有点之后,所得到的圆就是覆盖所有点的最小圆。...,则p一定在SU{p}的最小覆盖圆上。...令前i-1个点的最小覆盖圆为C 如果第i个点在C内,则前i个点的最小覆盖圆也是C 如果不在,那么第i个点一定在前i个点的最小覆盖圆上,接着确定前i-1个点中还有哪两个在最小覆盖圆上。

    1.8K30

    最小生成树(Kruskal算法和Prim算法

    而今天我们要说一个非常实用的算法——最小生成树的建立!这是图论中一个经典问题,可以使用Kruskal和Prim两种算法来进行实现!...在实际中,这种算法的应用非常广泛,比如我们需要在n个城市铺设电缆,则需要n-1条通信线路,那么我们如何铺设可以使得电缆最短呢?最小生成树就是为了解决这个问题而诞生的! ?...最小生成树 如上图所示,一幅两两相连的图中,找到一个子图,连接到所有的节点,并且连接边的权重最小(也就是说边的数量也是最小的,这也保证了其是树结构). 2 Kruskal算法(克鲁斯卡算法) Kruskal...算法是一种贪心算法,我们将图中的每个edge按照权重大小进行排序,每次从边集中取出权重最小且两个顶点都不在同一个集合的边加入生成树中!...4 资源分享 以上完整代码文件(C++版),文件名为:最小生成树(Kruskal算法和Prim算法).cpp,请关注我的个人公众号 (算法工程师之路),回复"左神算法基础CPP"即可获得,并实时更新!

    5K30

    最小生成树算法:Kruskal 与 Prim算法

    贪心算法不是对所有的问题都能得到整体最优解(也就是说这两种算法不是万能的)。 并且 最小生成树是不唯一的!...Ⅱ、Kruskal算法 任给一个有 n 个顶点的连通网络 N={V,E}, 首先构造一个由这 n 个顶点组成、不含任何边的图 G={V,NULL},其中每个顶点自成一个连通分量, 其次不断从 E 中取出权值最小的一条边...除了 Kruskal 算法以外,普里姆算法(Prim 算法)也是常用的最小生成树算法。...prim 算法的核心信仰是:从已知扩散寻找最小。它的实现方式和 Dijkstra算法相似但稍微有所区别,Dijkstra 是求单源最短路径。而每计算一个点需要对这个点从新更新距离。...总的来说,Prim 算法是 以点为对象,挑选与点相连的最短边来构成最小生成树。而 Kruskal 算法是以边为对象,不断地加入新的不构成环路的最短边来构成最小生成树。

    2K20

    最小生成树(Prim算法和Kruskal算法算法详解)

    前言 在数据结构与算法的图论中,(生成)最小生成树算法是一种常用并且和生活贴切比较近的一种算法。但是可能很多人对概念不是很清楚。...最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。 通俗易懂的讲就是最小生成树包含原图的所有节点而只用最少的边和最小的权值距离。...从定义上分析,最小生成树其实是一种可以看作是树的结构。而最小生成树的结构来源于图(尤其是有环情况)。通过这个图我们使用某种算法形成最小生成树的算法就可以叫做最小生成树算法。...具体实现上有两种实现方法、策略分别为kruskal算法和prim算法。 学习最小生成树实现算法之前我们要先搞清最小生成树的结构和意义所在。咱么首先根据一些图更好的祝你理解。...此时被选择的边构成最小生成树。 ? 在这里插入图片描述 ? 在这里插入图片描述 Prim算法 除了Kruskal算法以外,普里姆算法(Prim算法)也是常用的最小生成树算法。虽然在效率上差不多。

    3.8K20
    领券