我可以用什么算法来一个半圆内确定分？ [英] 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.

重新present半圆作为两个组件：

Represent the semi-circle as two components:

• 从点线段 为 B 再presenting半圆的直径
• 或者左的或右键的的说明半圆要么是线段的左侧或右侧的 AB 从行驶时 为 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.

然后一些伪code，以测试点的 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

该方法具有不使用任何三角函数的好处，你可以通过比较来的平方距离消除所有方的根源。您也可以加快它通过缓存VEC 1计算，半径计算，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屋！