Jump to content
  • Advertisement
Sign in to follow this  
stuh505

Point-Curve distance?

This topic is 4334 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Anyone know how a quick way to compute the shortest distance between a cubic bezier curve an arbitrary point? edit: I don't think there is an easy direct solution so I'm just going to do without this func [Edited by - stuh505 on January 31, 2007 3:55:03 PM]

Share this post


Link to post
Share on other sites
Advertisement
There is a way, but it isn't quick or simple. If you have the polynomials X(t) and Y(t) describing the position of the curve as a function of time, and the location of the point (x,y), then you can find the minimum of the following polynomial:

(x - X(t))2 + (y - Y(t))2

A cubic equation squared is a degree-6 polynomial, so the derivative is a quintic equation. Unfortunately, there is no closed-form solution for finding the roots of anything higher than a quartic, so you're stuck using a numerical method. Newton-Raphson is good, as long as you can come up with some good guesses.

Then again you're probably better off just dropping this functionality altogether if you don't really need it :)

Share this post


Link to post
Share on other sites
Yeah, I wanted to make a whole bunch of checks. Once I started googling up papers discussing "efficient numerical methods" for solving the problem I realized that wasn't the way to go. Now I'm just rendering it into a buffer and then checking the buffer bits when I want to do a comparison. I only need to know if it's within a minimum distance. This works perfectly well. If I needed to actually know the distance value I could render it and then do a pseuo-euclidean distance transform.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!