optimization - What algorithm can I use to determine points within a semi-circle?

Question

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

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.

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.

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.

Answer 1

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

Checking N points lie inside or outside a semi-circle or rectangle is O(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.

EDIT

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 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.

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

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.

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.