[算法] 已知在平面坐标系内有N个点，求离开给定坐标距离最近的4个点

最近在工作中碰到了这个问题：已知在平面坐标系内有N个点，求离开给定坐标距离最近的10个点。

团队的第一反应自然是按照两点间距离公式， 遍历N个已知点，然后排序获得前10个最短距离的结果。

 只是，我从来不是一个规规矩矩的人。我一直推崇用人类直觉思维来编程，而不要被僵化的程序思想束缚。

传统距离公式，计算N个点的距离需要2N次的减法和平方。

而事实上， 一个真正的人类，是不会把所有N个点的距离都计算一遍的。大多数点都会被某些快速条件过滤掉的。

今天先把问题在这里写下来， 有时间在把优化后的算法补充进来。

最差劲模式：
每次遍历已知点数组，逐个计算两点间距离，保留最小值以及索引信息。

时间复杂度 O(n)

缺点：每次查询都要重新遍历数组，效率低下。

优化模式1：

dic3提出的方式

预处理阶段，遍历所有已知点，得出一个初始化半径，以确保至少能有一个或多个点在半径内。

实际处理阶段：

用初始化半径，判断半径内的已知点。然后根据结果再次扩大或缩小半径。

缺点：严重的问题是，如何知道半径内的点都是谁？其实又要遍历所有点了。

优化模式2：网格预处理

预处理阶段，按已知坐标将所有点分配到二维数组内

实际处理阶段：

按目标坐标计算并获取核心下标，获得二维数组内的一个元素

判断这个网格内的所有点的距离并获取结果。

如果目标点在网格边缘，需要进一步增加相邻网格内的数据来判断。

缺点：

1、最差情况下要判断4个网格

2、当网格内元素数量持续增加时，算法效率同样下降明显。

时间复杂度 O(n/网格数量)

关于网格预处理哪位大哥可以说的更详细一点》？

8 个解决方案

#1

对于这个问题，使用nd-tree，便可极大地提供效率。

#2

上楼的能不能说详细一点？

#3

楼上说的可是K-D tree?

#4

http://blog.csdn.net/zhjchengfeng5/article/details/7855241

#5

引用 2 楼 zhongdugen 的回复:

上楼的能不能说详细一点？

yes!

#6

引用 3 楼 zhongdugen 的回复:

楼上说的可是K-D tree?

yes!!

#7

 private void button1_Click(object sender, EventArgs e)
        {
            ary = new List<Point>() { new Point(0, 0), new Point(0, 1), new Point(0, 2), new Point(0, 3), new Point(0, 4) };
            string a = "";

            ary.Sort(lstSort);
            ary.RemoveRange(ary.Count - n, n);
            foreach (var item in ary)
                a = a + item + ",";
           
            textBox1.Text = a;
        }
        /// <summary>
        /// 比较规则
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        int lstSort(Point a, Point b)
        {
            double lengthA = GetdeltaLength(a, currPoint);
            double lengthB = GetdeltaLength(b, currPoint);

            if (lengthA - lengthB < 0)
                return 1;
            if (lengthA - lengthB > 0)
                return -1;
            else
                return 0;
        }

        double GetdeltaLength(Point pointA, Point pointB)
        {
            double templength = Math.Pow(Math.Pow(pointA.X - pointB.X, 2) + Math.Pow(pointA.Y - pointB.Y, 2), 0.5f);

            return templength;
        }

#8

你可以先把N个坐标划分成很多小区域，然后把N个点按照所在的区域进行区分，  到时候看看给定的坐标在哪个区域，然后只在所在区域和周边的区域查找就行了，太远的区域不用找了。