Hongyi Zhao on Mon, 13 Mar 2023 04:09:42 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Determine the mirror reflection relationship between the coordinates of two sets of pairs of points in n-dimension space. |
On Mon, Mar 13, 2023 at 9:39 AM Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote: > > * Hongyi Zhao [2023-03-13 00:59]: > > On Mon, Mar 13, 2023 at 2:38 AM Karim Belabas > > <Karim.Belabas@math.u-bordeaux.fr> wrote: > > > > > > Unordered sets of points then. > > > > Very good, your general assumption above will make your algorithm > > applicable to any case of two sets of points : ordered or disordered > > correspondence between two sets of points. > > > > > OK, so for all (a,b) with a in A and b in B, > > > compute v = a - b: this gives us the possible (unnormalized, i.e. > > > arbitrary norm instead of |v| = 1) vectors v(a,b). > > > > > > If we normalize them, the possible vectors v are the ones that occur at > > > least #A times from the (#A)^2 pairs (a,b). It should be a very short > > > list, with at most #A entries in any case. We can then check whether any > > > of the attached reflexions s work or not by computing s(A) and comparing > > > with B (as sets). > > > > > > Something like > > > > > > normalize(v) = foreach(v, x, if (x, return(v / x))); > > > > > > V = matreduce([normalize(a - b) | a <- A; b <-B]); > > > for (i = 1, #V[,2], if (V[i,2] >= #A, print(V[i,1]))) > > > > > > This prints the single vector > > > v = [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~ > > > with attached reflexion > > > s(x) = x - 2 * (x~*v / norml2(v)) * v; > > > > > > Unless I made a stupid mistake, it doesn't work: > > > ? Set([s(a) | a <- A]) == Set(Vec(B)) > > > %10 = 0 > > > > Failed as follows: > > > [...] > > ? normalize(v) = foreach(v, x, if (x, return(v / x))); > > ? V = matreduce([normalize(a - b) | a <- A; b <-B]); > > ? for (i = 1, #V[,2], if (V[i,2] >= #A, print(V[i,1]))) > > [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~ > > ? s(x) = x - 2 * (x~*v / norml2(v)) * v; > > ? Set([s(a) | a <- A]) == Set(Vec(B)) > > *** at top-level: Set([s(a)|a<-A])==Set(Vec(B)) > > *** ^------------------------ > > *** in function s: x-2*(x~*v/norml2(v))*v > > *** ^--------------------- > > *** _-_: forbidden addition t_VEC (8 elts) + t_COL (8 elts). > > *** Break loop: type 'break' to go back to GP prompt > > You need to set > > v = [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~ > > as I wrote ! (But see below.) > > > > (Please double-check, this is really a quick hack :-) > > > > Side remark: In fact, the point sets used here are generated with > > Wolfram language, which ensure that they are mirror images of the > > other via the following commands: > [...] > > Ah, so you meant an affine reflection (through a affine hyperplane with > normal vector v not necessarily containing 0; its equation being > <v,x> = c for a normal vector v as before and some scalar c, which I had > assumed to be 0). > > The formula for the reflection becomes > s_{v,c}(x) = x - 2 ((<v,x> - c) / <v,v>) * v > and everything remains the same up to (and including) the determination of > possible vectors v. > > But the final check for the computed v's becomes more complicated since > we don't know c. I don't see any better way than picking a in A and > testing b - s_{v,0}(a) for all b in B. One of these b must be s_{v,c}(a) > and for this choice we must find a vector colinear to v > > s_{v,c}(a) - s_{v,0}(a) = (2 c / <v,v>) * v > > giving the possible values for c (we may find other values, again a > short list: at most #A possibilities). > > s0(x) = x - 2 * (x~*v / norml2(v)) * v; > a = A[,1]; s0a = s0(a); v = normalize(v); > C = List(); > { > foreach(B, b, > if (normalize(b - s0a) == v, > w = (b - s0a)*norml2(v)/2; \\ c * v > listput(C, matsolve(Mat(v), w)[1]))); > } > > In this case, we find a single possibility > > ? C > %15 = List([-5/2]) > > So the reflection we must now test is > > c = -5/2; > v = [0, 1, -1/2, 2, 3/2, 2, -1/2, -1]~ > s(x) = x - 2 * ((x~*v - c) / norml2(v)) * v; > > ? Set([s(a) | a <- A]) == Set(Vec(B)) > %20 = 1 > > Hurray, found it ! I am glad to hear this news! > So let's recap: the previous algorithm finds all possible v's given A,B; > for each such v, the above finds a list of tentative c and the > Set(...) = Set(...) test above is true iff s_{v,c}(A) = B (as sets) But in all the above steps, I can only see that there is exactly one v is found. So, the complete solution set of this problem is still not obtained so far. > Cheers, > > K.B. Regards, Zhao > -- > Pr Karim Belabas, U. Bordeaux, Vice-président en charge du Numérique > Institut de Mathématiques de Bordeaux UMR 5251 - (+33) 05 40 00 29 77 > http://www.math.u-bordeaux.fr/~kbelabas/ > `