证明给定一个查询点q，可以在时间O（log n）中检验q是否位于P内 [英] Show that, given a query point q, it can be tested in time O(log n) whether q lies inside P

问题描述

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

给定一个凸多边形P作为其排序顺序中的n个顶点的数组
沿着边界。显示给定一个查询点q，它可以在
时间O（log n）中进行测试，不管q是否在P内。

到目前为止我的想法：
我知道确定一个点是否位于O（log n）中的p的唯一方法是使用有向无环图。为了使用有向无环图我需要建立它，这在O（log n）中是不可能的。所以，不知何故，我需要使用有序数组，但我知道的唯一解决方案将花费O（N）。

我希望有人能帮助我。

解决方案

这个想法基本上是做一个二进制搜索，来找到这个点属于哪个'segment'。这里的假设是多边形环绕一些固定的原点 O ，这是定义一个角度排序例程所必需的。

要找到 q 左'或'右'的 P [n / 2] （我的意思是逆时针或顺时针方向的旋转差异大约 O ：

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

<然后我们可以使用这个测试来找出哪个'segment'或者'wedge' q 在哪里，也就是说多边形中的哪些点 q 之间（在图上是 P [n / 2 - 1] 和 P [n / 2] ），使用二进制搜索，即O（log n）。 （我假设你知道如何做到这一点）

一旦我们知道了，我们需要知道 q 在'楔子'内。

从

计算路口在[ Pl ， Pr ]和[ q ， O ]赋予 s ，并计算距离e | s - O | 。如果这大于 | q - O | ，那么 q 在多边形P内，反之亦然。

（这一步当然是O（1）。但是可能有更优雅的方式来实现它 - 我只是在说明它背后的逻辑）

总复杂度为O（log n）+ O（1）= O（log n）。

I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 6 - Point Location. Unfortunately, I have no idea how to solve the following exercise:

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.

My Idea so far: The only way I know to determine if a point lies inside p in O(log n) is to use a directed acyclic graph. In order to use a directed acyclic graph I need to build it, which is impossible in O(log n). So, somehow I need to use the ordered array, but the only solution I know with an array will cost O(N).

I hope that someone could help me.

解决方案

The idea is basically to do a binary search, to find which 'segment' the point belongs to. The assumption here is that the polygon wraps around some fixed origin O, which is necessary to define an angular sorting routine.

To find whether q lies on the 'left' or 'right' of P[n/2] (by which I mean an anticlockwise or clockwise rotational difference about O), we do the 2D cross-product:

This is a real scalar. If this is positive, then a is to the right of b, and vice versa. In our code a = q - O and b = P[i] - O, where i is the index of the point on the polygon we are testing q against.

We can then use this test to find which 'segment' or 'wedge' q is in, i.e. which points of the polygon q is between (on the diagram these are P[n/2 - 1] and P[n/2]), using a binary search, which is O(log n). (I'll assume you know how to do this)

Once we know that, we need to know whether q is inside the 'wedge'.

From https://en.wikipedia.org/wiki/Line%E2%80%93line_intersection, for two lines defined by pairs of points [(x1, y1), (x2, y2)] and [(x3, y3), (x4, y4)] respectively, their intersection point (Px, Py) is given by

Compute the intersection between [Pl, Pr] and [q, O] to give s, and compute the distance |s - O|. If this is greater than |q - O| then q is inside the polygon P, and vice versa.

(This step is of course O(1). There may however be more elegant ways of doing it - I'm just illustrating the logic behind it)

The total complexity is then O(log n) + O(1) = O(log n).

这篇关于证明给定一个查询点q，可以在时间O（log n）中检验q是否位于P内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！