显示,给定查询点q,可以在时间O(log n)中测试q是否位于P内

Question

我试图解决第6章 - 点位置"计算几何算法和应用,第3版 - 德伯格等人"一书的一些练习.不幸的是,我不知道如何解决以下练习:

Given a convex polygon P as an array of its n vertices in sorted order
along the boundary. Show that, given a query point q, it can be tested in
time 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),我们做2D 交叉产品:

这是一个真正的标量.如果这是积极的,那么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).