Orthogonal constraint between two 3d vectors basis

Help!
1

Hi, I’m a Prolog learner, so my code can not be very efficient. I’m stuck on a little problem in Prolog which seems doable. Here is the problem :

I have two basis [i0,j0,k0] and [i1,j1,k1]. Then we have an orthogonal constraint between all elements of the same basis (i0 is orthogonal to j0, j0 is orthogonal to k0, and k0 is orthogonal to i0, and the same for the vectors of the second basis).

I would like to find the set of new orthogonal constraint to add between elements of the first basis and the second one such that the two basis are aligned/equal. Then it could be interesting to find the minimal number of constraints (which seems to be 3 when you think about it).

Here is my attempt:

:- dynamic ortho_constraint/2.

basis([i0,j0,k0]).
basis([i1,j1,k1]).

ortho(X,Y) :- ortho_constraint(X,Y); ortho_constraint(Y,X).
ortho(X,Y) :- basis(B), permutation(B,[X,Y,_]).

collin(X,Y) :-
    dif(X,Y), % fail fast principle
    basis(B1), basis(B2), dif(B1,B2),
    permutation([E1,E2,X],B1), member(Y,B2),
    ortho(E1,Y), ortho(E2,Y).

equal(B1,B2) :-
    B1 = B2;
    length(B1,3), length(B2,3),
    maplist(collin, B1, B2).

In this code I defined basis/1 the predicate to define a base. Then ortho/2 is true when it exists a base B in which X and Y are vectors, or when it exists a dynamically added ortho_constraint/2 between the two vectors.

The first problem occurs in collin/2. It’s defined on the fact that two vectors X and Y are collinear iif it exists two different basis B1=[E1,E2,X] and B2=[_,_,Y] (possibly with a permutation) such that ortho(E1,Y) and ortho(E2,Y) are true.

When I query that, with some dynamic constraints added and that I want to get all X and Y such that collin(X,Y) is true, I get :

?- asserta(ortho_constraint(i1,k0)), asserta(ortho_constraint(j1,k0)), asserta(ortho_constraint(j1,i0)), collin(X,Y), retractall(ortho_constraint(_,_)).
X = j0,
Y = j1 ;
false.

But for instance :

?- asserta(ortho_constraint(i1,k0)), asserta(ortho_constraint(j1,k0)), asserta(ortho_constraint(j1,i0)), collin(k0,k1), retractall(ortho_constraint(_,_)).
false.

?- asserta(ortho_constraint(i1,k0)), asserta(ortho_constraint(j1,k0)), asserta(ortho_constraint(j1,i0)), collin(k1,k0), retractall(ortho_constraint(_,_)).
true .

collin/2 seems to depends on the order of the arguments even if I pay attention to not impose the basis in which X and Y belong, and we are not able to query all answers since {X=k1, Y=k0} should at least appear in the answers of collin(X,Y) …

Also, collin/2 has to be true between two vectors of two different basis if the two others vectors of the two different basis are already collinear (i0 // i1 and j0 // j1 => k0 // k1), but I am not able to express this rule without falling into an infinite recursion …

Can you help me to code a better version of collin/2 ?

At this point I will also be able to simplify equal/2 as when two vectors of two basis are collinear, it implies that the third vectors of the two basis are also collinear one to another ;).

Then I would like to formulate my query to answer my problem. The goal is to generate a list L of all possible pairs X-Y such that X is a member of B1 and Y is a member of B2, and then generate a powerset P from this list. This represents all the possible constraints we have to test in our problem. Then, for a list of constraint T in the powerset P, we define the constraints which are in T and we check that the two basis are equals, just before removing the dynamically added constraints.

powerset([], []).
powerset([_|T], P) :- powerset(T,P).
powerset([H|T], [H|P]) :- powerset(T,P).

solution(T,B1,B2) :-
    basis(B1), basis(B2), dif(B1,B2),
    findall(PS, (setof(X-Y, (member(X,B1), member(Y,B2)), L), powerset(L,PS)), P),
    member(T,P), forall(member(X-Y,T), asserta(ortho_constraint(X,Y))),
    equal(B1,B2), retractall(ortho_constraint(_,_)).

If you think that my query could be expressed in a simpler/clearer way, please notice me. I have 260 results and when I order them I have :

?- setof(Len-T, (solution(T, [i0,j0,k0],[i1,j1,k1]), length(T,Len)), Z), keysort(Z, S).
S = [
 1-[j0-i1],
 2-[i0-i1, j0-i1],
 2-[i0-j1, k0-i1],
 2-[i0-k1, j0-k1],
 2-[j0-i1, k0-i1],
 3-[i0-i1, i0-j1, k0-i1],
 3-[i0-i1, i0-k1, j0-k1],
 3-[i0-i1, j0-i1, k0-i1],
[...]

So some problems with lists of size 1 and 2 which are clearly not solutions of my problem, but the rest “seems” correct …

Thanks in advance

Teusner

2

As far as I rember it correctly that any orthogonal group transforms orthogonal basis to another orthogonal one. If so, by restricting G to an appropriate subgroup H of G, one could generate in a systematic way a series of orthogonal basis systems from given basis. Perhaps I am wrong and missing some basic point of your post. I appreciate if you could enlightening me on this point.

3

I second that.

EDIT

Is this what you are referring to in your question?

Determining a perpendicular vector to two given vectors.

4

@kuniaki.mukai You are absolutely right (at least sure for the special orthogonal group SO(n) as it corresponds to a rotation in the space, but not 100% sure for all transform in any orthogonal group).

It’s therefore not really what I’m searching for. Here I want to find all orthogonal constraints to add between vectors of the two basis to align the two basis.

If I represent this problem in an array I have :

ortho

i0 j0 k0 i1 j1 k1
i0 0 1 1 x x x
j0 1 0 1 x x x
k0 1 1 0 x x x
i1 x x x 0 1 1
j1 x x x 1 0 1
k1 x x x 1 1 0

In this table 1 stands for an orthogonal constraint between X and Y, 0 for a non-orthogonal constraint, and x for an undetermined constraints for now. I’ve put all piece of information given by the fact that [i0,j0,k0] is a basis, and [i1,j1,k1] is another basis.

Remark: This matrix is symmetrical.

Now I need to find the set of all x which have to be set to 1 such that the two basis are aligned, i.e i0 is collinear to to i1, j0 is collinear to j1, and k0 is collinear to k1.

For instance :

i0 j0 k0 i1 j1 k1
i0 0 1 1 x 1 x
j0 1 0 1 x 0 x
k0 1 1 0 1 1 0
i1 x x 1 0 1 1
j1 1 0 1 1 0 1
k1 x x 0 1 1 0

Adding ortho(i1,k0), ortho(j1,k0), and ortho(i0,j1) lead to the fact that the two basis are aligned (I know it because I thought about it :laughing:). In the table, the corresponding 1 are added, and I’ve added 0 as we couldn’t have three 1 on the same row/column.

The remaining x could be set independently in [0,1] such that there is at least a 0 on each row/column and the two basis should remain aligned.

Remark:
The explaination of collin/2 is very visual with this table : two vectors X and Y are collinear if there is 1 on all the line except in front of the two vectors X and Y. It’s the case for k0 which is collinear to k1, and j0 which is collinear to j1. This condition also implies that i0 is collinear to i1, which is not visible on this table. It joins a question i asked in the first post to add this rule in my program without falling into an infinite loop :sweat_smile:.

By adding these constraint the program should know that the basis are aligned using collin/2 and should return [i1-k0, j1-k0, i0-j1].

5

Yes, but I don’t want to work with number coordinates. I need to stay with atoms.

6

Sorry but I am still lost as to what you seek. :frowning_face: If I had more time I would ask more questions so for now will just keep an eye on this and see if my confusion is relived by more information from others asking questions.

1 Like
7

My tentative guess is this: The input of your constraint problem is a something like boolean combination of orth(x, y), where x and y are 3d vectors symbols. The output is a set of nontrivial collin(y,z) information. collin(a, a) is trivial, for example. Your method does not use matrix operations with concrete numbers, doing only symbolic computation without numbers. Anyway this is only my tentative guess, surely poor guess, which, I am afraid, might be nothing to do with your problem.

8

In fact @kuniaki.mukai this is a very strong reformulation of my problem (much better than I could do). You have it !

I would just add that there is two kind of inputs constraints:

  • ortho(X,Y) constraints deduced from basis([X,Y,Z]), which are irrefutable,
  • ortho(X,Y) constraints which will be assumed by the program in the searching process of solutions, i.e. the ortho_constraint/2 of my first post, or x’s in the table which will be transformed in 1’s.
9

I have not looked at the code in detail yet nor run it but this jumped out now that I have more knowledge.

B1 = B2 will unify B1 with B2 (=/2) but by the name of the predicate equal I take it that you want to check if B1 equals B2, if that is the case you may want B1 == B2, see: ==/2, or something else.

10

Totally, the goal here is not to unify B1 and B2 but to test the equality. I will replace =/2 by ==/2.

In fact this predicate was added to avoid the following tests if the input basis B1 and B2 are already the same (no need test a lot of collin/2 predicates).

Moreover, as only two collinear vectors of two different basis are sufficient to state that the basis are aligned, I propose this new version of equal/2 :

equal(B1,B2) :-
    B1 == B2;
    length(B1,3), length(B2,3),
    permutation([X1,Y1,_],B1), permutation([X2,Y2,_],B2),
    collin(X1,Y1), collin(X2,Y2).

Now I need to understand why :

11

FYI, read the last post but still am lost as to what you seek and glad I gave something back of value. I don’t have time to dig into this in detail as I still don’t have enough understanding of how this is suppose to work. I am getting fixated on the apparent restriction that the values in the matrix can only be 0, 1 or a variable x when I am expecting values that are all reals.

If there is a paper(s) that explains this or gives an introduction to the concepts or Wikipedia and/or Mathworld articles for the terms used that might help. When I see the matrix with only 0 or 1 I keep thinking Adjacency matrix. which I am sure is wrong.

12

Nope, 0 1 and x have to be seen as boolean relation between entries of the table :

  • 1 means ortho(x,y) true,
  • 0 means ortho(x,y) false,
  • x means ortho(x,y) is for now undefined and could be 1 or 0.

Maybe the table is confusing you.

There is no paper/wikipedia/… as far as I know. I’m trying to solve another problem in which I have to find the set of orthogonal constraint to setup between vectors of two basis to align these basis. I feel that we need at least 3 constraints, but it’s only intuition, and that we could maximum add 6 well chosen orthogonal constraints but it’s my intuition again.

I feel that Prolog is perfectly suitable to find this set of constraints but I’m still stuck for now.

That’s exactly it :grinning: (I don’t know the term of Adjacency matrix) ! The table example was definitely confusing …

As said at the beginning of this reply, my problem is about boolean constraints ortho/2 between vectors of two basis. But vectors don’t have any coordinates, it’s only atoms representing vectors. I don’t have to compute the coordinates of vectors, instead I want to know the set of constraints between these vectors to align / make these basis equals.

It can in fact be reformulated using a graph :

2022-11-25 10.28.01
2022-11-25 10.28.011920×1446 54.8 KB

On this graph, solid red lines between two nodes represent an ortho/2 irrefutable constraints (as vectors of the same basis are orthogonal one to another), and dotted lines represent here a solution I want to determine : If I add these 3 red-dotted constraints between nodes of the two basis, the two basis will be aligned (I found this solution by just thinking about it)

Here added constraints are : ortho(i1,k0), ortho(j1,k0), and ortho(i1,j0).

But there is also other solutions I want to have using prolog. For instance : ortho(i1,k0), ortho(j1,k0), and ortho(j1,i0) seems also to be a solution.

13

output

This animation show also the same 3 constraints (ortho(i1,k0), ortho(j1,k0), and ortho(i1,j0)) added between vectors of the two basis which align these basis.

And maybe, there is also set of 4, 5, or 6 constraints to add between the two basis to align them, but I feel that only 3 constraints are sufficient ; 4, 5, or 6 constraints will add redundancy. (but it could be interesting to get these solutions also :grin:)

I hope my problem is understandable now :innocent: Thank you for your patience and determination to understand it otherwise

14

Sorry, no. :frowning_face:

Parts of it I understand, parts of it just seem like trying to force a square peg into a round hole in my head or sitting in a chair with one of the four legs missing, it is just to wobbly to feel like it is safe to use.

I hate to say it but for me to help work on this, which does not include the possibility to solve it, would require creating a well defined set of terminology first then building up rules using the terminology. That would take more time than I currently have which is why I was seeking the references in my last reply. :slightly_frowning_face:

15

Now I feel I unserstand your problem a little bit better. Let A, B be a couple 3d basis, and C an orthogonal matrix such that A = C*B. Solve C in a way of dynamic programming. Initial constaint on C is a well known system of algebraic equations for condition of orthogonal matrix. However I am stucked at what’s next. Dynamic programming needs transactions, which are vague for me. If my guess is to some point, Prolog constraint system (on Boolean, or finite domain) might be useful as you and other might agree, because I think these constraint system are libraries to solve that dynamic programming efficiently.

16

@Teusner Is any of this related to or is this your problem?

Graph Theory FAQs: 03. Isomorphism Using Adjacency Matrix

17

I just found that it could be related to direct cosine matrix (DCM) as described on this page.

Warning: the following table will be different from the previous one. Here are the new rules for this table:
We store scalar product between input vectors on each cases:

  • 1: if x.y=1
  • 0: if x.y = 0
  • . no relations has been established for now between vectors
i0 j0 k0 i1 j1 k1
i0 1 0 0 . . .
j0 0 1 0 . . .
k0 0 0 1 . . .
i1 . . . 1 0 0
j1 . . . 0 1 0
k1 . . . 0 0 1

Here are the relations between vectors of the basis B0=[i0,j0,k0] and B1=[i1,j1,k1]. In this matrix, there is already 1’s where input vectors are equals (i0.i0 = 1 for instance), and 0 where vectors are orthogonal (i0.j0=0 for instance).

This table has the form :

B1 B2
B1 I_3 R
B2 R^T I_3

With I_3 the identity matrix, and R \in SO(3) (special orthogonal group, i.e. a rotation matrix) is the direct cosine matrix between B0 and B1. To have aligned basis, I need to only have +1 and -1 in R instead of ., and R has to be a rotation matrix respecting the following conditions:

R.R^T = I_3
det(R) = 1

In my problem, I want to find the minimal number of 0 to put in R, such that R respect the previous conditions, and 3 .'s are replaced by 1’s in R (one per row and one per column, which implies that R respects the previous conditions in other terms).

18

If I read this correctly, it sounds possible R are at most 3^9= 19683,
which is fairly easy to enumerate them all. Maybe I am missing something. Anyway I am glad to feel you have approached finally to your goal.

1 Like