Mathematics of 2D Hit-testing

Computer games or graphical user interfaces often need to check if certain objects overlap, get selected or manipulated by the user. Using a pointing device like a mouse is therefore a very natural way of interacting with the world. Detecting if objects are hit, highly depends on the type of objects that interact with each other.

Hit-test: Circle and Point

Given the center point $$\mathbf{c}$$ of a circle $$C$$ with its radius $$r$$ and a the position $$\mathbf{p}$$ of a point $$P$$, the point hits the circle iff the point is inside the circle, which means the hypothenuse of the right triangle is smaller than the radius of the circle:

The hypothenuse of the triangle is simply the distance of the two points and as such the hit-test can be formulated as follows:

$\begin{array}{rl} \text{hittest}_{CP}(C, P):=& |\mathbf{c} - \mathbf{p}| \leq r\\ =& (\mathbf{c} - \mathbf{p})\cdot(\mathbf{c} - \mathbf{p})\leq r^2 \end{array}$

function hittestCP(C, P) {

let tx = C.x - P.x;
let ty = C.y - P.y;
return tx * tx + ty * ty <= P.r * P.r;
}

Hit-test: Circle Outline and Point

Let $$\mathbf{c}$$ be the center of a circle $$C$$ with radius $$r$$ and the point $$P$$ with position $$\mathbf{p}$$ the point to be tested. Since hitting a very thin circle right on the radius line with a point is hard, like with the mouse cursor, we put a margin of size $$\epsilon$$ around the line. We also define the distance $$d=|\mathbf{c} - \mathbf{p}|$$ between the center of the circle and the point to be tested.

To check if the point is on the ring with width $$\epsilon$$ around the radius of the circle, we can check

$\begin{array}{rl} \text{hittest}_{CoP}(C, P) :=& r - \frac{1}{2}\epsilon \leq d\leq r+\frac{1}{2}\epsilon\\ = & 2|d - r | \leq \epsilon \end{array}$

function hittestCoP(C, P, eps) {

let tx = C.x - P.x;
let ty = C.y - P.y;
let d = Math.sqrt(t.x * t.x + t.y * t.y);
return 2 * Math.abs(d - r) <= eps;
}

Hit-test: Arc and Point

Let $$\mathbf{p}_1$$ be the center of an arc $$A$$ with radius $$r$$ and a starting angle $$\theta_1$$ and an end angle $$\theta_2$$. Furthermore, we have a point $$P$$ with position $$\mathbf{p}_2$$, which we want to test. Since hitting a very thin arc with a point is hard, like with the mouse cursor, we put a margin of size $$\epsilon$$ around the arc. We also define the distance $$d=|\mathbf{p}_2 - \mathbf{p}_1|$$ between the center of the arc and the point to be tested.

The first thing we do is, we interpret the arc $$A$$ as a circle $$C$$ and use the hit-testing routine for a point on a circle. If the point is on the ring defined by the $$\epsilon$$ margin, we need to check if the angles are in the right interval. I wrote an article about checking if an angle is between two other angles quite some time ago. That’s why I use the result here only:

$\begin{array}{rl} \text{hittest}_{AP}(A, P) :=& \text{hittest}_{CoP}(A, P) \land \text{angleBetween}(\phi, \theta_1, \theta_2) \end{array}$

Where $$\phi=\tan^{-1}\left(\frac{\mathbf{p}_2^y - \mathbf{p}_1^y}{\mathbf{p}_2^x - \mathbf{p}_1^x}\right)$$ is the angle between the x-axis and the vector formed by the two points $$\mathbf{p}_1$$, $$\mathbf{p}_2$$.

Hit-test: Line segment and Circle

Given a line segment $$L$$ defined by two points $$\mathbf{p}_1$$ and $$\mathbf{p}_2$$ as well as a circle $$C$$ with position $$\mathbf{p}_3$$ and its radius $$r$$. Between the two points on the line segment are infinitely many points and we choose exactly that point $$\mathbf{p}$$ which has the minimal distance to the circle. That is the orthogonal line passing through the circle center:

Now the two points of the line form a vector $$\mathbf{b}=\mathbf{p}_2 - \mathbf{p}_1$$, the first point of the line and the center of the circle form the vector $$\mathbf{a}=\mathbf{p}_3 - \mathbf{p}_1$$ and the first point of the line and point $$\mathbf{p}$$ form vector $$\mathbf{c}=\mathbf{p}-\mathbf{p}_1$$. Point $$\mathbf{p}$$ is the orthogonal projection of vector $$\mathbf{a}$$ onto vector $$\mathbf{b}$$ plus the original point $$\mathbf{p}_1$$ as position vector:

$\mathbf{p} = \mathbf{p}_1 + \frac{\mathbf{a}\cdot\mathbf{b}}{\mathbf{b}\cdot\mathbf{b}}\mathbf{b}$

Using the point $$\mathbf{p}$$ and the center of the circle $$\mathbf{p}_3$$, we can determine the distance $$d=|\mathbf{p}_3 - \mathbf{p}|$$ between the circle and the line. The necessary condition for a hit-test is therefore $$d \leq r$$.

This check is not sufficient, however, since it will deliver false positives outside the range of the line. We need additional tests if the length of vector $$\mathbf{c}$$ does not exceed the length of vector $$\mathbf{b}$$ for the right side. Moreover, we also have to limit the direction of the vector $$\mathbf{c}$$ relative to vector $$\mathbf{b}$$ by saying the angle between the vectors must be less than $$90^°$$ or $$\mathbf{b}\cdot\mathbf{c}\geq 0$$ to limit the left hand side as well.

The hit-test now stops orthogonal to the line-caps, which is not okay. We want to include the line-caps and we do so by checking if the line-caps are within the radius $$r$$.

The final hit-test condition for a circle and a line-segment is then:

$\begin{array}{rl} \text{hittest}_{LC}(L, C):=& (d\leq r\land |\mathbf{c}|\leq|\mathbf{b}|\land\mathbf{b}\cdot\mathbf{c}\geq 0)\lor |\mathbf{p}_3 - \mathbf{p}_1|\leq r\lor |\mathbf{p}_3 - \mathbf{p}_2|\leq r \end{array}$

Hit-test: Line segment and Point

Given a line segment $$L$$ defined by two points $$\mathbf{p}_1$$ and $$\mathbf{p}_2$$ as well as the point $$\mathbf{p}$$ to be tested. A typical use case of $$\mathbf{p}$$ is the mouse cursor. If we use the line-circle Hit-testing method with a small radius, we will not hit the line segment properly. But what we can do instead is, we put a small margin $$\epsilon$$ around the line and check the orthogonal distance $$|\mathbf{m}|\leq\epsilon$$:

Now the two points of the line form a vector $$\mathbf{b}=\mathbf{p}_2 - \mathbf{p}_1$$ and the first point of the line and the point to be hit-tested form another vector $$\mathbf{a}=\mathbf{p} - \mathbf{p}_1$$.

$$\mathbf{m}$$ is the orthogonal projection of $$\mathbf{a}$$ onto the normal vector $$\mathbf{n}=\mathbf{b}^\perp$$. Since we only need the length $$m$$ of $$\mathbf{m}$$, we can state

$m^2 = (\mathbf{a}\cdot\hat{\mathbf{n}})^2=\frac{\left(\mathbf{b}^\perp\cdot\mathbf{a}\right)^2}{\mathbf{b}\cdot\mathbf{b}}$

The sufficient condition is then that the length of the margin $$|m| \leq\epsilon$$ (that’s why we work with $$m^2$$), where $$\epsilon$$ is the maximum activation range of the margin. What is missing is a check for line-endings. The easiest way is to say that $$\mathbf{a}\cdot\mathbf{b}\geq 0$$ to state that the angle between $$\mathbf{a}$$ and $$\mathbf{b}$$ may not surpass $$90^°$$. The last test is, that the length of the orthogonal projection of $$\mathbf{a}$$ onto $$\mathbf{b}$$ not surpasses the length of the vector $$\mathbf{b}$$ between point $$\mathbf{p}_1$$ and $$\mathbf{p}_2$$, or

$\begin{array}{rrl} \Leftrightarrow & \left|\mathbf{\frac{\mathbf{a}\cdot\mathbf{b}}{\mathbf{b}\cdot\mathbf{b}}}\mathbf{b}\right|&\leq|\mathbf{b}|\\ \Leftrightarrow & \left|\mathbf{\frac{\mathbf{a}\cdot\mathbf{b}}{\mathbf{b}\cdot\mathbf{b}}}\right|\cdot |\mathbf{b}|&\leq|\mathbf{b}|\\ \Leftrightarrow & \mathbf{\frac{\mathbf{a}\cdot\mathbf{b}}{\mathbf{b}\cdot\mathbf{b}}} &\leq 1\\ \Leftrightarrow & \mathbf{a}\cdot\mathbf{b} &\leq \mathbf{b}\cdot\mathbf{b}\\ \end{array}$

The final hit-test condition for a point and a line-segment is then:

$\text{hittest}_{LP}(L, P):= 0\leq\mathbf{a}\cdot\mathbf{b} \leq \mathbf{b}\cdot\mathbf{b} \land m^2 \leq\epsilon^2$

Hit-test: Circle and Circle

Given two circles $$C_1$$ and $$C_2$$ with their center points $$\mathbf{p}_1$$ and $$\mathbf{p}_2$$ and their radii $$r_1$$ and $$r_2$$, we can determine the distance $$d$$ between the two circles with:

$d = |\mathbf{p}_2 - \mathbf{p}_1|$

The Hit-test condition is then if the distance is smaller than the sum of the two radii:

$\text{hittest}_{CC}(C_1, C_2):= d \leq r_1 + r_2$

function hittestCC(C1, C2) {

let dx = C2.x - C2.x;
let dy = C2.y - C2.y;
let ar = C1.r + C2.r;
return dx * dx + dy * dy <= ar * ar;
}

Hit-test: Rectangle and Rectangle

Given two rectangles $$R_1$$ and $$R_2$$ defined as the upper left points $$\mathbf{a}_1$$ and $$\mathbf{a}_2$$ and the bottom right points $$\mathbf{b}_1$$ and $$\mathbf{b}_2$$, we require the following properties to be true:

• Left edge of $$R_1$$ has to be left to the right edge of $$R_2$$.
• Right edge of $$R_1$$ has to be right to the left edge of $$R_2$$.
• Bottom edge of $$R_1$$ has to be below the top edge of $$R_2$$.
• Top edge of $$R_1$$ has to be above the bottom edge of $$R_2$$.

which is

$\text{hittest}_{RR}(R_1, R_2):= \mathbf{a}_2^{X} \leq \mathbf{b}_1^{X} \land \mathbf{a}_1^{X} \leq \mathbf{b}_2^{X} \land \mathbf{a}_2^{Y} \leq \mathbf{b}_1^{Y} \land \mathbf{a}_1^{Y} \leq \mathbf{b}_2^{Y}$

function hittestRR(R1, R2) {

return R2.x1 <= R1.x2 && R1.x1 <= R2.x2 && R2.y1 <= R1.y2 && R1.y1 <= R2.y2
}

Hit-test: Rectangle and Circle

Given a rectangle $$R$$ defined by the upper left point $$\mathbf{a}$$ and the bottom right point $$\mathbf{b}$$, and the circle $$C$$ defined by its radius $$r$$ and position $$\mathbf{c}$$, the hit-test can be formalized by the distance between $$\mathbf{c}$$ and the closest point $$\mathbf{p}$$ on the rectangle. The closest point on the rectangle can be found using the clamp function of point $$\mathbf{c}$$ within the rectangle dimensions:

function clamp(x, min, max) {
return Math.min(Math.max(x, min), max);
}

function collideCircleRect(C, R) {

let closeX = clamp(C.x, R.x1, R.x2); // R.x1 <= C.x <= R.x2
let closeY = clamp(C.y, R.y1, R.y2); // R.y1 <= C.y <= R.y2

let dx = C.x - closeX;
let dy = C.y - closeY;
return dx * dx + dy * dy <= C.r * C.r;
}

Performance Considerations

Depending on the used method and the size of the problem, it can be a good idea to put a rectangle on top of the objects area and check if something happening there. If it does, the more detailed method can be used, but for every other case we save costly computation time.

If objects get really complicated, it could be a good idea to draw all objects in a monochrome color space on a hidden canvas and use it as a lookup table.

« Back to Book Overview