最近点到点，最近点到线

Question

想象一下2D平面上的一组m点，称为“候选点”。然后有两种情况之一：

• 还有一组n点(“对象”)-参见图1。
• 还有一组与X或Y轴(“对象”)共线的n线-见图2。

我想知道哪一对候选对象的笛卡儿距离最短。

请问，有没有人知道这个问题在计算几何学中有名字？有比O(m*n)更快的算法吗？如果对象保持不变，并且只有候选对象发生变化，那么通过一些巧妙的预计算，是否有可能比O(m*n)更快呢？

图1

              c      o
       c
                          o         c      o
           o    c
                             c
              c o              
                       c             o
                                          c
               o                 c
          c

图2

             |                      c           |  
-------------+----------------------------------+------  
             |                                  |  
             |              c                   |    c  
             c                                  |  
             |                                  |  
-------------+----------------------------------+------  
             |          c            c          |  
-------------+----------------------------------+------  
             |                            c     |  

Answer 1

这基本上是对你所有候选人的近邻搜索。您可以使用kd树索引加速这些类型的问题。

Answer 2

我不明白你怎么从物体上创建线条。为每一个对象创建两条线:一条是垂直的，一条是水平的，是吗？

在任何情况下，假设您有垂直线v1、v2、.、va和水平线h1、h2、.、hb。

根据垂直线的x轴偏移和水平线的y轴偏移对垂直线进行排序。

对于候选集中的每个点，进行二进制搜索，得到最近的垂直和水平线。现在，如何计算最接近的一对(候选，行)是非常简单的。

Answer 3

您要查找的名称很可能是NNS (请参见：搜索)，而且是的，如果为静态“对象”集预计算提供一定的时间和空间，则应该可以比O(n*m)更快地执行搜索。

即使使用构建二进制搜索树的最简单方法，您也应该能够将单个查找的时间复杂度降低到O(log )，从而导致整个问题的O( most )。