I've been told that a quad tree is the ideal data structure for my game, but I'm having trouble understanding how exactly shapes work within quad trees.
I think I mostly understand how basic (x,y) points and point insertion works in quad trees, and that I could do it on paper.
Here is a JSfiddle of my experimenting with points.
Aside from one case, my tests with points are working as expected.
But my confusion starts when shapes like rectangles are involved. When you are retrieving from a quad tree with shapes, does it check each point of the shape, and what nodes they fall into? And how do shape insertions even work, when it accepts (x,y,width,height) parameters for each shape? Does it use the width/height from the starting point to calculate other corner points, which are then dispensed into appropriate nodes? If an inserted shape spans into four nodes, is that shape's data saved into all four nodes?
And when a retrieval method accepts a shape as the parameter(x,y,width,height), what is actually going on? Is it first seeing what nodes the shape would span to if it were to be inserted, and then retrieve all the objects of those nodes?
I have a JSfiddle working with shapes, but I am utterly confused on the results of my testing. I am getting duplicate objects being returned!
For example, the red square is a drawn equivalent of the parameters I am entering into my retrieval method. I would think that since this red square spans all four nodes, it should return every object in the quad tree! But it doesn't, and I am having trouble rationalizing what it does return. I have a number of other tests that are currently commented out, but you can un-comment and run them to see more confusing results!
As say, if I want to return all points in a quad tree, how would I do that? A retrieve method using a shape the entire size of the bounds? In example, retrieve(0, 0, canvas.width, canvas.height)?
I think a lot of my confusion may stem from a misunderstanding of quad tree terminology. Like, why do they say bounds instead of dimensions, when a "point" has width/height parameters as well? Is it a matter of convention/short-hand, or are they completely different concepts?
Thanks for your time!