13

我有一组 2D 点S，我需要测试输入点q是在 . 的凸包内部还是外部S。

由于它是关于二元决策的，我认为理论上我可以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. 算法应该是什么样子？
4

6 回答 6

4

让我们先处理一个链。我们要检查是否(qx, qy)在凸线段链之上。

昂贵的部分是在x坐标列表上进行二进制搜索，以找到小于查询点的最大坐标。为此，您只需要一个按x顺序排序的链点数组。那么它是一个简单的“线上点？” 测试。

现在我们想看看一个点是否在一个凸多边形中。如果您将该凸多边形的边缘表示为上链和下链，则它是上链下方的东西与下链上方的东西的交点。所以这是两个二进制搜索。

（即使您只是按顺时针排序或其他方式获得点，您也可以x使用二进制搜索或四点搜索在对数时间内找到多边形中的最小和最大坐标。因此您甚至不必预先计算如果你不想的话，上链和下链。）

编辑：我看到您的问题也可以解析为“点位置数据结构看起来像什么？” 而不是“我如何存储凸包以进行有效的内部/外部测试？”

在比内外测试稍微更一般的背景下研究点位置是很自然的。有一个

CGAL可以通过几种不同的方式进行点定位。它是由对他们正在实施的算法和算法将使用的计算机有很好理解的聪明人编写的。您可能无法以更快的速度找到仍然可以正常工作的任何东西。

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

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

于 2013-06-13T17:24:52.290 回答
2

这个问题可以归类为经典point-location问题。

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

  • O(log n)对于这类问题（http://en.wikipedia.org/wiki/Point_location ）有很多标准的查询时间算法，比如柯克帕特里克三角剖分、随机梯形图等。

另请注意，期望中的点数CH(S)是O(log N)其中N的总点数S。因此，考虑点定位的线段数量已经减少到O(log N)，这意味着查询时间实际上是期望的 O(log log N) （以 中的总点数计S）。

于 2013-06-13T20:54:06.833 回答
1

您应该能够使用扫描算法（如光栅化，例如使用水平扫描线）来执行此操作。建立顶点的排序边是 n*log(n)，但是一旦排序，你可以找到基于点 q 设置扫描线并找到扫描线交叉的边。

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

一个简单的轮廓是围绕多边形，构造边缘对象，使用绕组确定左右边。每个点的所有 y 值都进入一个排序列表（或数组，或集合，或映射，等等）。

您的点 qy 用于查找左右两侧的边缘，然后您可以简单地确定 qx 是否在左右坐标之间。您可以先计算凸包，以确保您的左/右侧是凸的。

（哇，在搜索光栅扫描转换时，我在毕业后的一年里看到了我本科班的笔记。）

于 2013-06-13T20:24:41.880 回答
1 
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
于 2015-09-01T11:19:27.650 回答
1

您可以在 Log(h) 中执行此操作，其中 h 是已计算的船体点的点数。尽管这是在 Wikipedia 中所写的，但它受 Log(n) 的约束是完全错误的。

您应该注意，维基百科“凸壳算法”由您引用的 David Eppstein 过滤。这家伙阻止添加有用的信息。如果那个人愿意添加有用的信息（新算法）并理解它，他会意识到你可以在 O(Log h) 内实现你的目标。请查看 Wikipedia 页面以了解该页面的历史。

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

2个要点：

  • 您必须首先确定象限。您应该检查它是否可能是象限边界本身。之后，仅使用不相交象限的根点，或者使用象限的第一个和最后一个点的叉积来知道它是否在右边（如果是叉积，如果没有找到象限，那是因为该点不能是一个船体点 - 无需识别象限）。
  • 点按 x 坐标排序。

如果我能找到一些时间，我会在我的类中添加一个接口来动态检查/添加新点。但是你现在就可以做到：获取凸包中间结果并直接使用它（请参阅 2 个重点）。

于 2017-11-22T19:01:18.237 回答
0

使用角度的替代解决方案：

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

选择一条穿过 C 的线 L，例如平行于 OX 轴的线。

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

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

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

于 2017-11-23T08:58:23.440 回答