About whudj

computational geometry

web服务器的迁移

因之前使用的云服务器的期限将近,不打算继续使用,所以购买了新的服务器实例,需要将博客网站迁移到新的实例上。本文作为网站迁移的记录。因为我对网站开发的专业知识较为欠缺,所以本文并非专业的实践。

主要内容包括wordpress以及mysql数据库的中的记录导出;在新的服务器上部署安装nginx,php,mysql等软件并且进行配置;将数据导入新的服务器几个部分。

Continue reading

google的软件工程实践

本文对谷歌资深工程师Fergus Henderson发表的论文《Software Engineering at Google》进行了翻译。论文的主要内容是从软件开发、项目管理、人事管理等三个方面介绍谷歌的软件工程实践方法,文章不仅从“道”,“法”方面介绍谷歌多年沉淀出的软件工程理念,而且详细的说明“术”,“器”即谷歌构建的具体流程与工具。本文从多个层面具备参考价值。 Continue reading

点在多边形内判断(point in polygon)

给定2D平面上点\(c(x,y)\)确定其是否在多边形p内部,是比较常见的几何查询问题之一。本文的内容是阐述射线法(Ray Casting Algorithm)求解普通多边形(simple polygon) PIP(point in polygon)问题的思路与实现。目前网上类似文章不少,但是其中部分文章缺乏对特殊情况的讨论,在应用时容易在特例数据上失败。 Continue reading

高斯-牛顿法(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算法)等非线性最小二乘问题解法起到引出作用。

Continue reading

KD树的主要算法以及FLANN(PCL)的实现分析

kd树可能是我们最熟悉的空间索引。kd树的全称是k-dimensional tree,顾名思义,是一种将多维数据组织起来的数据结构。不仅服务于计算几何领域,而且在统计分析、机器学习领域都是非常活跃的。本文将主要围绕kd树的结构、构建、半径搜索(范围搜索)、最近邻搜索(KNN)等主要的算法进行展开,同时也会涉及到近似最近邻与最近邻算法的区别,spliting 策略等有趣的细节。并且,我还会介绍部分FLANN库(被PCL使用)对上述算法的实现方式。在文章末尾,提供了c++实现代码。 Continue reading

C++编码规范

近期,在小组内做了一期关于编码规范的小培训,将编写的编码规范文件分享与下文。组内成员有不同的背景和风格,因此几个工程的编码风格迥异,不乏有一些不规范,有风险的地方。目前网上流行的编码规范一般大而全,考虑到不影响现有工作进行,循序渐进的改进方法,我尽量选择了重要的条目,并且进行了分级。结合组内实际情况,突出了一些常见问题。

Continue reading

叠置算法(4):算法-拓扑面标记算法

叠置分析的核心任务是解决由多个图层生成的新数据中,每个新生成的对象是由哪些输入对象“叠置”生成出来的问题。即所谓的对象标记。栅格叠置分析的标记非常简单,矢量对象的对象标记算法相对来说就要复杂很多。接上文,当输入要素建立了对象模型与拓扑模型的关联,构建拓扑模型后,本文介绍一种拓扑面标记算法,以解决叠置分析结果的标记问题。 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交模型的原理以及常见的拓扑关系描述符。

Continue reading

B-Spline(11):样条曲线拟合-光顺逼近

曲线拟合包含两个方面,插值(interpolation)和逼近(approximation)。用于曲线拟合的离散点通常不具有非常高的精度,直接插值得到的曲线可能不满足“光顺(fair)”要求,本节的目标是介绍光顺的定义,以及给出一种满足“光顺”要求的最小二乘逼近方法。 Continue reading

windows下gdal python安装与使用

我日常的编程语言是C++,看到周边的同事有学习python,围观了几个小例子,感觉python很不错,用起来很方便。所以我打算利用业余时间学习一些python的知识,如果学会了用GPIO 库控制我的树莓派做一些好玩的事情最好了。这篇文章里。我打算分享一下gdal python库的安装与pycharm下编写一个读取shapefile小程序的过程。 Continue reading

B-Spline(八):节点插入

节点插入的含义是在不改变曲线形状的前提下,向节点序列(knot vector)中插入节点。节点插入的出发点与Bezier曲线的升阶一样,都是想增加控指点的数量以增加曲线的自由度。在不考虑改变曲线阶次的情况下,根据 m=p+n+1的等式,节点数加一,控制点数量加一。 Continue reading

B-Spline(四):基函数计算

与Bezier曲线一样,B样条对于给定参数u求曲线上点的算法都不是通过计算基函数的值后带入控制点坐标计算的,而是通过de Boor算法计算,但是在曲线内插、拟合、优化等后续话题中,都需要带入基函数的值。因此本节的目标是介绍给定任意参数u,计算一组\(N_{i,p}(u)\)值的算法。 Continue reading