timohausmann / quadtree-ts

Quadtree Typescript Implementation
https://timohausmann.github.io/quadtree-ts/
MIT License
125 stars 15 forks source link

Issue understanding example in documentation to retrieve `area` #11

Closed NickyWeber closed 11 months ago

NickyWeber commented 11 months ago

Hey there,

I have some trouble understanding the example given in the documentation. Let's iterate:

import { Quadtree } from '@timohausmann/quadtree-ts';

const myTree = new Quadtree({
    width: 800,
    height: 600,
    x: 0,           // optional, default:  0
    y: 0,           // optional, default:  0
    maxObjects: 10, // optional, default: 10
    maxLevels: 4    // optional, default:  4
});

const rectangle = new Rectangle({
    x: 100,
    y: 100,
    width: 100,
    height: 100
});
myTree.insert(rectangle);

const line = new Line({
    x1: 25,
    y1: 25,
    x2: 75,
    y2: 25
})
myTree.insert(line);

const circle = new Circle({
    x: 100,
    y: 100,
    r: 50
})
myTree.insert(circle);

const area = new Rectangle({
    x: 150,
    y: 150,
    width: 100,
    height: 100
})
const elements = myTree.retrieve(area);

console.log(elements)

Output:

[
  Rectangle {
    x: 100,
    y: 100,
    width: 100,
    height: 100,
    data: undefined
  },
  Line { x1: 25, y1: 25, x2: 75, y2: 25, data: undefined },
  Circle { x: 100, y: 100, r: 50, data: undefined }
]

I have plotted the elements in a simple way to visualize what is happening in my understanding:

Screenshot 2023-11-07 at 19 12 13

The purple area is the query area. I would have guessed only the red rectangle returned but retrieve returns all elements stored.

However, when I change the tree's maxObjects to 1 it works fine.

Am I using the tree in a wrong way?

Thanks in advance

timohausmann commented 11 months ago

Hi, just commenting on your illustration: the coordinates 0,0 is in the top left corner. For Rectangles: the geometry starts top left too.

Does that solve it? Otherwise I can test your example code later today.

timohausmann commented 11 months ago

By the way, to which example do you refer?

NickyWeber commented 11 months ago

In my visualization bottom left is 0,0. I guess it doesn't matter if it's a right hand or left hand coordinate system.

I am referring to the paragraph "Use" in your Readme. It is not stating an outcome, but I am trying to figure out what I should expect and how to use/configure your Quadtree.

timohausmann commented 11 months ago

I guess it doesn't matter if it's a right hand or left hand coordinate system.

true!

It's expected to recieve all elements in this example, because the Quadtree did not split once yet. The option "maxObjects" defaults to 10, so 10 objects will be in the very first node before the "resolution" increases.

Try to add 11 objects and see if it makes sense then.

timohausmann commented 11 months ago

The simple example has maxObjects of 4, check it out (see how it splits only when that number is reached. Before, all elements will always be returned from retrieve): https://timohausmann.github.io/quadtree-ts/examples/simple/

If your issue persists feel free to re-open this issue.

NickyWeber commented 10 months ago

Thanks for replying, that make sense.

So if you query the tree and it returns objects the user still has to test if these objects are actually intersected by the retrieve object?

timohausmann commented 10 months ago

Correct! The Quadtree gives you all objects from intersecting Quadtree-nodes. This reduces the list of potential collisions. But the precise intersections on object-level has to be checked again.