我可以使用什么算法来确定半圆内的点? [英] What algorithm can I use to determine points within a semi-circle?

问题描述

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

I have a list of two-dimensional points and I want to obtain which of them fall within a semi-circle.

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

Originally, the target shape was a rectangle aligned with the x and y axis. So the current algorithm sorts the pairs by their X coord and binary searches to the first one that could fall within the rectangle. Then it iterates over each point sequentially. It stops when it hits one that is beyond both the X and Y upper-bound of the target rectangle.

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

This does not work for a semi-circle as you cannot determine an effective upper/lower x and y bounds for it. The semi-circle can have any orientation.

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

Worst case, I will find the least value of a dimension (say x) in the semi-circle, binary search to the first point which is beyond it and then sequentially test the points until I get beyond the upper bound of that dimension. Basically testing an entire band's worth of points on the grid. The problem being this will end up checking many points which are not within the bounds.

推荐答案

检查一个点是在半圆(或矩形)的内部还是外部是一个常数时间的操作.

Checking whether a point is inside or outside a semi-circle (or a rectangle for that matter) is a constant-time operation.

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

Checking N points lie inside or outside a semi-circle or rectangle is O(N).

对你的 N 个点进行排序是 O(N*lg(N)).

Sorting your N points is O(N*lg(N)).

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

It is asymptotically faster to test all points sequentially than it is to sort and then do a fast culling of the points based on a binary search.

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

This may be one of those times where what seems fast and what is fast are two different things.

编辑

还有一种非常简单的方法可以测试半圆中某个点的包含情况，而无需费力地进行旋转、变换等操作.

There's also a dead-simple way to test containment of a point in the semi-circle without mucking about with rotations, transformations, and the like.

将半圆表示为两个分量:

Represent the semi-circle as two components:

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

• a line segment from point a to b representing the diameter of the semi-circle
• an orientation of either left-of or right-of indicating that the semi-circle is either to the left or right of line segment ab when traveling from a to b

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

You can exploit the right-hand rule to determine if the point is inside the semicircle.

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

Then some pseudo-code to test if point p is in the semi-circle like:

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 计算并重新排序几个操作以提早退出来加速它.但我试图弄清楚.

This method has the added benefit of not using any trig functions and you can eliminate all square-roots by comparing to the squared distance. You can also speed it up by caching the 'vec1' computation, the radius computation, center_pt computation, and reorder a couple of the operations to bail early. But I was trying to go for clarity.

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

The 'cross_product' returns an (x,y,z) value. It checks if the z-component is positive or negative. This can also be sped up by not using a true cross product and only calculating the z-component.

这篇关于我可以使用什么算法来确定半圆内的点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！