Robert Eisele
Engineer, Systems Architect and DBA

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\\=& \langle(\mathbf{c} - \mathbf{p})\cdot(\mathbf{c} - \mathbf{p})\rangle\leq r^2\end{array}\]

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}\]

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{\langle\mathbf{a}\cdot\mathbf{b}\rangle}{\langle\mathbf{b}\cdot\mathbf{b}\rangle}\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 \(\langle\mathbf{b}\cdot\mathbf{c}\rangle\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\langle\mathbf{b}\cdot\mathbf{c}\rangle\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_3}\) to be tested. A typical use case of \(\mathbf{p_3}\) 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 using vector \(\mathbf{m}\):

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}_3 - \mathbf{p}_1\). Point \(\mathbf{p}\) is found by the orthogonal projection of vector \(\mathbf{a}\) onto vector \(\mathbf{b}\) plus the original point \(\mathbf{p}_1\) as position vector and vector \(\mathbf{c}=\mathbf{p} - \mathbf{p}_1\) lies between the first point of the line and the newly constructed point \(\mathbf{p}\):

\[\mathbf{p} = \mathbf{p}_1 + \frac{\langle\mathbf{a}\cdot\mathbf{b}\rangle}{\langle\mathbf{b}\cdot\mathbf{b}\rangle}\mathbf{b}\]

The margin vector \(\mathbf{m}\) is then

\[\mathbf{m} = \mathbf{a} - \mathbf{c}\]

The necessary condition is then that the length of the margin \(|\mathbf{m}| \leq\epsilon\), where \(\epsilon\) is a maximum activation range of the margin.

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

\[\text{hittest}_{LP}(L, P):= |\mathbf{m}| \leq\epsilon\]

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\]

Hit-test: Rectangle and Rectangle

Hit-test: Bezier curve and Point

Hit-test: Triangle and Point

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.