Skip to content
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

Add method to query for nearest point on spline to a point #14

Open
ecurtiss opened this issue Jun 3, 2024 · 1 comment
Open

Add method to query for nearest point on spline to a point #14

ecurtiss opened this issue Jun 3, 2024 · 1 comment
Labels
feature A new feature

Comments

@ecurtiss
Copy link
Owner

ecurtiss commented Jun 3, 2024

This ends up being a minimization problem on a 6th-degree polynomial. If the user is tracking the nearest point over time, then starting the minimization from a nearby reference point could give quick convergence with a basic algorithm. Otherwise, we could find all roots of the derivative in [0, 1] using http://www.cemyuksel.com/research/polynomials/.

@ecurtiss ecurtiss added the feature A new feature label Jun 15, 2024
@ecurtiss
Copy link
Owner Author

On second thought, the distance function is actually discontinuous when you take the query point as a parameter. Hence, trying a root-find at the previous time could give you the next closest point, but it is not guaranteed.

Here's an idea for doing a nearest point query that considers all segments:

  1. Broad phase: For each segment, compute the smallest distance and largest distance from the segment's bounding box to the query point. This gives an upper bound and a lower bound on the distance from the segment to the query point. Discard any segments whose lower bound is greater than the smallest upper bound. Lastly, cache the bounding boxes.
  2. Narrow phase: For every segment that survives the broad phase, do the root find.

Thoughts:

  • Since we can cache the bounding boxes, it is probably worth our time to write a tighter bounding box algorithm.
  • We could still start with a root-find at the previous closest time, as this would give an upper bound on the distance. We could use this for the broad phase if it's smaller than the smallest upper bound from the bounding boxes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature A new feature
Projects
None yet
Development

No branches or pull requests

1 participant