11

我有一个二维点列表，我想获得它们中的哪些落在半圆内。

最初，目标形状是与 x 和 y 轴对齐的矩形。因此，当前算法通过它们的 X 坐标和二进制搜索对可能落在矩形内的第一个对进行排序。然后它依次迭代每个点。当它碰到一个超出目标矩形的 X 和 Y 上限的位置时，它会停止。

这不适用于半圆，因为您无法为其确定有效的上/下 x 和 y 边界。半圆可以有任何方向。

最坏的情况是，我会在半圆中找到维度（比如 x）的最小值，二分搜索到超出它的第一个点，然后依次测试这些点，直到超出该维度的上限。基本上是在网格上测试整个乐队的分数。问题是这将最终检查许多不在范围内的点。

4

11 回答 11

18

检查一个点是在半圆（或矩形）内部还是外部是一个常数时间操作。

检查 N 个点位于半圆或矩形的内部或外部是 O(N)。

对 N 个点进行排序是 O(N*lg(N))。

顺序测试所有点比排序然后基于二分搜索快速剔除点要快。

这可能是那些看起来快和快是两种不同事物的时代之一。

编辑

还有一种非常简单的方法可以测试半圆中某个点的包容性，而无需使用旋转、变换等。

将半圆表示为两个分量：

  • 从 a 点到b点的线段代表半圆的直径
  • left-of或right-of的方向，表示半圆在从a到b行进时位于线段ab的左侧或右侧

您可以利用右手定则来确定该点是否在半圆内。

然后一些伪代码来测试点p是否在半圆中，例如：

procedure bool is_inside:
    radius = distance(a,b)/2
    center_pt = (a+b)/2    
    vec1 = b - center_pt
    vec2 = p - center_pt
    prod = cross_product(vec1,vec2) 
    if orientation == 'left-of'
        return prod.z >= 0 && distance(center_pt,p) <= radius
    else
        return prod.z <= 0 && distance(center_pt,p) <= radius

此方法的另一个好处是不使用任何三角函数，您可以通过与平方距离进行比较来消除所有平方根。您还可以通过缓存 'vec1' 计算、半径计算、center_pt 计算并重新排序几个操作以提早退出来加速它。但我试图澄清。

'cross_product' 返回一个 (x,y,z) 值。它检查 z 分量是正还是负。这也可以通过不使用真正的叉积而只计算 z 分量来加速。

于 2009-02-11T01:08:03.740 回答
7

首先，平移和旋转半圆，使一端在负 X 轴上，另一端在正 X 轴上，以原点为中心（当然，您不会实际平移和旋转它，您将获得可以平移和旋转它的适当数字，并在下一步中使用它们）。

然后，您可以将其视为一个圆，忽略所有负 y 值，只使用 X 和 Y 的平方和的平方根进行测试，看看它是否小于或等于半径。

于 2009-02-11T00:57:26.213 回答
5

“也许他们可以暴力破解，因为他们有一个完整的 GPU 专用于他们。”

如果您有 GPU 供您使用，那么还有更多方法可以做到这一点。例如，使用模板缓冲区：

  • 清除模板缓冲区并将模板操作设置为递增
  • 将你的半圆渲染到模板缓冲区
  • 提出你的观点
  • 读回像素并检查您的点的值
  • 半圆内的点将增加两次。

本文介绍了如何在 OpenGL 中使用模板缓冲区。

于 2009-02-11T01:23:29.007 回答
1

如果有这样做的标准算法，我相信其他人会想出它，但如果没有：您可以尝试按距圆心的距离对点进行排序，并仅迭代那些距离小于半圆的半径。或者，如果计算距离很昂贵，我会尝试找到半圆的边界框（甚至是半圆所在的圆的边界正方形）并迭代该范围内的点。在某种程度上它取决于点的分布，即您希望它们中的大多数还是只有一小部分落在半圆内？

于 2009-02-11T00:58:10.143 回答
1

您可以在给定斜率的一侧找到圆中的点，对吗？

只需将两者结合起来。

于 2009-02-11T01:42:21.490 回答
1

这是我编写的函数的一部分，它确实为基于瓷砖的游戏中的武器提供锥形发射弧。 

float lineLength;
float lineAngle;
for(int i = centerX - maxRange; i < centerX + maxRange + 1; i++){
    if(i < 0){
        continue;
    }
    for(int j = centerY -  maxRange; j < centerY + maxRange + 1; j++){
        if(j < 0){
            continue;
        }

        lineLength = sqrt( (float)((centerX - i)*(centerX - i)) + (float)((centerY - j)*(centerY - j)));
        lineAngle = lineAngles(centerX, centerY, forwardX, forwardY, centerX, centerY, i, j);

        if(lineLength < (float)maxRange){
            if(lineAngle < arcAngle){
                if( (float)minRange <= lineLength){ 
                    AddToHighlightedTiles(i,j);
                }
            }
        }
    }
}

变量应该是不言自明的，线角度函数需要 2 条线并找到它们之间的角度。根据您指向的角度，forwardX 和 forwardY 只是从中心 X 和 Y 沿正确方向的一个图块。这些可以通过 switch 语句轻松获得。

float lineAngles(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
    int a = x2 - x1;
    int b = y2 - y1;
    int c = x4 - x3;
    int d = y4 - y3;

    float ohSnap = ( (a * c) + (b * d) )/(sqrt((float)a*a + b*b) * sqrt((float)c*c + d*d) );
    return acos(ohSnap) * 180 / 3.1415926545f;
}
于 2009-02-11T03:20:22.923 回答
0
  • 将弧的中心平移到原点
  • 计算纵坐标轴与半圆半径端点之间的角度
  • 用相同的 dx,dy 翻译问题点

  • 计算从原点到平移 x,y 点的距离，如果 d > 圆/弧的半径消除

    • 计算纵坐标轴和终点之间的角度
    • 如果角度不在半圆的起点和终点弧之间，则消除

    剩余点应在半圆内

于 2009-02-11T02:16:53.433 回答
0

我想有人在这里找到了与我相同的解决方案，但我没有代码可以显示，因为它在我的记忆中很远......

我会按步骤进行...
1.我会看看我是否在一个圆圈内...如果是的话，看看圆圈的哪一边。
2. 通过绘制一个来自半球体的向量的法线向量。我可以知道我是在向量的后面还是前面……如果你知道哪一边是半球，哪一边是虚空……如果你在向量之内，那将非常容易找到半球形。你必须做点积。

我不确定它是否足够清楚，但测试不应该那么难做......最后你必须寻找一个负值或正值......如果它是 0 你在向量上半球，所以由你决定它是在半球之外还是在半球内。

于 2009-02-11T03:39:05.233 回答
0

最快的方法将取决于您的典型数据。如果您要查看真实世界的数据，请先执行此操作。当点在半圆之外时，通常是因为它们在圆之外吗？您的半圆形通常是薄饼片吗？

有几种方法可以用向量来做到这一点。您可以将圆缩放为单位圆并使用叉积并查看结果向量。您可以使用点积并查看预期点如何落在其他向量上。

如果你想要一些非常容易理解的东西，首先检查以确保它在圆内，然后获取角度并确保它在决定半圆的两个向量的角度之间。

编辑：我忘记了半圆总是半圆。我在想一个圆的任意部分。

现在我已经记住了半圆是什么，这就是我将如何做到的。它类似于 stbuton 的解决方案，但它以不同的方式表示半圆。

我将半圆表示为平分半圆的单位向量。您可以通过交换 x 和 y 并取反其中一个，轻松地从指示半圆边界的任一向量（因为它们与表示相距 90 度）中得到它。

现在，您只需穿过从圆心减去要测试的点所创建的向量。z 的符号告诉您该点是否在半圆中，并且 z 的长度可以与半径进行比较。

我为 Cool Pool 做了所有的物理（来自 Sierra Online）。这一切都是在向量中完成的，并且充满了点和十字。向量解决方案很快。Cool Pool 能够在 P60 上运行，并进行了合理的休息甚至旋转。

注意：对于检查 sqrt(x x+y y) 的解决方案，甚至不要执行 sqrt。相反，保持半径的平方并与之进行比较。

于 2009-02-11T16:26:51.880 回答
0

看起来一个简单的方案在这里可以工作。

  1. 通过首先计算凸包来减少集合中的点数。只有凸包上的点将有助于与任何凸边界形状的任何交互。所以只保留船体周边的点子集。

  2. 可以很容易地认为，最小半径边界半圆必须具有凸包的一个边缘（两个点）沿半圆的直径重合。即，如果船体的某些边缘不在直径范围内，则存在一个直径较小的不同半圆，其中包含相同的点集。

  3. 依次测试每条边。（凸包通常有相对较少的边，所以这会很快。）现在它变成了一个简单的一维最小化问题。如果我们选择假设所讨论的边缘位于直径上，那么我们只需要找到球的中心。它必须位于我们认为是直径的当前线。因此，作为该点沿当前直径的位置的函数，只需找到离标称中心最远的点。通过最小化该距离，我们找到沿该线的最小半圆的半径作为直径。

现在，只需选择在凸包所有边缘上找到的最佳半圆。

于 2009-04-01T01:25:02.063 回答
0

如果您的点具有整数坐标，则最快的解决方案可能是查找表。由于半圆是凸的，对于每个 y 坐标，您会得到一个固定范围的 x，因此查找表中的每个条目都会给出最大和最小 X 坐标。

当然你仍然需要预先计算表格，如果你的半圆不是固定的，你可能会做很多。也就是说，这基本上是曾经渲染半圆的一部分——通过重复调用水平线绘制函数，整个形状将被渲染为一系列水平跨度。

首先要计算跨度（如果需要重复计算），您可能需要查找 Michael Abrash 的图形编程禅宗的旧副本。这描述了 Bresenhams 著名的直线算法和不太知名的 Hardenburghs 圆算法。将两者的面向跨度的版本结合起来快速计算半圆的跨度应该不会太难。

IIRC，Hardenburgh 使用 x^2 + y^2 = 半径^2，但利用了您正在逐步通过跨度以避免计算平方根的事实 - 我认为它使用了 (x+1)^2 = x 的事实^2 + 2x + 1 and (y-1)^2 = y^2 - 2y + 1，保持x、y、x^2和(radius^2 - y^2)的运行值，所以每一步只需要比较（当前 x^2 + y^2 是否太大）和一些补充。它只针对一个八分圆（确保单像素步长的唯一方法），并通过对称扩展到整个圆。

一旦你有了整个圆圈的跨度，应该很容易使用 Bresenhams 来切断你不想要的一半。

当然，只有在您绝对确定需要（并且可以使用整数）时，您才会执行所有这些操作。否则坚持使用stbuton。

于 2009-09-28T16:05:17.513 回答