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

本文介绍两种多边形（简单多边形）的顺逆时针顺序判断算法，其中一种算法就是通过计算多边行的面积(带符号)来判断。另一种方法是根据最左侧点前后边的转向(叉积)判断。有意思的是，网上有一些文章并没有就这种方法的特殊情况进行讨论。 Continue reading →

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

本文原来发布在cnblogs上，现在移动到我个人博客,并进行了一些修改。 Continue reading →

两线段（直线/射线）求交点是几何计算中的一个最基本的算法。虽然它大部分情况都不是影响程序效率的主要因素，但是它的执行次数可能非常的高，因此提升它的执行效率仍然具有价值。本文将分为两部分，一部分以geos为例，介绍主流的直线交点的判断与计算算法，另一部分给出我的实现，我相信它是一种更加简单和高效的算法，并且可以直接应用于更高的维度。 Continue reading →