Remove named children

[oliver-foggin]

The named children of the quadtree (i.e. northeast, northwest, southeast, southwest) are only ever used internally to the tree itself and anything done to one of the children is always done to all four of them; this adds clunkiness to it where you have repeated calls to the same function on each of the children.

For example, in the draw method you have...

show(qt.northeast);
show(qt.northwest);
show(qt.southeast);
show(qt.southwest);

By removing these and instead using an array called children it allows you to compress a lot of this repetition while not losing out on the readability.

The above would become...

qt.children.forEach(show);

The query function becomes significantly simpler. The original code...

  query(range, found) {
    if (!found) {
      found = [];
    }

    if (!range.intersects(this.boundary)) {
      return found;
    }

    for (let p of this.points) {
      if (range.contains(p)) {
        found.push(p);
      }
    }
    if (this.divided) {
      this.northwest.query(range, found);
      this.northeast.query(range, found);
      this.southwest.query(range, found);
      this.southeast.query(range, found);
    }

    return found;
  }

becomes...

query(range) {
  if (!range.intersects(this.boundary)) {
    return [];
  }

  return this.children
    .reduce((a, c) => a.concat(c.query(range)), this.points.filter(p => range.contains(p)));
}

I have also moved the creation of the sub-Rectangles into the Rectangle class so you can now do this.boundary.ne() to create the northEast boundary to pass into the child quadTree.

I guess a lot of this is personal preference and I know this is an old repo but I've been really enjoying the series during the recent isolation and thought I'd contribute 😄

Thanks

N.B. There is one bit of this change that I don't like and that's the serialization into and out of JSON. The current method writes out to the obj.ne, obj.nw and so on. I have kept this for backwards compatibility with people using this repo but it means that the order of the children being defined needs to be correct. The order I went with is the same order that the children were originally defined (ne, nw, se, sw). However, there is nothing (other than tests) to stop this.

Perhaps this could be improved by either:

• defining the order of the directions in some other place to remove the manual indexing of arrays.
• removing the ne, nw, etc... from the JSON serialization and instead creating a JSON array of the children.

[crhallberg]

Thank you for this work! I think adding children as a convenience attribute would be really helpful.

The concerns I have are all about the nature of this particular project as a learning tool. What would you think of a middle ground between the named children and your array approach? We can keep the named children AND save them in an array. I think that would make the JSON exporting and other parts that are less readable with an array easier to understand.

Does that make sense?

[crhallberg]

Hey! I've gotten upgraded permissions to the repository so I'm trying to do some clean up! Any interest in getting this up to date?

[oliver-foggin]

@crhallberg yeah definitely up to getting this back up and running.

Let's get the width/height stuff in first and then the k-nearest-neighbours.

Then I'll take another look at this. 👍🏻

[crhallberg]

Incorporated into #62, now merged.