-
Notifications
You must be signed in to change notification settings - Fork 526
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
spatial/kdtree: Go generics ideas based on user experience #1799
Comments
I'd be happy for this (and the other spatial containers) to be rewritten as type-parameterised code. It would be in the v0.12 milestone. For your specific case, I'd suggest making the distance compares between triangle centers (first convert your triangles to cows and then convert those to idealised point masses, which is already a solved problem). Alternatively, you can choose either the closest or furthest vertex; whichever is better for your use case. |
Awesome! So does adding a second type parameter |
Yes, I think so. I'd like to see an implementation. |
Not entirely happy with how it turned out. Feel like there are some knobs that could be turned
|
Props
Let me start by saying I am amazed by the kdtree implementation. I can't believe how fast I was up and running making a kdtree based SDF (didn't work perfect, but it did things!) I had NO idea what kdtree was before I started using this package- my knowledge of kdtrees was limited to gimmicky 80's movies CGI.
What are you trying to do?
I am attempting to transform a mesh into a signed distance function. To do this I must have a data structure that allows me to get the triangles of the mesh closest to a point in space in a reasonable amount of time.
What did you try?
Using current kdtree.
How does Gonum not allow you to achieve your goal?
The issue I ran into was that the current kdtree implementation was more suited to problems where
kdtree.Comparable
(the base data structure) was the representation of a point of Dim dimensionality.When working with a Triangle as a Comparable type there is a lot of superfluous data that is thrown around:
BoundingBox
is composed of Min and MaxComparable
s, which are also triangles. These should be pointskdtree.Tree.Nearest(Comparable)
should take a point in my case- which meansComparable.Distance()
should also take a point as an argument if my rudimentary reasoning is correctCompare(Comparable, Dim) float64
I'm unsure how this is implemented in my case. Looking at the documentation for this method it seems very likely leaving it as Comparable is the soundest choice. Maybe worth adding aComparePoint()
method for the reduced case?I'll end the issue on this flat not since I'm very new to the advanced data structure scene. These are just loose ideas we can discuss.
Given these changes, the kdtree types could look something like this if written with Go Generics (click to display):
The text was updated successfully, but these errors were encountered: