Add function to query the closest site to a given point

[RudyTheDev]

This has performance implications. For example, building a square grid on top of the generated diagram, I might want to check each square tile against the diagram.

• Basic query logic
• Brute force
• KD tree
• Better KD tree algorithm
• Better spatial algorithm

[DeeCeptor]

This has performance implications. For example, building a square grid on top of the generated diagram, I might want to check each square tile against the diagram.

I'm needing this exact same functionality.

Did you implement this yourself?

[RudyTheDev]

Hi,

I added a GetNearestSiteTo(x,y) method for this.

I tried to implement an efficient a KD-tree algorithm for this, but it is only more efficient long-term with lots of lookups (like 1000s of points and 1000s of lookups); otherwise brute force is basically faster. I will probably look into some other faster spatial lookup algorithms, but I don't see anything I could easily adapt after a quick search around.

[DeeCeptor]

Thanks for the info.

That's what I ended up doing. Each VoronoiSite is inserted into a KDTree ( https://github.com/viliwonka/KDTree ). I haven't done profiling yet to know how efficient this is, but I do have 800 VoronoiSites, and need to make thousands of queries using the tree to find the nearest VoronoiSite.