Crash (infinite loop?) in visualize_qtree

[oliver-foggin]

I don't know the cause of this yet but there is a crash in visualize_qtree.

I think it's hitting an infinite loop somewhere but I haven't been able to find where yet. It seems to happen near the top of the canvas when you only have one point near the edge of the circle.

Just adding this as a placeholder. Will continue looking for the infinite loop.

EDIT

OK, found it.

In quadtree.js, closest function.

If point has 0 points with the maxDistance then, during the binary search the inner radius will get asymptotically close to maxDistance but limit is never adjusted and so the search will never end.

Creating a PR for it now.

[oliver-foggin]

OK, not creating a PR because I don't know how to make this binary search work. Haha 😄

The search is even difficult to describe in words. Ideally what you want is the smallest circle at centre point.x, point.y that contains at least count points (excluding point itself).

But... you could have arbitrarily many points at any distance and even at the same distance from point. So you're not looking for the smallest circe with exactly count points.

If your current smallest circle has more than count points. Then you could go smaller to get closer to count. But potentially a tiny change (infinitesimal, even) could drop you down to 0 if all the points at at the exact radius of the current circle. Or, a big change might not reduce the number at all (you might have more than count points at the exact same place as point).

My closest "best guess" is to start small with a radius of say maxDistance * 0.5^10 and then reduce the power each loop (effectively doubling the radius of the circle) until you have a circle that contains at least count points.

If you get to maxDistance radius then that's because you didn't find a smaller circle with count points in it.

[oliver-foggin]

I think another approach to this would be to use a k-nearest-neighbours algorithm instead of using a range query lookup.

I don’t know how to do that but I’ll give it a go. 😃

[oliver-foggin]

Woop! 🎉

OK, got the nearest neighbors algorithm working and it's nice and fast 😄

Did spot an inconsistency with the Rectangle though. The w, h properties seem to be used in two way. One is that they are the width and height from the center of the rect, the other is the full width and height.

Going to assume it is the latter though as that's what the tests show 😄

Expect, when using left, right, top, bottom to determine if a Rect contains a point some other tests fail.

Will fix those too 😄

But for now... it's 1am so it's bed time 😴

[oliver-foggin]

OK... it's still not working and one of the issues is due to the inconsistency of how Rectangle width and height are used.

I think I'll make a PR for that first and then work with the rest. 😄

[crhallberg]

Sorry if you've felt like you've been talking in a vacuum! I'd like to hear more about your approach!

The binary search can have issues with the outer limits and if it's also hard to understand, I'd be interested in using a different approach!

[crhallberg]

I looked into it more and you're exactly right! If you provide a maxDistance and it doesn't contain enough points -> infinite loop.

I've created a fix for this problem until we can get a closer look at your search method. How does this sound to you?

https://github.com/CodingTrain/QuadTree/compare/master...crhallberg:closest-fix?expand=1#diff-ca9c3c06805e72822546dc584c96cf26R310-R316

[oliver-foggin]

@crhallberg hey, thanks for the reply. For some reason I don't seem to be getting emails from Github so apologies for not replying sooner. That looks like a good fix for now 👍

[oliver-foggin]

RE the k-nearest neighbours. I think the first thing to fix is the inconsistency with the usage of w and h. Watching the video, you use w and h to represent the distance from the centre point to each edge. However, it looks like shortly after that there was a contribution that used it to mean the distance from one side to the other.

This causes some issues when trying to dive into the algorithm to adjust it a bit but there are lots of tests that are built working around the inconsistency so it's difficult to unpick it as changing it either way breaks a lot of the tests.

😄

[oliver-foggin]

For some info... k-nearest-neighbours iterates over the structure of the quad tree building a list of "neighbours" instead of using a range lookup.

If it finds a node closer than any of the current "neighbours" then it adds that to the list and then removes the furthest one.

It can skip a quadrant (and all of its children) if the quadrant is further away than all of the current neighbours as none of its nodes will be closer than any of the neighbours.

I think it's important too to remove the overlap of each sector. Instead of using <= and >= at every border it should use <= and >. That way if a node's position is equal to the border it only has one quadrant that is valid.

[crhallberg]

Hey, @oliver-foggin! I'm sorry for being away for so long. I was finally able to fix some permissions errors that was preventing me from merging any pull requests!

In review of #51, I wanted to check back in on this. Do you still have your k-nearest-neighbor code? I'd be interested to see the approach, since I think my binary search query method might be a bit hard to grasp for the intent of this library.

[oliver-foggin]

@crhallberg hey, I never got to the point of having the k-nearest-neighbours code working due to the width & height inconsistencies in the repo.

The k-nearest-neighbours algorithm was almost working but because it relies on knowing the width and height of each node it was getting confused and so never actually returned the correct values.

I had a look into fixing them but got to the point where there were too many tests built on top of them and so they would all need updating.

Def happy to have a look at it again. I think the main task first would be to fix the inconsistencies so that "width" and "height" have a definite meaning within the repo.

I'm happy to have a look at that too but it will be a fairly big update not functionally, just due to the number of changes required.

[oliver-foggin]

Let me have a play and see if I can come up with something.

[oliver-foggin]

Regarding the inconsistency... you can see it here...

get left is defined as ...

x minus half the width.

Whereas the check for if a point is inside the left boundary is ...

x minus the full width.

Likewise for top, right, and bottom.

[oliver-foggin]

Just linking for completeness...

Here's the PR for the fix of the width/height issue.

#57

[crhallberg]

Thanks for cleaning up both the inconsistencies (width vs. width/2 and also <= vs <)!

I'm going to give this a closer look but I think the PR is almost set. I left a couple of comments.

[crhallberg]

New use of k-nearest fixes the infinite loop!