自动摘要: 作为一个身在最底层的砖工，实践应该比原理更重要一些，所以先上代码，再说算法的原理。问题描述：最近在做人像美颜。一个子问题简而言之就是最近邻问题：一堆二维点中寻找一个与目标点最近(欧氏距离 ……..

作为一个身在最底层的砖工，实践应该比原理更重要一些，所以先上代码，再说算法的原理。

问题描述：

最近在做人像美颜。一个子问题简而言之就是最近邻问题：一堆二维点中寻找一个与目标点最近(欧氏距离最小)的点。

目前想出来这么几种思路：

最直接的方法：暴力遍历
建立KD树
使用opencv自带的Delaunay三角剖分
最前沿的进展可以看这个(写的挺好的，有更好的请教教我，一起学习一下)：

KDtree可以说是BST的升级版。这里有BST的代码：

还有一份不太鲁棒的KDtree代码：

这俩东西不是今天的重点。如果有更好的代码我也愿意一起学习哈。

因为工程中已经有了opencv库，所以一个简单直接的方法就是用opencv自带的算法。一开始我只是想做个伸手党，不过没找到现成的代码(找到一堆opencv2.x的)，所以看api写了个简单的demo。

环境: OS X, opencv3.4.2, cmake 3.10，Clion

// 先读取一张图像
    string src_img_path = "your_image_dir/JJY.jpg";
    Mat src_img = imread(src_img_path);
    if(src_img.empty()){
        cout << "empty img" << endl
        return -1;
    }
    auto img_height = src_img.size[0];
    auto img_width = src_img.size[1];
// 不能暴露我们的业务逻辑，所以这里搞一些均匀的点吧。
    vector<Point2f> pts_vec; // 存放每个点的坐标
    vector<int> pts_index_vec; // 假设每个点还有别的信息，都可以丢在这里，假设每个点还有个整数index吧
    //这个map用来存放Delaunay算法为每个点分配的index和原本的index之间的对应关系
    map<int, int> pt_id2pt_index; 
// 均匀画点
    int pt_index = 0;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++ ){
            pts_vec.emplace_back(img_width / 20.0 * i, img_height / 20.0 * j);
            pts_index_vec.emplace_back(pt_index);
            pt_index++;
        }
    }

把点画到图上

// opencv3.4.2 实现了这个算法，使用非常简单。官网的搜索功能太辣鸡，找了好久 // 初始化     CvRect rect = {0, 0, img_width, img_height};
    Subdiv2D sub_div;
    sub_div.initDelaunay(rect);
// 把坐标挨个塞进去     for(int i = 0; i < pts_vec.size(); i++) {
        int pt_id = sub_div.insert(pts_vec[i]); // 这里会返回一个自动分配的id         pt_index = pts_index_vec[i];
// 需要记住自动分配的id和坐标其他信息的对应关系         pt_id2pt_index.insert(std::pair<int, int>(pt_id, pt_index));
    }
// 假设我们需要找的点的坐标是(50, 50)， 实际可能是一个人脸关键     Point2f target = {50, 50};
// 自带最近邻搜索函数，返回最近邻的指针     auto vertex_ptr = sub_div.findNearest(target);
// 找到坐标     auto nearest_point_cord = sub_div.getVertex(vertex_ptr);

    cout << nearest_point_cord.x << endl;
    cout << nearest_point_cord.y << endl;
// 用刚才的map找到最近邻点的坐标     cout << pt_id2pt_index[vertex_ptr] << endl;

依次是x, y, 原本分配的index

画出来是这样，绿点是最近邻，红的是target

伸手党看到这里就可以关掉了。

算法原理

关于最近邻搜索算法的研究早在我出生之前就有了，2D面三角剖分也是非常经典了, 回顾一下：

1. 三角剖分和Delaunay剖分的定义

如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下：

1.1.三角剖分定义

【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：

1.除了端点，平面图中的边不包含点集中的任何点。

2.没有相交边。

3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。

1.2. Delaunay三角剖分的定义

在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起：

【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。

【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

1.3.Delaunay三角剖分的准则

要满足Delaunay三角剖分的定义，必须符合两个重要的准则：

1、空圆特性：Delaunay三角网是唯一的（任意四点不能共圆），在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示：

2、最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲，Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大。如下图所示：

1.4.Delaunay三角剖分的特性

以下是Delaunay剖分所具备的优异特性：

最接近：以最近邻的三点形成三角形，且各线段(三角形的边)皆不相交。
唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。

1.5.局部最优化处理

理论上为了构造Delaunay三角网，Lawson提出的局部优化过程LOP(Local Optimization Procedure)，一般三角网经过LOP处理，即可确保成为Delaunay三角网，其基本做法如下所示：

将两个具有共同边的三角形合成一个多边形。
以最大空圆准则作检查，看其第四个顶点是否在三角形的外接圆之内。
如果在，修正对角线即将对角线对调，即完成局部优化过程的处理。

LOP处理过程如下图所示：

2.Delaunay剖分的算法

Delaunay剖分是一种三角剖分的标准，实现它有多种算法。

2.1.Lawson算法

逐点插入的Lawson算法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，同时用Lawson设计的局部优化过程LOP进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。

上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，遇到非Delaunay边时，通过删除调整，可以构造形成新的Delaunay边。在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。

2.2.Bowyer-Watson算法

Lawson算法的基本步骤是：

构造一个超级三角形，包含所有散点，放入三角形链表。
将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
根据优化准则对局部新形成的三角形进行优化。将形成的三角形放入Delaunay三角形链表。
循环执行上述第2步，直到所有散点插入完毕。

这一算法的关键的第2步图示如下：

好吧。看到这里，说真的，如果不是经常搞这些理论，肯定没几天就忘了。算法工程师还是要找准自己的定位，谦虚谨慎才行。

其他参考：

落叶无痕

Delaunay三角剖分实践与原理