我可以使用什么算法来确定半圆内的点？

我有一个二维点列表,我想获得它们中的哪一个属于半圆.

最初,目标形状是与x和y轴对齐的矩形.因此,当前算法通过它们的X坐标和二进制搜索对对进行排序,以便第一个可以落入矩形内.然后它按顺序迭代每个点.当它击中超出目标矩形的X和Y上限的那个时,它会停止.

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

最糟糕的情况是,我会在半圆形中找到维度(比如x)的最小值,二元搜索到超出它的第一个点,然后依次测试这些点,直到超出该维度的上限.基本上测试整个乐队在网格上的价值点.这样的问题最终将检查许多不在范围内的点.

检查点是在半圆的内部还是外部(或者对于该问题的矩形)是恒定时间操作.

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

对N点进行排序为O(N*lg(N)).

按顺序测试所有点的速度比逐行排序然后基于二进制搜索快速剔除点的速度更快.

这可能是那些看似快速和快速的东西是两个不同的事情之一.

编辑

还有一种简单的方法来测试半圆中一个点的包含,而不用旋转,变换等.

将半圆表示为两个组成部分:

从a点到b点的线段表示半圆的直径

任一的定向左的或右的指示半圈是要么线段的左侧或右侧AB从行驶时一个给b

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

然后一些伪代码来测试点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分量来加速.

首先,平移和旋转半圆,使一端位于负X轴上,另一端位于正X轴上,以原点为中心(当然,您实际上不会平移和旋转它) ,你只需得到适当的数字即可翻译和旋转它,并在下一步中使用它们.

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

"也许他们可以蛮力,因为他们拥有专用于他们的完整GPU."

如果您拥有GPU,那么有更多方法可以实现.例如,使用模板缓冲区:

清除模板缓冲区并将模板操作设置为递增

将半圆渲染到模板缓冲区

渲染你的观点

读回像素并检查各点的值

半圆内的点会增加两次.

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