I've been studying this:
https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js
and I believe I understand the general idea about quad trees, although I do have two questions about how they work, and the implementation above:
Wouldnt you have to rebuild the entire tree every several ms? In Javascript wouldnt this be extremely slow to do?
If I have something like this: http://davzy.com/screenshots/skitched-20120318-180324.png, then its easy enough to find the other dots in the same quad but I have a rectangle that hits 3 different quads, is there a way I can make it display as a child of all 3 of those quads?
On 144 of the above example it says this Node.prototype._classConstructor = Node;, I'm just curious what's going on. I thought prototype was a way to define a function or variable for future use within a class, so I'm not sure what this line does.
The quadtree is an approach to image representation based on successive subdivision of the array into quadrants. In essence, the array is repeatedly subdivided into quadrants until blocks are obtained (possibly single pixels) which consist of entirely the same type of pixels.
Quadtree is a way of partitioning space so that it's easy to traverse and search. A quadtree recursively partitions two-dimensional space into squares, dividing each square into four equally-sized squares. Each distinct data point exists in a unique leaf node; Coincident points are represented by a linked list.
The most basic way to approach this type of 2d collision detection is to utilize a concept known as Axis-aligned bounding box. Axis-aligned bounding box, or AABB, detects if two non-rotational polygons are overlapping each other.
Two forms of collision detection: Continuous: very expensive. Simulate solid objects in real life. Discrete: objects will end up with penetrating each other.
1. Wouldnt you have to rebuild the entire tree every several ms? In Javascript wouldnt this be extremely slow to do?
I suppose that depends on what you're using it for; but yes, the author's collision-detection example in his blog post about his QuadTree implementation will clear the tree and repopulate it roughly 24 times per second (so, about once per 40 ms). You can judge for yourself whether that's "extremely slow"; on my machine it looks quite smooth. (And even if not, I would expect the rebuilding of the QuadTree to actually be cheaper/faster than the redrawing of all of the circles on the canvas.)
2. […] I have a rectangle that hits 3 different quads, is there a way I can make it display as a child of all 3 of those quads?
I'm not sure what you mean by "display", but: if you call the constructor with the pointQuad
parameter set to false
, then items are two-dimensional (i.e., they have width
and height
in addition to x
and y
), and every item will be a child of the smallest quad that it fits completely inside. In your example, since the rectangle crosses the vertical midline of the canvas, it will be a direct child of the root quad.
3. On 144 of the above example it says this Node.prototype._classConstructor = Node;, I'm just curious what's going on. […]
The Node
"class" has a "subclass" named BoundsNode
(used when the items are two-dimensional), and BoundsNode.prototype._classConstructor
is set to BoundsNode
(which overrides the inherited Node.prototype._classConstructor
). This allows Node
's subdivide
method to write new this._classConstructor(...)
in order to construct a new BoundsNode
if this
is a BoundsNode
, and a new plain Node
if this
is a plain Node
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With