algorithm - 表明，给定一个查询点 q，可以在时间 O(log n) 内测试 q 是否在 P 内

Question

我正在尝试解决第 6 章 - 点定位的“计算几何算法和应用，第 3 版 - de berg 等人”一书的一些练习。不幸的是，我不知道如何解决以下练习:

Given a convex polygon P as an array of its n vertices in sorted orderalong the boundary. Show that, given a query point q, it can be tested intime O(log n) whether q lies inside P.

到目前为止我的想法:我知道确定一个点是否位于 O(log n) 中的 p 内的唯一方法是使用有向无环图。为了使用有向无环图，我需要构建它，这在 O(log n) 中是不可能的。因此，我需要以某种方式使用有序数组，但我知道的唯一解决方案是使用数组，成本为 O(N)。

我希望有人能帮助我。

Answer 1

这个想法基本上是进行二进制搜索，以找到该点属于哪个“段”。这里的假设是多边形环绕某个固定原点 O，这是定义角度排序例程所必需的。

找出 q 是否位于 P[n/2] 的“左”或“右”(我的意思是逆时针或顺时针旋转差异O)，我们做二维叉积:

这是一个真正的标量。如果这是正数，则 a 位于 b 的右侧，反之亦然。在我们的代码 a = q - O 和 b = P[i] - O 中，其中 i 是多边形上点的索引我们正在针对 q 进行测试。

然后我们可以使用此测试来查找 q 位于哪个“段”或“楔形”中，即多边形 q 的哪些点位于(在图表上)它们是 P[n/2 - 1] 和 P[n/2])，使用二进制搜索，即 O(log n)。 (我假设你知道怎么做)

一旦知道这一点，我们就需要知道 q 是否在“楔形”内。

来自 https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection ，对于分别由点对 [(x1, y1), (x2, y2)] 和 [(x3, y3), (x4, y4)] 定义的两条线，它们的交点 (Px, Py) 由

计算 [Pl, Pr] 和 [q, O] 的交集，得到 s，并计算距离|s - O|。如果这大于 |q - O| 则 q 在多边形 P 内，反之亦然。

(这一步当然是 O(1)。然而，可能有更优雅的方式来做这件事——我只是说明它背后的逻辑)

总复杂度为 O(log n) + O(1) = O(log n)。