给定2D平面上点\(c(x,y)\)确定其是否在多边形p内部，是比较常见的几何查询问题之一。本文的内容是阐述射线法(Ray Casting Algorithm)求解普通多边形(simple polygon) PIP(point in polygon)问题的思路与实现。目前网上类似文章不少，但是其中部分文章缺乏对特殊情况的讨论，在应用时容易在特例数据上失败。 Continue reading
点在多边形内判断(point in polygon)
1
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交模型的原理以及常见的拓扑关系描述符。