Topic awaiting preservation: math problem

given are two quads (given are the vertices) which have the same balancepoints. now i want to rotate one of them so that the difference to the other one is minimized.
i think it would be minimized if the sum of the squared differences between the corresponding vertices is smallest, right?

then i should be able to get the rotation angle, which i need at the end.
(i think its a least squares problem)

here is an illustration:


how can i solve that to get the angle alpha?
pseudocode appreciated.

thanks!



(Edited by GRUMBLE on 05-06-2005 17:09)

quote:

---

now i want to rotate one of them so that the difference to the other one is minimized.

---

I'm not sure I quite understand what you're saying here - if you wanted the difference between the two quads to be minimized, then they would both have the same orientation, thus alpha would be 0.



(Edited by synax on 05-06-2005 17:16)

yes, but im looking for the difference.
how much do i have to rotate one quad so that it fits the other one?

the above graphic is just an example and maybe a bad one. the two quads can be arbitrary. all i have given are four vertices each.

(Edited by GRUMBLE on 05-06-2005 17:19)

To get the angle, pick the vectors V and R, respetively from the balance point to one vertex and from the balance point to the rotated counterpart of the vertex picked previously.

alpha = Math.acos( ( V.x*R.x + V.y*R.y ) / ( Math.sqrt( V.x*V.x+V.y*V.y )*Math.sqrt( R.x*R.x+R.y*R.y ) ) )


See VERC · Vectors: An Introduction:

Hope that helps,

your a genius! thanks very much!!!
havent thought of this approach! i can use this for an initial solution.

ok, but the problem is not over. (again my above explaination was probably bad.)

i need not only consider one pair of vertices but all four of them. i guess this could be done taking the average of the four angles.

BUT:
in the end i want that the overall adaption is minimal i.e. the collective distance between each pair of vertices is minimized. so this is some kind of regression problem, right? and therefore its not enough to just average the four angles but to calculate a minized sum of squared distances.

(Edited by GRUMBLE on 05-06-2005 17:35)

genius is waaaaay too strong.
If the second quad is a rotated version of the first one, you only need to check one pair of vertices.

Can you tell us if the second quad is just a rotated version of the first one or if the 2 quads are more general/not related.

quote:

---

poi said:
If the second quad is a rotated version of the first one...

---

no!
as i said they are arbitrary. thats why i have to find an optimal approximated position.

in my program i use an offset parameter (0-3) that specifies which vertex should be matched to which vertex on the other quad.

and a bit of elaboration here:
each quad is part of a mesh in 3D space. now i want to join these two meshes at these two faces.
so the steps to solve this problem are:

1. move second quad to origin
2. rotate it to the inverse of the other face's normal vector
3. rotate it along this normal vector to find a perfect match <- thats the missing part
4. move second quad to the position of first quad
5. each pair of vertices should now have a minimal position. average each pair. and merge the two meshes at these new positions.

steps 1,2,4,5 are up and running already. but step 3 is missing.

(Edited by GRUMBLE on 05-06-2005 17:48)

(Edited by GRUMBLE on 05-06-2005 17:55)

ok after lots of coffee and beer i finally figured it out another way without that minimizing thing. if anyone interested i can give a long explaination.

i would be interested in it, i am going into pre algebra next year, and i might try out for algebra, i dunno, but why are you trying to figure this question out? are you in geometry, or calculis?

"once i have fought, and now i am dead, but do not worry, for you shall also be deceased"

ok the approach i used in the end is that i measure the angle between each pair of vertices and take the average as already noted above. important is that i also measure them in the same direction, cause the dot product always gives the shortest angle. so depending on the cross product which is a vector either pointing up or down i can subtract 360° to get the correct angle.

and i do this for my thesis.

Sorry for not being helpfull till the end.

Is the junction between the 2 quads fully automated or is there a human interaction ? It could be useful to let the user shift the order of the vertices of one quad to get better ( less twisted ) junctions. No ?

its all fully automated.
and as i said i use a parameter to define the offset and a second one to define if the vertex ordering is clockwise or counterclockwise.

thanks!