QuadTree: Crash (infinite loop?) in visualize_qtree

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.

About this issue

Original URL
State: closed
Created 4 years ago
Comments: 16 (11 by maintainers)

Most upvoted comments

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 on Mar 8, 2021

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

oliver-foggin on Mar 7, 2021

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 on Jun 15, 2020