在对数时间内测试点相对于凸包的位置

Question

我有一个2D点集合，需要测试输入点是否在的凸包内。由于这是一个二进制决策问题，理论上可以使用决策树实现O(log(N))。然而，我不知道如何组织数据和算法的实际实现，以便在O(log(N))内得到答案。在研究此想法时，我发现了以下内容：

我们如何更快地找到这两种情况呢？二分查找。只需在两个链中的点的第一个坐标中搜索x。如果它在链中，您已经找到了通过顶点的交叉点（而且您不必像以前那样仔细告诉交叉点的类型）。如果x不是链中顶点的坐标，则最接近它的两个值告诉您从（x，y）可能穿过的线段。因此，我们可以在 O(log n) 的时间内测试点是否在凸多边形中。事实证明，有数据结构可以在相同的 O(log n)时间限制下测试点是否在任意多边形中（或者在哪些多边形中）。但是它们更加复杂，所以我没有时间在这里描述它们；我会在ICS 164中谈论它们。

(http://www.ics.uci.edu/~eppstein/161/960307.html)

你有什么想法吗：

1. 数据结构应该如何设计才能达到 O(log(N))？
2. 算法应该如何设计？

- Michael

---

构建树至少是O(n log(n))，不是吗？ - Mark Ping

@MarkPing 当然可以用记忆化，但我需要的是测试本身的log(N)。 - Michael

“Possible duplicate?”（https://dev59.com/HGQn5IYBdhLWcg3wiXqd#16807944）无论如何，我在那里提供了一个答案，应该能够满足您的需求。 - Nuclearman

Answer 1

首先，我们只处理一个链。我们想要检查点(qx, qy)是否在一系列线段的上方。

昂贵的部分是在x坐标列表上进行二进制搜索，以找到小于查询点的最大值。你所需要的就是按照x顺序排序的链的点的数组。然后这就是一个简单的“点在线上方？”测试。

现在我们想要看看一个点是否在一个凸多边形中。如果你把那个凸多边形的边表示为一个上链和一个下链，那么它就是上链下面的东西与下链上面的东西的交集。所以这是两个二进制搜索。

（即使你只有按顺时针排序的点或其他什么，你也可以使用二进制搜索或四点搜索以对数时间找到多边形中最小和最大的x坐标。因此，如果不想预先计算上链和下链，也可以做到。）

编辑：我看到你的问题也可以解释为“点位置数据结构是什么样子的？”，而不是“如何存储凸包以允许高效的内部/外部测试？”

自然而然地，在点位于内外测试之外的稍微更一般的情况下研究点定位是很正常的。有一个CGAL可以用几种不同的方式进行点定位。它是由聪明的人编写的，他们对他们正在实现的算法和计算机有很好的理解。您可能找不到任何更快但仍能正确工作的东西。

话虽如此，Haran和Halperin 比较了 CGAL的各种算法的性能。他们使用了2008年的现代计算机，并制造了大量测试数据，并在每个测试案例中尝试了CGAL的不同点定位策略。除其他事项外，他们还有一个包含约140万个随机放置的边缘的案例，其中他们最好的数据结构只需要约190微秒来回答点位置查询。

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

- tmyklebu

Answer 2

这个问题可以归类为一个经典的“点定位”问题。

预处理包括计算点集的凸包，凸包的线段将在下一步中使用（或整个凸包作为一个区域）。

对于这种问题，有许多标准的O(log n)查询时间算法（如Kirkpatrick三角剖分、随机梯形图等）。

此外，请注意，在期望意义下，CH(S)中的点数是O(log N)，其中N是S中总点数。因此，用于点定位的线段数量已经减少到O(log N)，这意味着查询时间实际上是O(log log N)（以S中的总点数为基础，处于期望状态）。

- Sailesh

Answer 3

您可以使用扫描线算法（例如光栅化，使用水平扫描线）来实现此操作。构建顶点的排序边界需要n*log(n)的时间，但一旦排序完成，您可以基于点q设置扫描线并找到扫描线穿过的边界。

在凸情况下，光栅化变得简单，因为您不必担心扫描线中的凹面。

一个简单的概述是绕着多边形走，构造边缘对象，并使用绕组确定左侧和右侧。每个点的所有y值都放入排序列表（或数组、集合、映射等）中。

您的点q.y用于查找左侧和右侧的边界，然后您可以简单地确定q.x是否在左右坐标之间。您可以先计算凸包，以确保左/右侧是凸的。

（哇，当我搜索光栅扫描转换时，我发现了我大学课程here的笔记，那是我毕业后的一年。）

- Mark Ping

Answer 4

你可以在Log(h)的时间复杂度内完成，其中h是已计算的凸包点的数量。尽管维基百科上写着这是Log(n)的限制，但这完全是错误的。

你应该注意，维基百科"凸包算法"被David Eppstein过滤了，而你正是参考他。这个人阻止有用的信息被添加。如果那个人能够接受添加有用的信息（新算法）并理解它，他会意识到你可以在O(Log h)的时间复杂度内实现你的目标。请查看维基百科页面以获取页面历史记录。

在算法Ouellet凸包AVL中，您可以使用中间结果（按象限分组的avl树）并直接查找内部。您将以最快的方式实现您的目标（最佳性能：Log(h)）。

两个重要的观点：

• 首先，您必须确定象限。您应该检查它是否可以是象限边界本身。然后，对于不相交的象限只使用根点，或者使用象限的第一个和最后一个点的叉积来判断是否在右侧（如果没有找到象限，则是因为该点不能成为凸包点 - 无需确定象限）。
• 点按x坐标排序。

如果我有时间，我会为我的类添加一个接口以动态检查/添加新点。但是您现在可以这样做：获取凸包的中间结果并直接使用它（请参见2个重要点）。

- Eric Ouellet

Answer 5

struct point {
     LL x,y ;
} C[100010];


/*return area of triangle */
LL areaTriangle(const point &a, const point &b, const point &c) {
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
}

/*An user define function to calculate where a point p inside a convex hull or not */

bool inConvexPoly(int N, const point p) {

/*Input: C is an array with vertex x, y of a convex hull, points must be anticlock-wise, If it's clockwise then just reverse it. p is a point and we have to find does p inside polygon C or not*/

/*Most important part, finding two point using binay search such that point p may be lie inside the trianle
  made by those two points and point0 or point p may be lie inside the triangle which is
  made by point0, point_last, point_start */


LL start = 1, last = N - 1;
while(last - start > 1) {
    LL mid = (start + last) >> 1;
    if(areaTriangle(C[0], C[mid], p) < 0)   last = mid;
    else    start = mid;
}

/*Area of triangle form by point0, start point and last point*/
LL r0 = abs(areaTriangle(C[0], C[start], C[last]));


/*If point p is inside a triangle then the area of that triangle must be equal to
  the area ((point0, poin1, p) + (point0, point2, p) + (point1, point2, p))
  here point0 = C[0], point1 = C[start], point2 = C[last]*/

LL r1 = abs(areaTriangle(C[0], C[start], p));
LL r2 = abs(areaTriangle(C[0], C[last], p));
LL r3 = abs(areaTriangle(C[start], C[last], p));

/*Point p must not lie on any border line of the convex hull, So if the area is 0 then that three point lie on the
  same line */

LL r4 = areaTriangle(C[0], C[1], p);
LL r5 = areaTriangle(C[0], C[N - 1], p);

/*If the area of triangle form by point0, start and last point is equal to area
  from by triangle (point0, last, p) + (point0, start, p) + (last, start, p)
  and p don't lie on start-last line, point0-point1 line, point0-point[N - 1] line
  then the point p inside the convex hull */


 return (r0 == (r1 + r2 + r3) && r3 != 0 && r4 != 0 && r5 != 0);
}

 /*Try to draw picture for better understand */ 

 //End

- Jobayer sheikh

---

如果该点可以位于凸包的边界上呢？我只需去掉r4和r5吗？ - tomer.z

Answer 6

使用角度的替代方案：

使用您选择的某种启发式方法在凸包内部选择一些点C。

选择通过C的某条线L，例如与OX轴平行的线。

对于凸包上的每个点P，计算线CP和L之间的角度，并使用它来排序凸包点。

现在，如果您想知道某个给定点T是否在凸包内，请计算线CT和L之间的角度，并使用二分搜索查找凸包中紧接其后和之前的点（分别为A和B）。

现在，您只需要检查T是否与C在线AB的同侧（内部）或不在同侧（外部）即可。

- salva