Started by Oct 15 2001 05:32 AM

,
9 replies to this topic

Posted 15 October 2001 - 05:32 AM

OK, I have a set coordinates in 3D space. I want to adjust them all so that they lie on a stright line. Thats pretty simple (dot product = 0 etc)
The problem is that the line has to be an average line based on all the points.
Is my question understandable ?
Maybe not, I'll upload a pic to explain:
Image
The main problem is to get a definition of the line.
Does anyone have any clever ideas about how to do this ?
(edit: typos)
Edited by - Jesper T on October 15, 2001 12:33:40 PM

Posted 15 October 2001 - 05:46 AM

I''d start at one point and calculate the slope from that point to each of the others and average that. The final line would use this average as its slope.

Posted 15 October 2001 - 05:56 AM

I''ve thought about that, doesnt work.

Say if you have A = (0, 1, 1) and B = (10, 1, 0) and C = (-10, 2, 1)

Now, if I''d take the average of vector CA, and CB it would do fine. The average of CA and AB would also go fine, but for example the average between AB and AC would be far from good enough.

Any other ideas ?

Say if you have A = (0, 1, 1) and B = (10, 1, 0) and C = (-10, 2, 1)

Now, if I''d take the average of vector CA, and CB it would do fine. The average of CA and AB would also go fine, but for example the average between AB and AC would be far from good enough.

Any other ideas ?

Posted 15 October 2001 - 05:59 AM

if i have grasped you have a set of 3d points randomly distribuited and you want to draw a line passing from a sort of center point ? find the center averaging all the values and the write the equation of a line passing from that point

that''s to say

((x-cx)/l)=((y-cy)/m)=((z-cz)/n)

note that a line in 3d space is the intersection of two planes

the vector l,m,n is a direction vector , but in this form it can be anything , if you give one more point you can draw a straight line from the center c to p , i don''t know if its clear ,

but it look to me like a gaussian distribuition .... only in 3d space

that''s to say

((x-cx)/l)=((y-cy)/m)=((z-cz)/n)

note that a line in 3d space is the intersection of two planes

the vector l,m,n is a direction vector , but in this form it can be anything , if you give one more point you can draw a straight line from the center c to p , i don''t know if its clear ,

but it look to me like a gaussian distribuition .... only in 3d space

Posted 15 October 2001 - 06:07 AM

quote:Original post by Jesper T

I''ve thought about that, doesnt work.

Say if you have A = (0, 1, 1) and B = (10, 1, 0) and C = (-10, 2, 1)

Now, if I''d take the average of vector CA, and CB it would do fine. The average of CA and AB would also go fine, but for example the average between AB and AC would be far from good enough.

I would have thought from your diagram that there would be "logical" choices for end points - those furthest left, right, up or down. If you always start from an extremity then the algorithm

Try to think of this graphically. From your first point (extremity) to the next you obtain a slope. You now average that with the slope from the first to the third, which refines your final line (the new slope should lie in between the first two), and so on.

quote:Original post by v71

if i have grasped you have a set of 3d points randomly distribuited and you want to draw a line passing from a sort of center point ? find the center averaging all the values and the write the equation of a line passing from that point

An infinite number of lines pass through a point. You need either a point and a slope or two points.

Posted 15 October 2001 - 06:10 AM

Hmm, I''ve just seen a flaw in my above post: your starting point will be on the eventual line, which may not be desirable. Hence the following modification.

After obtaining the slope, you still need a point for the line to pass through. That point is the average of all the points as suggested by v71. Given the slope and an intercept you now have a fully specified line.

After obtaining the slope, you still need a point for the line to pass through. That point is the average of all the points as suggested by v71. Given the slope and an intercept you now have a fully specified line.

Posted 15 October 2001 - 06:21 AM

You can use a statistical approach to finding a best-fit line for all of your data points (Linear Regression). Dave Eberly has a good document on how to do this here:

http://www.magic-software.com/Documentation/lsfit.pdf

And some free code to do it here:

http://www.magic-software.com/Approximation3D.html

http://www.magic-software.com/Documentation/lsfit.pdf

And some free code to do it here:

http://www.magic-software.com/Approximation3D.html

Posted 15 October 2001 - 06:33 AM

The magic-software reference should be a good one. You could also do a web search on "least squares" or "linear least squares." That might turn up some example code. This is a classic basic linear algebra problem.

Graham Rhodes

Senior Scientist

Applied Research Associates, Inc.

Graham Rhodes

Senior Scientist

Applied Research Associates, Inc.