给定2D平面上点\(c(x,y)\)确定其是否在多边形p内部,是比较常见的几何查询问题之一。本文的内容是阐述射线法(Ray Casting Algorithm)求解普通多边形(simple polygon) PIP(point in polygon)问题的思路与实现。目前网上类似文章不少,但是其中部分文章缺乏对特殊情况的讨论,在应用时容易在特例数据上失败。 Continue reading
Yearly Archives: 2018
高斯-牛顿法(Guass-Newton Algorithm)与莱文贝格-马夸特方法(Levenberg–Marquardt algorithm)求解非线性最小二乘问题
众所周知,最小二乘法通过最小化误差平方和获得最佳函数。有时候你可能产生疑问,为什么不能通过其他方式获得最优函数,比如说最小化误差的绝对值的和?本文中,我将会从概率的角度解释最小二乘法的依据(参考自andrew ng 《机器学习课程》 第三讲)。最小二乘问题可以分为线性最小二乘和非线性最小二乘两类,本文的目标是介绍两种经典的最小二乘问题解法:高斯牛顿法与莱文贝格-马夸特方法。实际上,后者是对前者以及梯度下降法的综合。 Continue reading
梯度下降法(gradient descent)与牛顿法(newton’s method)求解最小值
梯度下降法与牛顿法是求解最小值/优化问题的两种经典算法。本文的目标是介绍两种算法的推导思路与流程,并且从初学者的角度就一些容易混淆的话题如 梯度下降法(gradient descent)与最速下降法(steepest descent)的联系与区别、牛顿求根迭代方法(Newton–Raphson method) 与牛顿法求解最小值算法的联系(来自 Andrew Ng 机器学习课程第四讲)进行说明。本文的内容将对高斯牛顿法(Gauss–Newton algorithm) ,Levenberg-Marquardt算法(LM算法)等非线性最小二乘问题解法起到引出作用。
叠置算法(5):拓扑构建算法
拓扑(topology)是由DCEL构成的一种平面镶嵌数据结构。拓扑数据结构将平面划分为若干相互邻接且不压盖的拓扑面。在拓扑结构上实施的标记算法是叠置算法的核心(第四节)。这一节,我将介绍拓扑构建算法。 Continue reading
多边形面积以及顺逆时针顺序判断
本文介绍两种多边形(简单多边形)的顺逆时针顺序判断算法,其中一种算法就是通过计算多边行的面积(带符号)来判断。另一种方法是根据最左侧点前后边的转向(叉积)判断。有意思的是,网上有一些文章并没有就这种方法的特殊情况进行讨论。 Continue reading
KD树的主要算法以及FLANN(PCL)的实现分析
kd树可能是我们最熟悉的空间索引。kd树的全称是k-dimensional tree,顾名思义,是一种将多维数据组织起来的数据结构。不仅服务于计算几何领域,而且在统计分析、机器学习领域都是非常活跃的。本文将主要围绕kd树的结构、构建、半径搜索(范围搜索)、最近邻搜索(KNN)等主要的算法进行展开,同时也会涉及到近似最近邻与最近邻算法的区别,spliting 策略等有趣的细节。并且,我还会介绍部分FLANN库(被PCL使用)对上述算法的实现方式。在文章末尾,提供了c++实现代码。 Continue reading
3D Hough变换点云平面检测算法
本文的主要目标:1.介绍3D Hough Transform的应用场景,算法思路,算法步骤以及代码。2.对其应用场景进行更进一步分析,与相似用途的算法(RandSAC)进行比较,分析优缺点。 Continue reading
C++编码规范
近期,在小组内做了一期关于编码规范的小培训,将编写的编码规范文件分享与下文。组内成员有不同的背景和风格,因此几个工程的编码风格迥异,不乏有一些不规范,有风险的地方。目前网上流行的编码规范一般大而全,考虑到不影响现有工作进行,循序渐进的改进方法,我尽量选择了重要的条目,并且进行了分级。结合组内实际情况,突出了一些常见问题。
叠置算法(4):算法-拓扑面标记算法
叠置分析的核心任务是解决由多个图层生成的新数据中,每个新生成的对象是由哪些输入对象“叠置”生成出来的问题。即所谓的对象标记。栅格叠置分析的标记非常简单,矢量对象的对象标记算法相对来说就要复杂很多。接上文,当输入要素建立了对象模型与拓扑模型的关联,构建拓扑模型后,本文介绍一种拓扑面标记算法,以解决叠置分析结果的标记问题。 Continue reading
地图投影:高斯克吕格投影
地图投影是GIS领域中非常常见的概念。说到高斯克吕格投影,很多同学都耳熟能详,因为它是我国大中基本比例尺地形图使用的地图投影。但是如果涉及到高斯投影的具体性质,有人会犯迷糊了。所以,我将高斯克吕格投影的相关内容整理如下。 Continue reading
叠置分析(3):算法-对象模型到拓扑模型的关联
主流的GIS应用与spatial database 均采用了对象模型,一个空间要素包含几何与属性两部分,并不保存对象之间的拓扑关系。基于种种考虑,拓扑模型已经不常用,拓扑关系的生成转变为由实时计算生成。拓扑关系计算的核心是9交叉模型,本文的主要目的是揭示对象模型(以多边形为例)到拓扑模型的关联过程。并且结合 geos与ArcGIS中相应的内容予以说明。 Continue reading
叠置分析(2):数据结构:topology模型/DCEL
这一节我计划介绍叠置分析算法的基础-数据结构,即拓扑(topology)数据模型,在不同的领域/软件中,对拓扑数据模型的实现有不一样的叫法,比如geos中称之为planargraph(平面图)或者geomgraph,计算几何(Computational Geometry)的书籍以及CGAL中将其称为DCEL(Double Connected Edge List),ArcGIS早期的数据模型称之为Coverage。拓扑数据模型是一种用GeoRelational模型,即显式的表达了空间关系,叠置算法就是建立在这种数据模型之上的。 Continue reading
叠置分析(spatial overlay analysis)的应用
空间分析可以说是GIS系统的最重要的功能了。在若干种空间分析操作中,我们最常用的就是叠置分析(overlay analysis ,下文称overlay)。乃至于在《GIS Primer》中,overlay被称为任何GIS软件系统的基本必备功能。同时,任何软件也将空间分析定义为核心功能,其主要的难点在于数据量以及效率。这一节里,我们抛开具体的实现不谈,先请你了解一下overlay有哪些应用。 Continue reading
空间拓扑关系描述:9交叉模型(DE-9IM)
空间关系描述是GIS系统的基本功能之一。我在学校学习到的空间关系分为三种:方位关系、距离关系、拓扑关系。今天我要分享的拓扑关系的标准化描述:9交叉模型。科班出身的GISer可能都知道9交模型是Egenhofer在《point set topological spatial relations》中提出的,不过,我今天不打算综述空间关系有关的理论发展,而是结合geos,分享9交模型的原理以及常见的拓扑关系描述符。