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.

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 <https://en.wikipedia.org/wiki/Euclidean_distance Euclidean distance> 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:

x0y0 = [-2 -5];
  P = [0.5 3 -5];
  D = distance2polynomial(P,xy)
  D =
          1.89013819497707

(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

144 Solutions
27 Solvers

Last Solution submitted on Apr 23, 2023

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

John D'Errico on 30 Oct 2016

I'm enjoying these creative solutions.

Solution Comments

Show comments

Problem Recent Solvers27

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 43642. Euclidean distance from a point to a polynomial

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers27

Suggested Problems

More from this Author4

Problem Tags

Community Treasure Hunt

Problem 43642. Euclidean distance from a point to a polynomial

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers27

Suggested Problems

More from this Author4

Problem Tags

Community Treasure Hunt

Players