表明，给定一个查询点 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
我正在尝试解决本书 "Computational Geometry Algorithm and Applications, 3rd - de berg et al" 第 6 章 - 点位置的一些练习。不幸的是，我不知道如何解决以下练习：
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)。
希望有人能帮助我。
这个想法基本上是进行二分查找，以找到该点属于哪个 'segment'。这里的假设是多边形环绕某个固定原点 O，这是定义 angular 排序例程所必需的。
判断q是否位于P[n/2]的'left'或'right'（我指的是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 是否在 'wedge'.
中
从 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).
我正在尝试解决本书 "Computational Geometry Algorithm and Applications, 3rd - de berg et al" 第 6 章 - 点位置的一些练习。不幸的是，我不知道如何解决以下练习：
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)。
希望有人能帮助我。
这个想法基本上是进行二分查找，以找到该点属于哪个 'segment'。这里的假设是多边形环绕某个固定原点 O，这是定义 angular 排序例程所必需的。
判断q是否位于P[n/2]的'left'或'right'（我指的是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 是否在 'wedge'.
从 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).