Rich-Harris / pancake

Experimental charting library for Svelte
MIT License
1.29k stars 61 forks source link

Add max_levels parameter to Quadtree algorithm #27

Closed MarceloPrado closed 3 years ago

MarceloPrado commented 3 years ago

This PR fixes #24.

The current Quadtree implementation does not have any limits on how many sub-trees it can have. This causes an infinite recursion problem, whenever you're plotting two or more lines. From what I understood, two points close enough to another causes the algorithm to recursively split them. Because there's no limit, it keeps splitting the nodes until it crashes.

The current fix adds a max_levels parameter to the Quadtree implementation, controlling how deep the tree could grow. Initially, I thought this was a hotfix, not being the correct way to solve this problem. However, looking at other libraries such as Quadtree JS, it looks they also fixed this issue in a very similar way.

I created a new prop maxLevels for the Quadtree component, allowing the users to override the default value for this property. For my use case, 10 proved to be the minimum value that gave the results I needed, therefore, it currently defaults to 10.

Example Usage

Rich-Harris commented 3 years ago

Thank you! There's actually a much simpler fix, which is to discard coincident points — implemented in #37 — so I'll close this