Angular 2 Typescript Math Toolkit Point-In-Circles Demo
The point-in-circles problem is a classic from computational geometry. In short, the challenge is to efficiently detect if a point is inside a circle. Typical application of the test is to specifically identify a number of circles from a large collection that contain a point.
The circle collection is most likely distributed across a rectangular space in a game area, learning application, etc. The area covered by any single circle relative to a typical viewing area is often small. So, it is reasonable to presume that in a collection of circles, the majority case is that most circles will NOT contain a single point.
In choosing an algorithm, the first approach is to make the test for an individual circle as efficient as possible. The classic algorithm is to compute the distance between the point and circle center. This distance is compared to the circle radius to determine whether or not the point is inside the circle. It may seem that for n circles, n distance computations are required, each of which involves a (relatively expensive) square root.
In reality, the square root is not necessary, but we can do even better in terms of optimizing the test. Based on the above observations, it pays to optimize the test to prove that the point is outside the circle as soon as possible. This is the approach taken in the Typescript Math Toolkit CircleUtils class. The point is tested against the axis-aligned bounding box (AABB) of the circle. Based on either the x- or y-coordinate of the point, the point could be deduced as outside the circle in a best-case of A+C, where A is the cost of an add (or subtract) and C is the cost of a typical comparison (i.e. <, ==, !=). There is memory cost to fetch operands such as the point coordinates, circle center, and radius. These are constant per test.
In the worst case, the point could be disqualified as being inside the circle in 4(A+C) since the point y-coordinate is tested before the x-coordinate. If the bounding-box test passes, then the algorithm proceeds onto the distance-squared. In the absolute worst case, inclusion is proved or disproved in 4(A+C) + 3(A+M) + C (where M is the cost of a multiply). That is relatively efficient and average case is far better than worse case, so an O(n) sweep through the circle collection is pretty hard to beat for a typical interactive application.
If n becomes very large, memory is not a consideration, and a very efficient data structure is available that supports fast insert/delete with favorable average search cost, then it is possible to improve upon the above approach. This is particularly true if the circles do not move or move relatively infrequently so that the space may be partitioned into quadrants. Four data structures would be used to maintain a list of circles that overlap each quadrant. Of course, it is possible that one circle may overlap multiple quadrants and thus be repeated in multiple lists. It is relatively simple to compute the quadrant of the point and then only test circles that overlap the same quadrant as the point. The complexity of the test is O(k) where k < n (on average). This reduction, however, has additional bookkeeping cost. Every time a circle moves, its quadrant overlap must be re-computed and the quadrant lists may need to be updated. This can be well worth the overhead if the circles never move or switch quadrants infrequently.
There is a hybrid approach that is still O(n) but can be faster for situations where a small number of circles move per simulation step. Every time a circle moves, its quadrant overlap information is updated. This is done based on the AABB instead of the actual circle geometry, which makes the update rather efficient although slightly inaccurate.
First, compute the quadrant location of the point. Then, for every circle in the collection, query whether or not it overlaps the point quadrant. If not, skip the point-in-circle test entirely. If the circles are spread out throughout the visible space, a large number of them can be eliminated from consideration at a straight cost of C. Even a significant number of those inside the point quadrant will be eliminated from consideration with the above-mentioned average cost. So, while O(n), the algorithm cost is largely bounded by comparisons. The total effectiveness depends on how many circles move and how often.
This algorithm and the first algorithm mentioned at the beginning of the blog post are simulated in an Angular 2 demo. Several (alpha) classes from the Typescript Math Toolkit are provided. These include:
Circle (from the geometry package)
CircleFactory (from the geometry package)
ApproxEqual (from the utils package)
GeomUtils (from the utils package)
CircleUtils (from the utils package)
The Circle manager automatically performs the quadrant updates required for the hybrid algorithm, above.
After building and then running the Angular 2 demo, an introductory view is presented. Click on the ‘Begin’ button to advance to the simulation. Yes, well, you are right. That’s really not completely necessary, but it was a good excuse to experiment with imperative routing control in Angular 2
Select either Algorithm 1 (straight O(n)) or Algorithm 2 (hybrid) and then ‘Start’ to begin a simulation. 100 circles are used in this demo and EaselJS is used as a Canvas drawing engine. Click ‘End’ to terminate the simulation. Switch algorithms if you like and run a new simulation.
Here is a screen shot of a simulation of Algorithm 2.
The point is represented visually by a red circle with a 5px radius. There will be cases where the red circle is barely inside a circle, but the point itself is not. Circles that contain the point are drawn in red until the next simulation step. The point takes an approximate random walk through the visible space. Feel free to modify the simulation and the implementation of each algorithm as you see fit. The code is supplied with the intent that it will be modified and improved
The current demo uses Angular 2, beta 11. As mentioned above, EaselJS is used as a Canvas drawing engine, so the demo also illustrates how to use a third-party JS library inside an A2/Typescript application.
Yes, yes, code, code, you want it now. I get it Just point your friendly, neighborhood browser to this Github repository and I hope you find something useful and instructive from the demo.