最近点对问题，点到直线的最近距离问题

Question

在二维平面上有一组包含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     |  

- Ecir Hana

---

两个对象或线条能否与同一个候选项匹配？ - Corey Ogburn

另外，您是否真的关心对象与其候选对象之间的距离，还是只关心它们是否配对？ - Corey Ogburn

听起来很适合使用k-d树。 - Special Touch

@CoreyOgburn：关于您的第一个问题：是的，关于第二个问题：嗯，好问题 - 有什么区别？如果我知道这对数据，我可以非常快速地计算出实际距离，对吧？ - Ecir Hana

个人而言，我正在考虑优化代码。通过将x偏移量添加到y偏移量中，可以避免在距离公式中使用sqrt函数，从而得到一个粗略的距离估计值。这不是一个准确的距离，但它会节省大量的处理时间。就像你所说的，一旦它们配对，你可以获得真实的距离。在它们配对之前，可能需要计算很多距离。 - Corey Ogburn

Answer 1

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

- RickyA

Answer 2

你有两个一维问题，而不是一个二维问题。 将所有的“候选项”投影到x和y轴上，然后在x轴上放置垂直的“对象”，在y轴上放置水平的“对象”。

哇！两个一维问题。

现在是一维的。

将所有的“候选项”放入排序数组中，对于每个“对象”，使用二分查找在该数组中找到包含段（即最接近的两个“候选项”）。

结果为O(n log m + n log n)。

- kassak

---

谢谢！但是你确定它适用于图1吗？因为通过“投影”，它会优先选择出租车距离而不是笛卡尔距离。（对不起，我应该更明确一些 - 问题已编辑。） - Ecir Hana

@EcirHana 哎呀，我错过了那个图1是不同的任务 =) 对于点的情况，一切都变得更加困难。您可以使用基于四叉树的最近邻搜索方法（例如FLANN库http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN），或使用点Voronoi图（例如CGAL库http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Voronoi_diagram_2_ref/Chapter_intro.html）。 - kassak

Answer 3

我不明白如何从对象中创建行。对于每个对象，您需要创建两条线：一条垂直线和一条水平线，是吗？

无论如何，假设您有垂直线v1、v2、..、va和水平线h1、h2、...、hb。

根据它们在x轴上的偏移量对垂直线进行排序，根据它们在y轴上的偏移量对水平线进行排序。

对于候选集中的每个点，执行二分搜索以获取最近的垂直线和水平线。现在，计算最接近的(candidate,line)配对就很容易了。

- ElKamina

---

"对于每个对象，您创建两行" - 不，它要简单得多。只有一堆线，它们碰巧是轴对齐的。我想知道哪条线最靠近某个点（候选点）。 - Ecir Hana

@EcirHana 那么对象是什么意思？它们如何使用？无论如何，我的答案应该有效（输入一堆轴对齐的线和候选点。我不知道如何处理对象）。 - ElKamina

也许“对象”这个词有点令人困惑，我只是想要一个词来表示点和线。因此，“线”实际上就是“对象”，所以给定一堆线和一堆点，哪对的距离最短？对于点和点也是如此... - Ecir Hana

Answer 4

你要找的名字很可能是NNS（参见：http://en.wikipedia.org/wiki/Nearest_neighbor_search），是的，如果给定一些时间和空间来预计算一个静态的“对象”集合，你应该能够比O(n*m)更快地执行搜索。

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

- mikyra