## Bounds-checking with a circular sector

A circular sector is the part of a circle bounded by two radii and an arc connecting them. Determining whether a point lies in a sector is not quite as easy as rectangular bounds-checking. There are a few different approaches: θ-comparison, line-sides, and dot-products.

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`) = -1`x` + 2`y`

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.

### Trackbacks

The author does not allow comments to this entry

## Comments

Display comments as Linear | Threaded