Problem 43642. Euclidean distance from a point to a polynomial

Created by John D'Errico

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A not uncommon problem in the area of computational geometry is to find the closest point to a straight line from a given point, or the distance from a point to a line. As you might expect, there is a simple formula for those things.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As an extension, I decided one day to write a tool that would compute the distance from a point to a general polynomial function in the (x,y) plane. That is your problem here:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given a point (x0,y0), and a polynomial in the form y=P(x) where the function P is defined by the coefficients of a polynomial, you need to compute the minimum</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Euclidean_distance\"><w:r><w:t>Euclidean distance</w:t></w:r></w:hyperlink><w:r><w:t> to that polynomial. So you need to find and return the minimum distance in the (x,y) plane between the point (x0,y0), and the function y=P(x).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The function P will be passed in as the coefficients of a polynomial in standard MATLAB form, thus with the highest order coefficient first in a vector, like that generated by polyfit, and used by polyval. (P might be as simple as a constant function.) The point in question will be passed in as a vector of length 2, thus [x0,y0].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As test case for you to check your code, the distance from the point (-2,-5) to the curve y=x^2/2+3*x-5 should be:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[x0y0 = [-2 -5];\nP = [0.5 3 -5];\nD = distance2polynomial(P,xy)\nD =\n 1.89013819497707]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>(Be careful plotting these curves in case you want to plot your solution. The command \"axis equal\" is a good idea.)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The symbolic TB tells me the distance is 1.8901381949770695260066523338279..., but I'll allow some slop in your solution, since you may have chosen a different algorithm than the one I chose. You should expect to provide at least 13 correct significant digits in the solution.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Disclaimer: I'm not really sure why anyone needs such a code, which is why I've not posted my solution on the FEX. Anyway, my solution is a pretty one that I thought might make a fun Cody problem, and I wanted to see how others might approach the problem. I expect that my reference solution will score poorly for Cody purposes, since it is carefully coded, complete with error checks, and returns more than just the minimum distance.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

A not uncommon problem in the area of computational geometry is to find the closest point to a straight line from a given point, or the distance from a point to a line. As you might expect, there is a simple formula for those things.As an extension, I decided one day to write a tool that would compute the distance from a point to a general polynomial function in the (x,y) plane. That is your problem here:Given a point (x0,y0), and a polynomial in the form y=P(x) where the function P is defined by the coefficients of a polynomial, you need to compute the minimum <a href = "https://en.wikipedia.org/wiki/Euclidean_distance">Euclidean distance</a> to that polynomial. So you need to find and return the minimum distance in the (x,y) plane between the point (x0,y0), and the function y=P(x).The function P will be passed in as the coefficients of a polynomial in standard MATLAB form, thus with the highest order coefficient first in a vector, like that generated by polyfit, and used by polyval. (P might be as simple as a constant function.) The point in question will be passed in as a vector of length 2, thus [x0,y0].As test case for you to check your code, the distance from the point (-2,-5) to the curve y=x^2/2+3*x-5 should be:<pre class="language-matlab">x0y0 = [-2 -5];
P = [0.5 3 -5];
D = distance2polynomial(P,xy)
D =
 1.89013819497707
</pre>(Be careful plotting these curves in case you want to plot your solution. The command "axis equal" is a good idea.)The symbolic TB tells me the distance is 1.8901381949770695260066523338279..., but I'll allow some slop in your solution, since you may have chosen a different algorithm than the one I chose. You should expect to provide at least 13 correct significant digits in the solution.Disclaimer: I'm not really sure why anyone needs such a code, which is why I've not posted my solution on the FEX. Anyway, my solution is a pretty one that I thought might make a fun Cody problem, and I wanted to see how others might approach the problem. I expect that my reference solution will score poorly for Cody purposes, since it is carefully coded, complete with error checks, and returns more than just the minimum distance.

Solve

Solution Stats

88 Solutions
24 Solvers

Last Solution submitted on Sep 09, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

John D'Errico on 30 Oct 2016

I'm enjoying these creative solutions.

Solution Comments

Solution 1040753

1 Comment

1 Comment

James on 31 Oct 2016

John, I just tried your file exchange solution out of pure curiosity. Your guess is correct; it does score poorly. I also got the error "You may not use the command(s) builtin in your code" for the test cases. All I did was change only the first line to call the function and the variable names with no other checking. I'll do some real work on it now. :-)

Solution 1038560

2 Comments

2 Comments

Zhengyi on 2 Feb 2018

Will not solution like this be sooo much slower than simple loops?! Short yes, efficient no.

Zhengyi on 2 Feb 2018

well, I think I was wrong...This solution is slower if the degree of the polynomial is small but much faster if the degree gets higher...solving polynomials of high degree is really slow with ROOTS.

Problem Recent Solvers24

Problem Tags

Problem 43642. Euclidean distance from a point to a polynomial

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers24

Suggested Problems

More from this Author4

Problem Tags

Problem 43642. Euclidean distance from a point to a polynomial

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers24

Suggested Problems

More from this Author4

Problem Tags

Players