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

Question

我有一组二维点 S，我需要测试输入点 q 是在 S 的凸包内部还是外部>.

因为它是关于二元决策的，所以我想我可以通过使用决策树在理论上实现 O(log(N))。

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

带着这个想法进行研究时，我发现了这一点:

How can we find these two cases more quickly? Binary search. Just search for x in the first coordinates of points in the two chains. If it is in the chain, you have found a crossing through a vertex (and you don't have to be as careful to tell what kind of crossing, either). If x is not the coordinate of a vertex in the chain, the two nearest values to it tell you which segment the ray from (x,y) might cross. So we can test whether a point is in a convex polygon in time O(log n).

It turns out that there are data structures that can test whether a point is in an arbitrary polygon (or which of several polygons it's in) in the same O(log n) time bound. But they're more complicated, so I don't have time to describe them here; I'll talk about them at some point in 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 compared CGAL各种算法的性能。他们使用了 2008 年的现代计算机，他们制作了大量测试数据，并在每个测试用例上尝试了 CGAL 的不同点定位策略。除其他事项外，他们有大约 140 万个随机放置的边缘的情况，其中他们的最佳数据结构只需要大约 190 微秒来回答点位置查询。

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