首页
学习
活动
专区
工具
TVP
发布

每周学点大数据 | No.27高维外存查找结构——KD 树

今天我们要讲的二维空间内查找结构叫作KD 树,之所以讲它,是因为它的性质比较容易保证。 小可:那什么又是KD 树呢? Mr. 王:简单来说,KD 树很像是两个二叉树叠在一起。...那么水平线和垂直线也就相应地对应着KD 树的内部节点,而在二维平面上,我们要检索的这些就对应着KD 树的叶子节点。 小可带着疑惑的表情说:我还是不太明白。 Mr. 王:我们来举个例子吧。 ?...左边是一棵KD 树,右边是一个二维平面。下面我们分步演示它的过程。 ? 我们树根定义为一条水平线,在区域中画下它代表的水平线。 ? 下一层中的节点代表的是垂直线,我们在图中标示出这两条直线。 ?...为了查找树结构引入到磁盘上,我们引入了B 树。这次我们也可以发展KD 树,引入一种适合存储在硬盘上的数据结构——kdB 树。 小可:kdB 树是不是就是把KD 树和B 树融合到一起啊? Mr....然后分别在两个区域中,寻找x 轴的中位数,这样就又画出了第二级中的两条直线,也就得到了树的第二层中的两个节点的值。

1.4K80

线性代数--MIT18.06(一)

分别表示两条二维平面中的直线,如果这两条直线相交,那么交点的坐标 ? 即为方程组的解。...更确切的讲: 如果两条直线相交于一,那么该方程组有且仅有一个解,即为交点的坐标; 如果两条直线重合,那么说明这两条直线方程实际上是同一条直线,此时直线上的所有点的坐标均为方程组的解; 如果两条直线平行但不重合...,则说明不存在的坐标同时满足这两条直线的方程,此时方程组无解。...类似的,情形推广到三维,对于三元一次方程组 ? 从行的角度来看,三个三元一次方程表示三维空间中的三个平面,如果三个平面相交于一,那么交点的坐标即为方程组的解。...的一组基。此时对于任意的 ? 均可由 ? 的列向量线性表出,也即是 ? 一定有解。 换言之,如果 ? 可逆,则 ? 一定有解。

1K30
您找到你想要的搜索结果了吗?
是的
没有找到

线性代数的本质课程笔记-特征向量/特征值

前面介绍过,一个矩阵代表的是一种线性变换,考虑二维空间中的某个线性变换,它将i即[1,0]变换到[3,0]的位置,j即[0,1]变换到[1,2]的位置,那么对应的矩阵就是[3,1;0,2](先说一下写法...,两条位置不变的直线上的向量都可以称之为特征向量,而对应伸缩的大小,就称之为特征值。...回顾本系列视频第五讲的内容,当一个二维矩阵的行列式为0时,它能代表的线性变换能将空间压缩为一条直线或者是零。...以特征值2为例子,求解如下的方程组即可,你可以发现,一条直线上的所有向量都可以作为特征向量: 一般情况下,一个二维矩阵有两个特征值,而对应的特征向量在两条直线上,但也存在一些特殊情况。...因此,矩阵[2,-1;1,1]所代表的线性变换,可以理解为一组坐标系下某一个向量的坐标,转换到我们这组坐标系下的坐标,同样的,矩阵[2,-1;1,1]的逆代表一个向量在我们坐标系下的坐标,转换成另一个坐标系下的坐标

78620

「动画中的数学与物理基础」直线

在三维坐标系里表示 所谓的三维坐标,就是在二维的基础上,添加第三个坐标轴——Z轴而已。z轴的具体方向在哪,目前还没有统一的标准。目前有两个标准:左手系统和右手系统。...这3个值带入方程后,将会得到以下三个: (0,4)、(2,-1)、(4,2)。 3、在坐标系里画出这3个,并用线将它们连接起来如图所示: ?...如果两条直线相互垂直,那么m1*m2=-1 如果两条直线平行,那么他们的斜率是相等的。...如果同一平面的两条直线,其解的情况如下: 如果两条直线的斜率不相等,则仅有一组解 如果两条直线的斜率及在y轴上的截距分别相等,则有无穷组解 如果两条直线斜率相等,而在y轴上的截距不相等,则方程组无解 方程组的求解方法一般分为两种...如果发生碰撞,那么碰撞是多少? 解题思路: 消元法求解 1、是否会碰到墙上,我们需要确认两条直线的斜率,第一条直线为 -3/5,第二条直线为 -1/3,因此必相交。

1.3K30

「前端动画数学与物理基础」直线

00E9A666ADB269CB868CEDF0B68AC1F8.png 在三维坐标系里表示 所谓的三维坐标,就是在二维的基础上,添加第三个坐标轴——Z轴而已。...这3个值带入方程后,将会得到以下三个: (0,4)、(2,-1)、(4,2)。...如果两条直线相互垂直,那么m1*m2=-1 如果两条直线平行,那么他们的斜率是相等的。...如果同一平面的两条直线,其解的情况如下: 如果两条直线的斜率不相等,则仅有一组解 如果两条直线的斜率及在y轴上的截距分别相等,则有无穷组解 如果两条直线斜率相等,而在y轴上的截距不相等,则方程组无解 方程组的求解方法一般分为两种...如果发生碰撞,那么碰撞是多少? 解题思路: 消元法求解 1、是否会碰到墙上,我们需要确认两条直线的斜率,第一条直线为 -3/5,第二条直线为 -1/3,因此必相交。

97260

【笔记】《计算机图形学》(1&2)——导言与数学工具

有时我们需要从一个向量构造一组比较适合这个向量的标准正交基也就是一组相互垂直且模长为1的向量来构建坐标系。...二维直线的一般式 Ax+By+C=0 中,(a,b)到线的距离为: ?...重心坐标系的关键是利用三角形的边和顶点来定位坐标,如下图我们二维中可以用三角形的一a和两条边作为基描述中间蓝点p的坐标 ?...显然此时我们可以用下式描述p ? 然后这公式进行变形,可以得到更简洁的公式,从此我们可以用(β,γ)来描述一个的坐标 ?...第二种是几何法,运用前面说到的距离比值的特性,我们先按照点法式列出如下的方程,只有当x,y恰好在ab构成的直线上时值才会为0 ? 那么如果我们此时代入的不在线上,必然得到的函数值就是点到直线的距离。

1.8K42

干货 | 线性代数的本质课程笔记完整合集

该线性变换把原二维空间压缩成一条直线,行列式为0 上面的例子中,当二维空间经过一次线性变换被压缩成一条直线甚至是一个时,行列式为0,因此可以通过行列式是否为0来判断线性变换后的空间的维度是否与原空间相同...从投影的角度看,要求两个向量v和w的积,可以向量w朝着过原点的向量v所在的直线进行投影,然后w投影后的长度乘上向量v的长度(注意两个向量的的夹角)。 ? ?...总结一下,在刚才的线性变换中,有两条直线上的向量,在变换后仍在其所在的直线上,只不过长度和方向发生了改变,但其他的向量,都离开了它所张成的直线: ? ?...回顾本系列视频第五讲的内容,当一个二维矩阵的行列式为0时,它能代表的线性变换能将空间压缩为一条直线或者是零。...以特征值2为例子,求解如下的方程组即可,你可以发现,一条直线上的所有向量都可以作为特征向量: ? 一般情况下,一个二维矩阵有两个特征值,而对应的特征向量在两条直线上,但也存在一些特殊情况。

69850

万字长文|线性代数的本质课程笔记完整合集!

该线性变换把原二维空间压缩成一条直线,行列式为0 上面的例子中,当二维空间经过一次线性变换被压缩成一条直线甚至是一个时,行列式为0,因此可以通过行列式是否为0来判断线性变换后的空间的维度是否与原空间相同...从投影的角度看,要求两个向量v和w的积,可以向量w朝着过原点的向量v所在的直线进行投影,然后w投影后的长度乘上向量v的长度(注意两个向量的的夹角)。 ? ?...总结一下,在刚才的线性变换中,有两条直线上的向量,在变换后仍在其所在的直线上,只不过长度和方向发生了改变,但其他的向量,都离开了它所张成的直线: ? ?...回顾本系列视频第五讲的内容,当一个二维矩阵的行列式为0时,它能代表的线性变换能将空间压缩为一条直线或者是零。...以特征值2为例子,求解如下的方程组即可,你可以发现,一条直线上的所有向量都可以作为特征向量: ? 一般情况下,一个二维矩阵有两个特征值,而对应的特征向量在两条直线上,但也存在一些特殊情况。

69820

万字长文 | 线性代数的本质课程笔记完整合集!

该线性变换把原二维空间压缩成一条直线,行列式为0 上面的例子中,当二维空间经过一次线性变换被压缩成一条直线甚至是一个时,行列式为0,因此可以通过行列式是否为0来判断线性变换后的空间的维度是否与原空间相同...从投影的角度看,要求两个向量v和w的积,可以向量w朝着过原点的向量v所在的直线进行投影,然后w投影后的长度乘上向量v的长度(注意两个向量的的夹角)。 ? ?...总结一下,在刚才的线性变换中,有两条直线上的向量,在变换后仍在其所在的直线上,只不过长度和方向发生了改变,但其他的向量,都离开了它所张成的直线: ? ?...回顾本系列视频第五讲的内容,当一个二维矩阵的行列式为0时,它能代表的线性变换能将空间压缩为一条直线或者是零。...以特征值2为例子,求解如下的方程组即可,你可以发现,一条直线上的所有向量都可以作为特征向量: ? 一般情况下,一个二维矩阵有两个特征值,而对应的特征向量在两条直线上,但也存在一些特殊情况。

57220

线性代数的本质课程笔记完整合集

该线性变换把原二维空间压缩成一条直线,行列式为0 上面的例子中,当二维空间经过一次线性变换被压缩成一条直线甚至是一个时,行列式为0,因此可以通过行列式是否为0来判断线性变换后的空间的维度是否与原空间相同...从投影的角度看,要求两个向量v和w的积,可以向量w朝着过原点的向量v所在的直线进行投影,然后w投影后的长度乘上向量v的长度(注意两个向量的的夹角)。 ? ?...总结一下,在刚才的线性变换中,有两条直线上的向量,在变换后仍在其所在的直线上,只不过长度和方向发生了改变,但其他的向量,都离开了它所张成的直线: ? ?...回顾本系列视频第五讲的内容,当一个二维矩阵的行列式为0时,它能代表的线性变换能将空间压缩为一条直线或者是零。...以特征值2为例子,求解如下的方程组即可,你可以发现,一条直线上的所有向量都可以作为特征向量: ? 一般情况下,一个二维矩阵有两个特征值,而对应的特征向量在两条直线上,但也存在一些特殊情况。

1.1K21

学习「线性代数」看哪篇?推荐这篇,超级棒!

该线性变换把原二维空间压缩成一条直线,行列式为0 上面的例子中,当二维空间经过一次线性变换被压缩成一条直线甚至是一个时,行列式为0,因此可以通过行列式是否为0来判断线性变换后的空间的维度是否与原空间相同...从投影的角度看,要求两个向量v和w的积,可以向量w朝着过原点的向量v所在的直线进行投影,然后w投影后的长度乘上向量v的长度(注意两个向量的的夹角)。 ? ?...总结一下,在刚才的线性变换中,有两条直线上的向量,在变换后仍在其所在的直线上,只不过长度和方向发生了改变,但其他的向量,都离开了它所张成的直线: ? ?...当一个二维矩阵的行列式为0时,它能代表的线性变换能将空间压缩为一条直线或者是零。因此,想让v经过(A-λI)变换后的结果为零向量,(A-λI)的行列式值必须为0,所以整个过程如下: ?...以特征值2为例子,求解如下的方程组即可,你可以发现,一条直线上的所有向量都可以作为特征向量: ? 一般情况下,一个二维矩阵有两个特征值,而对应的特征向量在两条直线上,但也存在一些特殊情况。

77520

使用Matlab计算两条线的交点及三角形垂心

Matlab版本:R2016A 操作系统:Win-8 为了让整个流程比较完整, 1、我用了12个,每两个一条线,能组成6条线; 2、每两条线相交于一,一共有3个; 3、3个构成了三角形的三个顶点...,每个的橫坐标放在一个数组里,纵坐标放在一个数组里,然后进行绘制: X = [294.94, 668.61, 1678.70, 1731.25, 540.16, 1731.25, 335.80, 1696.22...2、下面计算每两条线之间的交点(即上图所示的1,2一组,3,4一组,5,6一组计算其交点) 两条直线相交,必然需要求出两条直线的表达式,每条直线的表达式可以用 y = ax + b来表示,下面用...) = fzero(fun, 2); points(i, 2) = a(2*i) * points(i, 1) + b(2*i, 1); end 得到直线交点如图所示: 3、三个连线绘制...两个的横坐标一个选择很小,一个选择很大,这样可以保证画出来的直线足够长,方便观察(这个方法似乎有些简单粗暴~~~~~~~~,不过还是能够绘制出来的) % 设置预绘制直线的两个端点的X值 verticalLinePoints

46520

编程求取直线一般式表达式,两直线交点

背景介绍   最近在水面无人艇(USV)模拟仿真中,用到了一些和线的关系求解,本文主要讲述一下两确认直线,点到直线距离,两条直线的交点等问题的解决方法,并给出python程序。...博客更新可参见github点线关系 两确定直线 表达式定义   空间直线的表达式有多种,比如一般式Ax+By+C=0、斜式y-y0=k(x-x0)、截距式x/a+y/b=1、两式:(y-y1)/(...由上可以看出来,一般式的适用范围最广,不需要单独做处理和判断,所以在计算机领域处理二维图像数据中一般式用的最多。   ...两条直线的交点 表达式定义 ?   在已知直线的情况下,利用上面的直线一般式可以求得直线的参数A、B和C,那么两条直线的一般式表达可以列成二元一次方程组,其解即为两条直线的交点坐标。...注意处理两条直线平行的特殊情况。 ?

4.6K70

支持向量机

而这两条平行虚线正中间的分界线就是在保持当前决策面方向不变的前提下的最优决策面。 两条虚线之间的垂直距离就是这个最优决策面对应的分类间隔。...(1)"决策面"方程 我们都知道二维空间下一条直线的方式如下所示: 现在我们做个小小的改变,让原来的x轴变成x1,y轴变成x2 移项得: 公式向量化得: 进一步向量化,用w列向量和x列向量和标量...二维空间的直线方程已经推导完成,将其推广到n维空间,就变成了超平面方程。...我们高中都学过,点到直线的距离距离公式如下: 公式中的直线方程为Ax0+By0+C=0,P的坐标为(x0,y0)。...现在,直线方程扩展到多维,求得我们现在的超平面方程,对公式进行如下变形: 这个d就是"分类间隔"。其中||w||表示w的二范数,求所有元素的平方和,然后再开方。

56710

C++ OpenCV透视变换改进---直线拟合的应用

微卡智享 void cv::fitLine( cv::InputArray points, // 二维的数组或vector cv::OutputArray line, // 输出直线...,可以是二维的cv::Mat数组,也可以是二维的STL vector。...line: 输出的直线,对于二维直线而言类型为cv::Vec4f,对于三维直线类型则是cv::Vec6f,输出参数的前半部分给出的是直线的方向,而后半部分给出的是直线上的一(即通常所说的斜式直线)。...微卡智享 # 步骤 1 旋转矩形的和上一步获取的最近设置一个阈值距离,在距离内的都列入当前区域的直线拟合,超过阈值的用最近加上阈值重新算为计算点来进行拟合 2 根据不同区域计算直线拟合 3 求到的直线拟合实现每两条求交点...03 每两条直线拟合求交点 ? 直线拟合的函数,输出的参数line里面有说到了是Vec4f的类型,输出参数的前半部分给出的是直线的方向,而后半部分给出的是直线上的一(即通常所说的斜式直线)。

1.3K10

总结 | 相机标定的基本原理与改进方法

n代表n张图片,m代表每张图片上有m个角。 可以三维空间中的都投影到二维空间的对应点m^处,在二维平面上通过角提取算法可以提取出对应角 ? 。...通过选择合适的内外参数来使得目标函数达到最小,一组内外参数作为实际求得的内外参数。 提出问题:为什么张正友没有使用这样一种简单直观的方式?...棋盘格检测精度低,可能是因为实际的棋盘格标定板的边缘存在过渡带,不是直接的由白瞬间变黑,但不存在偏心误差,这是由于空间中两条相交直线的交点,投影到二维图像上仍然是这两条投影直线的交点,故棋盘格检测不存在偏心误差...(3)标定结果的评判标准 重投影误差Re-projection error 用目标函数,三维物投影至二维图像中与二维图像中提取出的对应角坐标做某种差值计算(目标函数)求和。...②双目测量 用两个相机拍摄的图片中可以恢复三维信息,这是由于二维图片中的一对应于三维空间中的一条射线,由两条射线的交点可以确定这个点在三维空间中的位置。

2.2K20

支持向量机1--线性SVM用于分类原理

给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。...如果数据空间本身是三维的,则其超平面是二维平面,而如果数据空间本身是二维的,则其超平面是一维的直线。 边际(margin)越大越好 二维平面内有两类数据点,实心圆与空心菱形表示。...---- 间隔最大化的理解 决策边界的两边要有两个超平面,这两个超平面在二维空间中就是两条平行线(即图中虚线超平面),而他们之间的距离就是我们的边际 。...两条虚线表示的超平面,是数据边缘所在的。...这条直线是由 平移得到,所以两条直线在纵坐标上的差异就是 (竖直的黑色箭头)。而 点到 的距离就可以表示为 ,即 在 方向上的投影。

1.5K40

霍夫变换

空间变换一个空间中具有相同形状的曲线或直线映射到另一空间的一个上形成峰值。 下述内容转载自《霍夫变换Hough》 霍夫变换(Hough)是一个非常重要的检测间断点边界形状的方法。...它通过图像坐标空间变换到参数空间,来实现直线与曲线的拟合。...具体计算时,可以参数空间视为离散的。建立一个二维累加数组A(a,b),第一维的范围是图像坐标空间中直线斜率的可能范围,第二维的范围是图像坐标空间中直线截矩的可能范围。...与直角坐标不同的是,用极坐标表示时,图像坐标空间的共线的两(xi,yi)和(xj,yj)映射到参数空间是两条正弦曲线,相交于(ρ0 ,θ0),如上图所示。...默认值为20.θ和ρ θ和ρ)的两条线段之间的距离小于 FillGap,则合并为一个直线段。默认值为20.

1.6K30

主成分分析到底怎么分析?

则在二维平面上A和B可以用两条发自原点的有向线段表示,见下图: ? 好,现在我们从A向B所在直线引一条垂线。...不难证明所有二维向量都可以表示为这样的线性组合。此处(1,0)和(0,1)叫做二维空间中的一组基。 ? 所以,要准确描述向量,首先要确定一组基,然后给出在基所在的各个直线上的投影值,就可以了。...但实际上任何两个线性无关的二维向量都可以成为一组基,所谓线性无关在二维平面内可以直观认为是两个不在一条直线上的向量。 例如,(1,1)和(-1,1)也可以成为一组基。...通过上一节对基变换的讨论我们知道,这个问题实际上是要在二维平面中选择一个方向,所有数据都投影到这个方向所在直线上,用投影值表示原始记录。这是一个实际的二维降到一维的问题。...以上图为例,可以看出如果向x轴投影,那么最左边的两个会重叠在一起,中间的两个也会重叠在一起,于是本身四个各不相同的二维投影后只剩下两个不同的值了,这是一种严重的信息丢失,同理,如果向y轴投影最上面的两个和分布在

1.2K101

降维方法(一):PCA原理

则在二维平面上A和B可以用两条发自原点的有向线段表示,见下图: ? 好,现在我们从A向B所在直线引一条垂线。...不难证明所有二维向量都可以表示为这样的线性组合。此处(1,0)和(0,1)叫做二维空间中的一组基。 ? 所以,要准确描述向量,首先要确定一组基,然后给出在基所在的各个直线上的投影值,就可以了。...但实际上任何两个线性无关的二维向量都可以成为一组基,所谓线性无关在二维平面内可以直观认为是两个不在一条直线上的向量。 例如,(1,1)和(-1,1)也可以成为一组基。...通过上一节对基变换的讨论我们知道,这个问题实际上是要在二维平面中选择一个方向,所有数据都投影到这个方向所在直线上,用投影值表示原始记录。这是一个实际的二维降到一维的问题。...以上图为例,可以看出如果向x轴投影,那么最左边的两个会重叠在一起,中间的两个也会重叠在一起,于是本身四个各不相同的二维投影后只剩下两个不同的值了,这是一种严重的信息丢失,同理,如果向y轴投影最上面的两个和分布在

1.3K90
领券