Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-07-30 04:52:14

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

distance to a surface

is there any way of calculating the distance to a surface from any giving point?

i.e. lets say you have the surface x^2 - y^2 = 2xz

if i give a random point (1,2,5) is there any way to directly calculate the distance from the surface it is? Obviously such a distance is going to be given along a surface normal, but i couldn't think if it would be even possible to directly calculate points on the surface giving such a normal in a simple way or is there another way of doing this i havn't thought of?

If it was a surface z = f(x,y), i could create a distance function d(x,y) = (f(x,y)-pZ)^2 + (y-pY)^2 + (x-pX)^2

and differentiate and solve for (x,y) such that it equals 0, and choose the minimum of d(x,y) for those values, but thats not exactly a method that can be done generically and for implicit equations too on a computer.

Last edited by luca-deltodesco (2007-07-30 04:58:36)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#2 2007-07-30 10:26:34

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: distance to a surface

Let’s lower our ambitions slightly and ask the simpler question: How to find the shortest distance from any point to a curve in two dimensions?

Even that doesn’t seem quite as straightforward as it sounds. yikes But if we can find a method, I should think it can be extended to the three-dimensional case.

Offline

#3 2007-07-30 11:58:47

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: distance to a surface

luca-deltodesco wrote:

If it was a surface z = f(x,y), i could create a distance function d(x,y) = (f(x,y)-pZ)^2 + (y-pY)^2 + (x-pX)^2

and differentiate and solve for (x,y) such that it equals 0, and choose the minimum of d(x,y) for those values, but thats not exactly a method that can be done generically and for implicit equations too on a computer.

Why should you differentiate? If you have the distance function, just make two "for"-s to estimate the minimum:

double min = VERY_BIG_NUM
for(i=0;i<li;i+=step)
for(j=0;j<lj;j+=step){
d_i_j=d(i,j);
if(d_i_j<min) min=d_i_j;
}

IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#4 2007-07-30 12:15:56

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: distance to a surface

Woah woah woah.  Anytime you can replace an O(n²) algorithm for O(1), do it.  Always use mathematical formulas rather than approximations.

I have to run out to dinner, but I'll make a post on this when I get back or possibly tomorrow morning.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#5 2007-07-30 13:53:52

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: distance to a surface

Ricky wrote:

Woah woah woah.  Anytime you can replace an O(n²) algorithm for O(1), do it.  Always use mathematical formulas rather than approximations.

I have to run out to dinner, but I'll make a post on this when I get back or possibly tomorrow morning.

I agree. But...
When you cannot, the O(n^2) is better than nothing!


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#6 2007-07-31 01:50:46

sky/mathswarrior
Member
Registered: 2007-07-31
Posts: 0

Re: distance to a surface

hmmmm......

Offline

#7 2007-07-31 01:51:17

sky/mathswarrior
Member
Registered: 2007-07-31
Posts: 0

Re: distance to a surface

anybody there???????????????

Offline

#8 2007-07-31 04:02:45

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: distance to a surface

We’re just waiting for Ricky to come back and show us his brilliant method for solving the problem. tongue

Offline

#9 2007-07-31 06:51:49

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: distance to a surface

We CAN implement differentiating a function, then we CAN use Newton's method, for example, for finding the roots and CAN compare them, but these CANs (especially the first one) will require much (MUCH!) more code than my six-lines.


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#10 2007-07-31 07:05:21

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: distance to a surface

well from what i remember, I think the shortest distance to a line or a plane is the distance to a perpendiculr intersection, hence the use of derivatives. Not sure how much that helps though.


A logarithm is just a misspelled algorithm.

Offline

#11 2007-07-31 08:00:46

JaneFairfax
Member
Registered: 2007-02-23
Posts: 6,868

Re: distance to a surface

That’s what I had in mind. For the two-dimensional case:

Let (a,b) be a point and let y = f(x) be a curve. Then the distance r from (a,b) to a point (x,y) on the curve is

To find the shortest distance between point and curve, set

i.e.

Put

Note that there may be places where the curve has a vertical tangent or is simply not differentiable. Let r[sub]2[/sub] be the minimum of all the distances from (a,b) to the places on the curve where the curve is not differentiable. Then r[sub]min[/sub] is the minimum of r[sub]1[/sub] and r[sub]2[/sub].

Now extend this above method to three dimensions.

That was the method I was thinking of. Maybe Ricky has an easier solution. roll

Last edited by JaneFairfax (2007-07-31 08:11:59)

Offline

#12 2007-07-31 08:18:55

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: distance to a surface

Drat.  I misunderstood the question, but then came up with what I thought was a solution.  Turns out it would only work on linear functions...  None the less, here it is.

The tangent plane of z = f(x, y) at (x_0, y_0) is given by:

This can be rewritten as:

Ax + By + Cz + D = 0, where A, B, and D are function of x_0 and y_0.  Note that C = 1.

Now the point we want to get our distance from is P = (P_x, P_y, P_z).  Thus, it must satisfy the equation:

P_x = At + x0
P_y = Bt + y0
P_z = t + z0

But remember, z_0 = f(x_0, y_0)

If you can solve this system in general terms of x_0, y_0, z_0, you will have your answer.  For example, if z = x + y, you come up with the restrictions that P_x + P_z = -y_0 and P_y + P_z = -x_0.

When it comes to collision detection, computer scientist generally use a block approach.  So for example, if you take a human body, you have a block that encompasses the head, the torso, and the legs.  Then, with in these are more blocks.  You have a block around the thigh, the lower leg, and the foot.  And so on until you get down to the size you need for accuracy.  I believe a similar approach can be used to find the distance to "nice" functions.

Take krassi's code, but modify it a bit.  Have step size start very small, and when you find a maximum there, only investigate that part of the function.  It will certainly be better than trying to step over the entire thing.  Another approach can be to vary step size with derivative, although this would be much more complex.  I'll try to give this some more thought and see if I can come up with anything useful.

Edited to add:

We CAN implement differentiating a function, then we CAN use Newton's method, for example, for finding the roots and CAN compare them, but these CANs (especially the first one) will require much (MUCH!) more code than my six-lines.

To measure code by the number of lines is to measure a car by how simple its engine is.

That was the method I was thinking of. Maybe Ricky has an easier solution.

That method is great for the mathematician, useless to the computer scientist.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#13 2007-07-31 11:35:01

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: distance to a surface

Ricky wrote:

To measure code by the number of lines is to measure a car by how simple its engine is.

OK. Let's say simplisity is the one main thing, the other is effectiveness. We may write:
WORTH = SIMPLICITY*EFFECTIVENESS wink
But I want to appologize, because I understood it can be made much simpler from computer-scientist-point of view. We may use approximations of derivatives.
for example here's a code for approx derivation:

double epsilon = VERY_TINY_CONSTANT_BUT_ENOUGH_NOT_TO_CRASH_DOUBLE_LIBRARY
double derivative(function f, double x){
//finds an approx to the f'(x)
return (f(x+epsilon)-f(x))/epsilon;
}

That must give good numberical results. We can make greater, if we use TaylorS, but let's leave this for now.
OK. We have a differentiating method. Now what?
JaneFairfax in her last post pointed the whole 2D theory needed for solving the problem.
We need a tiny generalization to tackle the 3D case.
But first, a little MATH:
Gradient of a two-variable function

is the vector-function
.
A (strongly) nessesery condition for a function to have min or max at point (x,y) is that the gradient at this point be (0,0).
Now first, we should implemet the gradien function forcomputing: express in form:

Now the code is straightforward:

2Dvector gradient(function f, double x, double y){
double f_x_y = f(x,y);
return {(f(x+epsilon,y)-f_x_y)/epsilon, (f(x,y+epsilon))/epsilon};
}

(sorry for the messy c-like language - I hope you understand)
now, for our gradient (u,v), if we take u^2+v^2, it will be null only for (0,0), this can be done by:

double norm( 2dvector v){
return v.x*v.x+v.y*v.y;
}

Here we found an effective function to represent the derivative of the distance from the point to the surface, namely

norm(gradient(f,x,y))

and the question is... to find ALL its roots.
The only way can think of this, requires O(n^2) time...
If you have more effective way, for example O(1), the problem will be solved!


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#14 2007-07-31 20:12:03

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: distance to a surface

i was thinking:

with an implicit surface, f(x,y,z) = 0, a point is 'in' the surface for f(x,y,z) <0 and out for f(x,y,z) > 0, is there any relation to f(x,y,z) for the distance to the surface maybe?

or perhaps, a non O(1) solution, taking the normal and tracing the normal back to the graph for the closest point or something?

Last edited by luca-deltodesco (2007-07-31 20:13:21)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#15 2007-08-01 04:13:54

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: distance to a surface

or perhaps, a non O(1) solution, taking the normal and tracing the normal back to the graph for the closest point or something?

Given a point on the graph, you can calculate the normal and the distance given by that normal.  The problem is, you need to find what normals intersect the point.  I don't believe this can be done in anything but n^2.

with an implicit surface, f(x,y,z) = 0, a point is 'in' the surface for f(x,y,z) <0 and out for f(x,y,z) > 0, is there any relation to f(x,y,z) for the distance to the surface maybe?

Remember that a surface is a function of x and y, and a 3d object is a function of x, y, and z.  But I don't see how the above would give you any useful information.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#16 2007-08-01 04:40:23

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: distance to a surface

actually, my method seems to work:

sin(x) + cos(0.3x) - y = 0

p/px = cos(x) - 0.3sin(0.3x)
p/py = -1

when you click a point (only do it above the graph) it uses the partial derivitaves (normalised as a vector) to step through space until it cross's the graph, then calculates distance from start point. the slower you make it step, the more accurate the distane is.

http://denvish.net/ulf/010807/63500_ite.php

atm, im using euler integration to step through space using the derivitaves, but if i used a better method, it would reduce the number of steps needed for same accuracy again.

I believe that under normal circumstances, this is alot faster than trying to find all (x,y) or (x,y,z) whose normal passes through point to find distance.

Last edited by luca-deltodesco (2007-08-01 04:43:17)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#17 2007-08-01 13:35:43

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: distance to a surface

luca-deltodesco wrote:

actually, my method seems to work:

sin(x) + cos(0.3x) - y = 0

p/px = cos(x) - 0.3sin(0.3x)
p/py = -1

when you click a point (only do it above the graph) it uses the partial derivitaves (normalised as a vector) to step through space until it cross's the graph, then calculates distance from start point. the slower you make it step, the more accurate the distane is.

http://denvish.net/ulf/010807/63500_ite.php

atm, im using euler integration to step through space using the derivitaves, but if i used a better method, it would reduce the number of steps needed for same accuracy again.

I believe that under normal circumstances, this is alot faster than trying to find all (x,y) or (x,y,z) whose normal passes through point to find distance.

Great! Fascinating!
It's really good, but the implict surface is another thing. When you have the equation of the curve - that's the way. And - something little - you said if you click below the curve, the point goes down. So you need to determine in which direction will you go. Because in general the curve may be pretty complex- with twists ect.
And last advice - you can change the step during evaluation. For example, if your point is far enough (f(x,y,z) much greater than 0) then you could use bigger step.

Last edited by krassi_holmz (2007-08-01 13:42:29)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#18 2007-08-01 13:40:57

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: distance to a surface

Quite an interesting method, nicely done.  And it is just as easily expanded to R^n as vectors and derivatives are (i.e. extremely easy).  O(m) solution too, independant of R^n.  I feel like this deserves some kind of official write up.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#19 2007-08-01 13:44:31

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: distance to a surface

Looking at this more, I see a vector field and it might be that differential equations can lead to an exact solution.  I'm quite unsure how to proceed with using diff eq though.  Any thoughts?

On an unrelated note... a fun game to play with that graph is to try to find points which go to the inflection points of the graph.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#20 2007-08-01 13:47:08

krassi_holmz
Real Member
Registered: 2005-12-02
Posts: 1,905

Re: distance to a surface

there will be areas, in which the convergence will be to the wrong direction, but these will be only extremly cases.

Last edited by krassi_holmz (2007-08-01 13:47:38)


IPBLE:  Increasing Performance By Lowering Expectations.

Offline

#21 2007-08-01 16:10:34

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: distance to a surface

I think the problem-

Min{(x-1)²+(y-2)²+(z-5)²}

at the Constraint: x^2 - y^2 -2xz=0

, best describes luca's original question.

And the simple Langrange multiplier method may solve it.
Maybe you guys think it too complicated...

Last edited by George,Y (2007-08-01 16:10:58)


X'(y-Xβ)=0

Offline

#22 2007-08-01 19:13:08

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: distance to a surface

Perhaps you misunderstand the problem George.  That computes the stationary points.  But the closest point on a surface to a particular point in space need not be a stationary point.  Or maybe you are suggesting using it in a different way?


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#23 2007-08-05 16:43:01

George,Y
Member
Registered: 2006-03-12
Posts: 1,379

Re: distance to a surface

"stationary points"

Yes, but with some other constraints we can determine amoung several the point having the shortest distance.

However, I do think this method is better than using the gradient accumatively from the surface, something similar to luca's program. Because the distance is straight instead of curvy, isn't it?


X'(y-Xβ)=0

Offline

Board footer

Powered by FluxBB