 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
If I have a bunch of random 3-d vectors, is there a way I can find a new
vector that is as close as possible to being perpendicular to as many as
possible of the vectors?
...or practically the same question formulated differently: If I have a
bunch of random points, how can I find the normal of the plane that is as
close as possible to as many as possible of the points? (The average
distance from a point to the plane should be as small as possible.)
Rune
--
3D images and anims, include files, tutorials and more:
Rune's World: http://rsj.mobilixnet.dk (updated June 26)
POV-Ray Users: http://rsj.mobilixnet.dk/povrayusers/
POV-Ray Webring: http://webring.povray.co.uk
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> If I have a bunch of random 3-d vectors, is there a way I can find a new
> vector that is as close as possible to being perpendicular to as many as
> possible of the vectors?
>
> ...or practically the same question formulated differently: If I have a
> bunch of random points, how can I find the normal of the plane that is as
> close as possible to as many as possible of the points? (The average
> distance from a point to the plane should be as small as possible.)
I would do the latter like this:
Take any 3 points, and build the cross product. Do this for all possibilities
of 3 points. So e.g. if you have 3 points, you get one cross product. If you
have 4 points, you get 6 cross products, and so on..
e.g. for A, B, C, D you do vcross(A-B, B-C), vcross(B-C, C-D), ...
Then, make all the vectors you got this way point to the same side. I forgot
how you do that, but probably you can just take a reference point a bit away
from the others, and then check if they are flipped.
Then "average" all these vectors together (i.e. add them), and take the result
as the normal to your plane.
I was just thinking this up right now, so it might be completely wrong, and
it sure is quite inefficient. But maybe it gives you some thought about a
solution :) If you want me to write it down mathematically or as POV code,
i could probably do that tomorrow. (Right now I'm too tired)
--
#macro C(X,Y)cylinder{X*x<X,0,-Y/2>.1}#end#macro U(R,X,Y)intersection{torus{.9
.1}box{-1 0rotate y*R*90}translate<X,0,Y>scale 1-z*.5}#end union{U(0,0,0)U(1,0
,0)U(2,-1,-1)U(1,1,0)U(1,1.5,-3)U(1,2,0)U(3,1,0)U(2,2,0)U(0,3,0)U(3,2,.5)C(.1,
2)C(.8,1)C(.8,-1)C(1.1,1)C(1.9,-1)pigment{rgb 10}rotate x*90translate<-1,0,4>}
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Wasn't it Rune who wrote:
>...or practically the same question formulated differently: If I have a
>bunch of random points, how can I find the normal of the plane that is as
>close as possible to as many as possible of the points? (The average
>distance from a point to the plane should be as small as possible.)
I'd try to extend the traditional line fitting technique from 2d into
3d. This technique actually minimises the average of the squares of the
distances, which produces a better looking fit than minimising the
average distances.
The 2d version:-
Calculate the mean of the x values, call it Mx.
Calculate the mean of the y values, call it My.
Calculate the mean of x^2, call it Mx2.
Calculate the mean of x*y, call it Mxy.
The best fit line y = A*x + B is then given by
A = (Mxy-Mx*My)/(Mx2-Mx*Mx)
B = My-A*Mx
[Example: three points <1,1> <2,1> <3,2> ]
[ Mx = (1+2+3)/3 = 2 ]
[ My = (1+1+2)/3 = 1.333 ]
[ Mx2 = (1^2 + 2^2 + 3^2)/3 = (1+4+9)/3 = 4.667 ]
[ Mxy = (1*1 + 2*1 + 3*2)/3 = (1+2+6)/3 = 3 ]
[ A = (3-2*1.333)/(4.667-2*1.333) = 0.167 ]
[ B = 1.333-0.167*2 = 1 ]
[ best line y = 0.167*x + 1 ]
Extending this into 3d is going to take a bit more thought.
--
Mike Williams
Gentleman of Leisure
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Wasn't it Mike Williams who wrote:
>Wasn't it Rune who wrote:
>
>>...or practically the same question formulated differently: If I have a
>>bunch of random points, how can I find the normal of the plane that is as
>>close as possible to as many as possible of the points? (The average
>>distance from a point to the plane should be as small as possible.)
>
>I'd try to extend the traditional line fitting technique from 2d into
>3d. This technique actually minimises the average of the squares of the
>distances, which produces a better looking fit than minimising the
>average distances.
It turns out that the 3d case is a bit trickier than 2d, the best
information about how to do it in 3d that I've managed to find is at
http://www.efunda.com/math/leastsquares/lstsqrzrwtxy1d.cfm
I'm not going to attempt to quote it here because it's full of symbols
that aren't in the character set that I'm using.
--
Mike Williams
Gentleman of Leisure
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Rune <run### [at] mobilixnet dk> wrote:
: If I have a bunch of random 3-d vectors, is there a way I can find a new
: vector that is as close as possible to being perpendicular to as many as
: possible of the vectors?
You could calculate the average of the normalized cross-products of all
pairs of vectors.
If there's any word in that sentence which you didn't understand, drop me
a line and I'll explain (I can't know how well you know the terminology).
--
#macro N(D,I)#if(I<6)cylinder{M()#local D[I]=div(D[I],104);M().5,2pigment{
rgb M()}}N(D,(D[I]>99?I:I+1))#end#end#macro M()<mod(D[I],13)-6,mod(div(D[I
],13),8)-3,10>#end blob{N(array[6]{11117333955,
7382340,3358,3900569407,970,4254934330},0)}// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Warp" wrote:
> You could calculate the average of the normalized
> cross-products of all pairs of vectors.
>
> If there's any word in that sentence which you didn't
> understand, drop me a line and I'll explain (I can't
> know how well you know the terminology).
Thanks, I understand it perfectly, and I've been thinking of doing that
myself, but it sounded inefficient and slow to me.
However, I realize now that for n points there's just n*(n-1)/2 pairs I
think, which is not too bad after all for the amounts of numbers I have.
So, how do this problem with the vectors relate to the problem with finding
the normal of a plane that best fits a bunch of points? Well, I figure that
when I have that bunch of points I can find the average point and look at
the vectors that go from that point to all the other points. Using the
method with the vectors I can find the normal of the plane, and I also know
that the plane goes through the average point.
For the curious, I need this for my spider walking animation, where I need
to find a good "up vector" for the spider dependent on where its feet points
are.
Rune
--
3D images and anims, include files, tutorials and more:
Rune's World: http://rsj.mobilixnet.dk (updated June 26)
POV-Ray Users: http://rsj.mobilixnet.dk/povrayusers/
POV-Ray Webring: http://webring.povray.co.uk
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Rune <run### [at] mobilixnetdk> wrote:
: Thanks, I understand it perfectly, and I've been thinking of doing that
: myself, but it sounded inefficient and slow to me.
You didn't say it should be fast... :)
If you want a faster version, I think that a good approximation can be
calculated by just choosing one of the points and using it as the end point
for all vectors. This way you have to calculate just n-1 crossproducts.
One possible variation is not taking any of the existing points as the
fixed end for the vectors, but take the average of all points as this point.
--
#macro N(D,I)#if(I<6)cylinder{M()#local D[I]=div(D[I],104);M().5,2pigment{
rgb M()}}N(D,(D[I]>99?I:I+1))#end#end#macro M()<mod(D[I],13)-6,mod(div(D[I
],13),8)-3,10>#end blob{N(array[6]{11117333955,
7382340,3358,3900569407,970,4254934330},0)}// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
