1
\$\begingroup\$

I'm developing a 2D ant simulation in JavaScript. I'd like to implement a quadtree to store the positions of ants and other markers. I approximate all of these entities as circles, and I'm only querying for circles that fall within the radius of a query circle.

Most of the things I've read about quadtrees implement rectangular entities/queries very efficiently. Is there a more efficient way of implementing a quadtree given all entities/queries are circular? Otherwise I would plan to store each circle as a square and perform a circular collision check on top of each query result.

\$\endgroup\$
4
  • \$\begingroup\$ Do the object stored move frequently? If so, are you sure(tried regular quad-tree) the cost of maintaining any structure would not massively overshadow the rather cheap circle-circle collision detection? Are the objects more or less distributed evenly or in clusters? \$\endgroup\$
    – wondra
    Sep 29 '20 at 9:06
  • \$\begingroup\$ Circles could be difficult. But I wonder if a hexagonal data structure could work. Hexagons are a pretty good approximation of circles, and they are one of the three regular polygons which can be used to tessellate a 2-dimensional plane. \$\endgroup\$
    – Philipp
    Sep 29 '20 at 11:01
  • \$\begingroup\$ @Philipp, Suppose you called this structure a "Hex Tree". You would need each hexagon node on the tree to be composed of hexagons. Luckily 7 hexagons in a flower shape make a pretty good approximation of a hexagon overall, but even this kind of tree would cover space such that a point near hexagon borders could be inserted in more than one branch on the tree. Maybe you could come up with a clever rule about the hexagon borders to determine which branch the point is in... But that still makes searching the tree for that entry a lot less optimized than a quad tree. \$\endgroup\$
    – Romen
    Sep 29 '20 at 16:25
  • \$\begingroup\$ I wonder if Lp space would be of use here, after all, L1 circle is a square and Linf circle is axis-aligned square... \$\endgroup\$
    – wondra
    Sep 30 '20 at 12:50
2
\$\begingroup\$

I can't recommend a structure that actually implements what you're asking for, but it definitely won't work like a quad tree. It may not be a tree at all and it might not even exist...

A quad tree has a tree structure because each node represents the node above it divided into four quadrants. At any level these four quadrants cover all of the space covered by their parent. Every single point in the 2D space can be inserted at exactly one leaf node somewhere on the tree.

If you try to divide space into circles, you're not going to be able to find a set of circles that cover their parent circle completely and evenly. This geometric problem rules out the possibility that you can store these circles in a tree that will be useful to traverse for collision detection. There will always be points that are either not covered by a circle or covered by more than one circle. (That's bad because it means a point in 2D space either has nowhere to go in the tree or it has more than one place to go!)

Testing whether two circles intersect is simple, but I am not aware of anything simpler than just checking if the distance between them is less than the sum of their radii. You can save some CPU power on so many circle-circle tests by comparing the squared radii and distances and skipping the sqrt calculation.

\$\endgroup\$
2
\$\begingroup\$

As explained in the answer by Romen, there aren't many applicable data structures which are not based on rectangles. But there are a couple other optimizations you can do for circle-circle collisions which could reduce your demand for a more optimized data-structure.

Compare the square of the distance with the square of the radius.

If you want to check if a point is in a circle or if two circles intersect, you have to use the Pythagorean theorem, which in its naive implementation looks like this:

distX = a.x - b.x
distY = a.y - b.y
radiusSum = a.radius + b.radius;

dist = sqrt(distX * distX + distY * distY);
if (dist < radiusSum) {
    // collision
}

Unfortunately, calculating the square-root of a number is a very expensive operation. Fortunately, you can replace that square-root with a much cheaper multiplication in this case. Just compare the squares of the sum of the radiii with the square of the distance:

distSquared = distX * distX + distY * distY;
if (distSquared < radiusSum * radiusSum) {
    // collision
}

Also note that if you want to check if points are within a circle, then you only need to calculate the square of the radius once. If it's always the same circle, you can even cache it. You can also cache the square of the radius sum if you compare objects which all have the same radius.

Check bounding boxes and inner boxes first

While multiplications are cheaper than square-roots, they are still not as cheap as addition and subtraction. But what you can do using only subtraction and addition is comparison between two axis-aligned boxes. So by checking the inner and outer rectangles of the circles first, you can rule out or detect a lot of circle-circle collisions without having to actually check if the radii overlap.

  1. If the bounding squares of two circles do not intersect, then there can not be a collision
  2. If the inner squares intersect, then there must be a collision
  3. If the outer squares intersect but the inner ones do not, then there might be a collision, which means you have to calculate the square of the distance and compare it to the square of the sum of the radii

(note that when you have a game where objects move relatively slow and overlapping objects usually don't remain overlapped, then implementing the 2nd step might not be worth it. When two objects approach each other slowly, then you will in most cases detect a circle-circle collision before you detect an inner rectangle collision)

And if you want to check bounding boxes first...

...then a quad tree can be a useful optimization.

I personally prefer spatial hashes, though. They are easier to implement (IMO) and often work better if objects are relatively evenly distributed. But trees usually adapt better to scenarios where you have to deal with vastly different object densities.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.