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

First, translate & rotate the semi-circle so that one end is on the negative X-axis, and the other end is on the positive X-axis, centered on the origin (of course, you won't actually translate & rotate it, you'll just get the appropriate numbers that would translate & rotate it, and use them in the next step).

Then, you can treat it like a circle, ignoring all negative y-values, and just test using the square root of the sum of the squares of X & Y, and see if it's less than or equal to the radius.

Answer 2

If there's a standard algorithm for doing this, I'm sure someone else will come up with it, but if not: you could try sorting the points by distance from the center of the circle and iterating over only those whose distance is less than the semicircle's radius. Or if computing distance is expensive, I'd just try finding the bounding box of the semicircle (or even the bounding square of the circle of which the semicircle is part) and iterating over the points in that range. To some extent it depends on the distribution of the points, i.e. do you expect most of them or only a small fraction of them to fall within the semicircle?

Answer 3

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.

Answer 4

"Maybe they can brute force it since they have a full GPU dedicated to them."

If you have a GPU at your disposal, then there are more ways to do it. For example, using a stencil buffer:

• clear the stencil buffer and set the stencil operation to increment
• render your semicircle to the stencil buffer
• render your points
• read back the pixels and check the values at your points
• the points that are inside the semicircle would have been incremented twice.

This article describes how stencil buffers can be used in OpenGL.

Answer 5

You can find points in a circle and points on one side of a given slope, right?

Just combine the two.

Answer 6

Here's part of a function I wrote do get a cone firing arc for a weapon in a tile based game.

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);
                }
            }
        }
    }
}

The variables should be self explanatory and the line angles function takes 2 lines and finds the angle between them. The forwardX and forwardY is just one tile in the correct direction from the center X and Y based on what angle you're pointing in. Those can be gotten easily with a switch statement.

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;
}

Answer 7

I guess someone found the same solution as me here but I have no code to show as its pretty far in my memory...

I'd do it by steps...
1. I'd look if i'm within a circle... if yes look on which side of the circle.
2. By drawing a normal vector that come from the vector made by the semi-sphere. I could know if I'm behind or in front of the vector...and if you know which side is the semi sphere and which side is the void...It will be pretty damn easy to find if you're within the semi sphere. You have to do the dot product.

I'm not sure if it's clear enough but the test shouldn't be that hard to do...In the end you have to look for a negative or positive value...if it's 0 you're on the vector of the semisphere so it's up to you to say if it's outside or inside the semi-sphere.

Answer 8

The fastest way to do this will depend on your typical data. If you have real-world data to look at, do that first. When points are outside the semi-circle, is it usually because they are outside the circle? Are your semi-circles typically thin pie slices?

There are several ways to do this with vectors. You can scale the circle to a unit circle and use cross-products and look at the resultant vectors. You can use dot-products and see how the prospective point lands on the other vectors.

If you want something really easy to understand, first check to make sure it's inside the circle, then get the angle and make sure it's between the angle of the two vectors that dictate the semi-circle.

---

Edit: I had forgotten that a semicircle is always half a circle. I was thinking of any arbitrary section of a circle.

Now that I have remembered what a semicircle is, here's how I would do that. It's similar to stbuton's solution, but it represents the semicircle differently.

I'd represent the semicircle as the unit vector that bisects the semicircle. You can easily get that from either one of the vectors that indicate the boundary of the semicircle (because they are 90 degrees away from the representation) by swapping x and y and negating one of them.

Now you just cross the vector created by subtracting the point to be tested from the circle's center. The sign of z tells you whether the point is in the semicircle, and the length of z can be compared against the radius.

I did all the physics for Cool Pool (from Sierra Online). It's all done in vectors and it's filled with dots and crosses. Vectors solutions are fast. Cool Pool was able to run on a P60, and did reasonable breaks and even spin.

Note: For solutions where you're checking sqrt(x*x+y*y), don't even do the sqrt. Instead, keep the square of the radius around and compare against that.

Answer 9

It would appear that a simple scheme will work here.

1. Reduce the number of points in the set, by first computing the convex hull. Only the points on the convex hull will contribute to any interaction with any convex bounding shape. So retain only the subset of points on the perimeter of the hull.

2. It can easily be argued that the minimal radius bounding semi-circle must have one edge (two points) of the convex hull coincident along the diameter of the semi-circle. I.e., if some edge of the hull does not lie in the diameter, then there exists a different semi-circle with smaller diameter that contains the same set of points.

3. Test each edge in sequence. (A convex hull often has relatively few edges, so this will go quickly.) Now it becomes a simple 1-d minimization problem. If we choose to assume the edge in question lies on the diameter, then we merely need to find the center of the sphere. It must lie along the current line which we are considering to be the diameter. So as a function of the position of the point along the current diameter, just find the point which lies farthest away from the nominal center. By minimizing that distance, we find the radius of the minimal semi-circle along that line as a diameter.

Now, just choose the best of the possible semi-circles found over all edges of the convex hull.

Answer 10

If your points have integer co-ordinates, the fastest solution may be a lookup table. Since a semicircle is convex, for each y co-ordinate, you get a fixed range of x, so each entry in your lookup table gives maximum and minimum X co-ordinates.

Of course you still need to precalculate the table, and if your semicircle isn't fixed, you may be doing that a lot. That said, this is basically one part of what would once have been done to render a semicircle - the full shape would be rendered as a series of horizontal spans by repeatedly calling a horizontal line drawing function.

To calculate the spans in the first place (if you need to do it repeatedly), you'd probably want to look for an old copy of Michael Abrash's Zen of Graphics Programming. That described Bresenhams well-known line algorithm, and the not-so-well-known Hardenburghs circle algorithm. It shouldn't be too hard to combine the span-oriented versions of the two to quickly calculate the spans for a semi-circle.

IIRC, Hardenburgh uses the x^2 + y^2 = radius^2, but exploits the fact that you're stepping through spans to avoid calculating square roots - I think it uses the fact that (x+1)^2 = x^2 + 2x + 1 and (y-1)^2 = y^2 - 2y + 1, maintaining running values for x, y, x^2 and (radius^2 - y^2), so each step only requires a comparison (is the current x^2 + y^2 too big) and a few additions. It's done for one octant only (the only way to ensure single-pixel steps), and extended to the full circle through symmetry.

Once you have the spans for the full circle, it should be easy to use Bresenhams to cut off the half you don't want.

Of course you'd only do all this if you're absolutely certain that you need to (and that you can work with integers). Otherwise stick with stbuton.