David Owen’s blog

For all of these, I assume that the point being considered is already known to be within the bounds of the circle and also that the circle is centered at (0, 0).

Terms

The sector is the area bounded by starting with the radius S and sweeping counter-clockwise by sweep to radius E. The point to check is P.

θ-comparison

The tricky thing about comparing angles (θ) is that they're modular—they wrap around—and the wrapping has to be dealt with explicitly. Perhaps the easiest approach is to force P_θ to one "side" of S. Then, the comparison with E is simple.

We can see in this example that even though P is in the bounded area between S and E, when we consider only the range of 0≤θ<2π it appears to the left of both S and E:

The solution is to add 2π to P until the result is right of S, at which point the comparison with E is straight-forward. In otherwords, we select the first P that is to the right of the first S.

The algorithm is simply:

def in_bounds(S, sweep, P):
    s_theta = theta(S)
    p_theta = theta(P)
    if p_theta < s_theta:
        p_theta += 2*PI
    return p_theta <= s_theta + sweep

Line-sides

Within the circle, the sector is the area found on certain sides of two lines. If we take each radii as having a direction from the center of the circle outward, then we can say that an in-bounds point will be left of S and right of E.

Determining which side of a directed line a point is on is actually pretty easy. We use the standard form for the equation of a line:

Ax + By + C = 0

Each radius runs through (0, 0), so C = 0, leaving just:

Ax + By = 0

The coefficients A and B can be determined by any vector perpendicular to the line. The perpendicular vector actually defines a gradient f(x, y), of which the line being defined is just one level at f(x, y) = 0.

Given a line running from (0, 0) through, for example, (2, 1), the perpendicular gradients will be either (-1, 2) or (1, -2), depending on which convention we choose to follow. We'll follow the convention that uses the vector on the left: (-1, 2). Then, the x and y of that vector give us A and B (respectively) for our equation:

f(x, y) = -1x + 2y

We can check that the points we know are on the line evaluate correctly:

f(0, 0) = -1·0 + 2·0 = 0

f(2, 1) = -1·2 + 2·1 = 0

Points "left" of the line will evaluate positively, and those "right" negatively:

f(1, 1) = -1·1 + 2·1 = 1

f(1, 0) = -1·1 + 2·0 = -1

f(x, y) will yield a measure of distance between the point and the line, scaled by the length of the vector selected for A and B. If that vector is normalized to length 1, then f(x, y) will give the distance itself without scaling.

For minor sectors (less than half the circle), the test for boundedness will be:

(P left of S) and (P right of E)

For major sectors (θ>π), that changes.

We instead determine whether P is not within the opposing minor sector:

not ((P right of S) and (P left of E))

This is equivalent to:

(P left of S) or (P right of E)

This is the union of the two half-planes, instead of the intersection of them.

The procedure then is:

def in_bounds(S, sweep, P):
    s_theta = theta(S)
    s_x = cos(s_theta)
    s_y = sin(s_theta)
    s_norm_x = -s_y
    s_norm_y = s_x

    e_theta = s_theta + sweep
    e_x = cos(e_theta)
    e_y = sin(e_theta)
    e_norm_x = -e_y
    e_norm_y = e_x

    p_x = x(p)
    p_y = y(p)

    f_s = s_norm_x*p_x + s_norm_y*p_y
    f_e = e_norm_x*p_x + e_norm_y*p_y

    if sweep <= PI:
        return f_s >= 0 and f_e <= 0
    else:
        return f_s >= 0 or f_e <= 0

Dot-products

The equations of the lines in the previous method already make use of some vector math. We can go all-out by using the dot-product to determine the angle between two vectors.

Let's define one vector as going from (0, 0) to P. The dot-product will tell us the angle between that and any other vector, such as S or E, but it doesn't distinguish which side of a vector another vector is on, just the absolute angle (the dot-product is commutative).

To overcome this, we'll select the test vector to be the bisector B of the sector:

If P is within sweep/2 of B, then it must be between S and E, whether the sector is minor or major.

Note that determining angle from dot-products requires normalization: either the vectors can be normalized before the dot-product is taken, or the product can be normalized after.

This gives a very simple test function:

def in_bounds(S, sweep, P):
    half_sweep = sweep/2

    b_theta = theta(S) + half_sweep
    b_x = cos(b_theta)
    b_y = sin(b_theta)

    p_theta = theta(P)
    p_x = cos(p_theta)
    p_y = sin(p_theta)

    d = b_x*p_x + b_y*p_y

    return d <= cos(half_sweep)

Comparisons

Which you use depends on several factors, including simplicity, speed, and utility.

The θ-comparison is probably the simplest. Which of the line-side or dot-product checks you consider to be simpler depends on which math you're more comfortable with.

Speed depends greatly on the relative costs to execute different types of operations, such as addition, multiplication, and trigonometric. It also depends on your prefered representation (e.g. whether you represent the sector by S_theta and E_theta, or by S_theta and sweep, etc.), and what values could be cached. If the sectors don't change frequently, the dot-product check could be the fastest, as it doesn't require any branching.

Utility is more nuanced. If you just want bounds-checking, the utilities are all identical. If, however, you'd like to force a point to be within bounds, utility becomes a distinguishing factor.

If you want to force it to be in bounds along the shortest distance according to the x,y plane, the line-side algorithm is most adaptable. If you want to force according to polar distance, the dot-product check might be easiest to adapt without error, as it would not have to deal with the extra intricacies of wrapping in modular arithmetic. If the distance a point moves while being forced is minimal, either approach will be roughly equivalent in terms of final result.