其在log(n)中相对于凸包的位置的测试点

Question

我有一个2D点的集合,S我需要测试输入点q是否在凸包的内部或外部S.

由于它是关于二元决策的,我以为我理论上可以O(log(N))通过使用决策树来实现.

但是我不知道如何组织数据以及算法如何真正得到答案O(log(N)).

在研究这个想法的同时,我发现了这个:

我们怎样才能更快地找到这两种情况？二进制搜索.只需在两个链中的第一个坐标点中搜索x即可.如果它在链中,你已经找到了穿过顶点的交叉(并且你也不必小心分辨什么样的交叉).如果x不是链中顶点的坐标,则它的两个最接近的值会告诉您来自(x,y)的光线可能穿过哪个线段.因此,我们可以在时间O(log n)中测试点是否在凸多边形中 .

事实证明,有一些数据结构可以测试一个点是否在同一个O(log n)时间范围内的任意多边形(或它所在的多个多边形中的哪个).但它们更复杂,所以我没有时间在这里描述它们; 我将在ICS 164中的某些方面谈论它们.

(http://www.ics.uci.edu/~eppstein/161/960307.html)

所以你有任何想法:

1. 如何将数据结构放入其中O(log(N))？
2. 该算法应该如何？

Answer 1

我们首先只处理一条链。我们想要检查 是否(qx, qy)位于一条凸线段链之上。

昂贵的部分是对x坐标列表进行二分搜索，以找到小于查询点的最大坐标。为此，您所需要的只是按顺序排序的链点数组x。那么这就是一个简单的“线上方的点？” 测试。

现在我们想看看一个点是否在凸多边形中。如果将该凸多边形的边缘表示为上链和下链，那么它就是上链下方的内容与下链上方的内容的交集。所以这是两次二分搜索。

（即使您刚刚按顺时针排序顺序或其他方式获得了点，您也可以x使用二分搜索或四点搜索在对数时间内找到多边形中的最小和最大坐标。因此您甚至不必预先计算如果您不想的话，请拆下上链和下链。）

编辑：我看到你的问题也可以解析为“点位置数据结构看起来像什么？” 而不是“如何存储凸包以允许有效的内部/外部测试？”

在比内部-外部测试稍微更一般的背景下研究点位置是很自然的。有一个

CGAL可以通过几种不同的方式进行点定位。它是由聪明人编写的，他们对他们正在实现的算法以及算法将使用的计算机有很好的了解。您可能无法更快地找到仍然可以正常工作的任何东西。

话虽如此，Haran 和 Halperin比较了CGAL 各种算法的性能。他们使用了 2008 年的现代计算机，制作了大量测试数据，并在每个测试用例上尝试了 CGAL 的不同点定位策略。除此之外，他们有大约 140 万条随机放置的边缘的情况，其中他们的最佳数据结构只需要大约 190 微秒来回答点位置查询。

考虑到典型点定位算法的复杂性，这是非常快的——我自己无法做到这一点。理论告诉我们，它的增长速度类似于 O(log n)。然而，该 O(log n) 比搜索排序数组所需的 O(log n) 时间慢几个数量级。当你做计算几何时请记住这一点；常数很重要，而且它们通常都不是很小。