Asked by Oskar Larsson
on 30 Dec 2018

Dear MathWorks Community,

I have written a short script that generates a matrix containing the lengths of the sides of right triangles, where all lengths are integers (e.g. the 3-4-5-triangle). After generation, the matrix is sorted by rows, so that any triangles with the same legs are removed (e.g. 3-4-5 is considered equal to 4-3-5), sides of the triangle are ordered by descending length (e.g. 3-4-5 becomes 5-4-3), and the rows are ordered in ascending order, by first column. See code-snippet # 2 below. Code-snippet # 2 is executed before code-snippet # 1.

My question is: How can I remove any triangles that are congruent from the resulting list? Preferably by removing the larger congruent triangles and keeping the smaller (e.g. remove 6-8-10 and keep 3-4-5).

I have tried doing the following, with limited succes: (code-snippet # 1)

for l = 1 : 1 : size(K1,1)

% Go through l from 1 to the number of rows in matrix K1, in steps of 1.

for m = 1 : 1 : size(K1,1)

% Go through m from 1 to the number of rows in matrix K1, in steps of 1.

leg1L = K1(l,2);

% Variable leg1L is the 1st leg of the triangle described in K1 on row l.

leg2L = K1(l,3);

% Variable leg2L is the 2nd leg of the triangle described in K1 on row l.

leg1M = K1(m,2);

% Variable leg1M is the 1st leg of the triangle described in K1 on row m.

leg2M = K1(m,3);

% Variable leg2M is the 2nd leg of the triangle described in K1 on row m.

frac1 = leg1L/leg1M;

% Variable frac1 is:

% the 1st leg of the triangle described in K1 on row l,

% divided by

% 1st leg of the triangle described in K1 on row m.

frac2 = leg2L/leg2M;

% Variable frac2 is:

% the 2nd leg of the triangle described in K1 on row l,

% divided by

% the 2nd leg of the triangle described in K1 on row m.

if ( (l ~= m) && (frac1 == int64(frac1)) && (frac2 == int64(frac2)) )

% IF l is not equal to m AND frac1 is an integer AND frac2 is an integer.

K2(l,:) = [0 0 0];

% Row l of K2 equals zeroes.

K2(m,:) = [0 0 0];

% and row m of K2 equals zeroes.

elseif ( (l ~= m) && (frac1 ~= int64(frac1)) && (frac2 ~= int64(frac2)) )

% IF l is not equal to m AND frac1 is not an integer AND frac2 is not an integer.

K2(m,:) = K1(m,:);

% Row m of K2 equals row m of K1.

end

end

end

It removes 3-4-5, 5-12-13 and 75-100-125, which is correct, but not entirely the desired result, as the first two of these sets are smaller than e.g. 6-8-10 and 10-24-26. It also fails to remove many congruent triangles, e.g. 12-16-20, which is simply 2*(6-8-10).

The code for generating, sorting and ordering the matrix is as follows, code-snippet # 2:

K = zeros(1e4,3);

% Matrix for combination is allocated, to speed up for-loops.

k = 0;

% Loop-counter is allocated.

for b = 1:1:100

% Go through b from 1 to 100 in steps of 1.

for c = 1:1:100

% Go through c from 1 to 100 in steps of 1.

a = sqrt(b^2 + c^2);

% a is defined as the squareroot of the sum of the squares of b and c.

if ( a == int64(a) )

% If a equals the integer of a

k = k+1;

% Add 1 to the loop-counter k

K(k,:)=[a, b, c];

% And write a, b and c to the k'th line of matrix K.

end

end

end

K = K(any(K,2),:);

% Remove any zero-rows of matrix K.

K = sortrows(K,1);

% Sort rows of matrix K by descending order after the values in the first

% column (the hypotenuse).

K1 = (zeros(size(K)));

% Allocate a zero-matrix the size of K called K1, for manipulating data

% from K.

% The purpose is to remove any copy-rows, where c and by have simple

% swapped places, so that 5 = sqrt(3^2 + 4^2) will be seen as equal to

% 5 = sqrt(4^2 + 3^2).

for i = 1 : 1 : size(K,1)

% Go through i from 1 to the number of rows in matrix K, in steps of 1.

vec = K(i,:);

% The vector vec equals the i'th row of matrix K.

vec = sort(vec,'descend');

% The vector vec is sorted in descending order.

K1(i,:) = vec;

% The i'th row of K1 equals vec. The loop continues to the next number,

% until it has gone through all of the rows of matrix K.

end

K1 = unique(K1,'rows');

% Any rows in matrix K1 that are identical, are now removed.

The entire script can be found in the attachment. Note that it is slightly different; in this post I have removed some non-essential code for clarity.

Thank you for your help, and may you have a Happy New Year!

Answer by per isakson
on 31 Dec 2018

Edited by per isakson
on 1 Jan 2019

Accepted Answer

Assumptions:

- The lengths of the sides are whole numbers
- The maximum length of the sides is "reasonable"

Another approach

%%

M = K1;

angles = atan( M(:,3)./M(:,2) );

%%

[ ~, ixa, ixc ] = uniquetol( angles, eps(100) );

%%

The answer is in ixa and ixc. The tolerance, eps(100), is just my first guess. The value of the M(:,1) lets you pick the smallest congruent triangle. (Lämnas som övning ;-)

A complete script (in response to commemnt)

%% Grab a small sample

M = K1(1:5,:);

M = flip( M, 1 );

%%

angles = atan( M(:,3)./M(:,2) );

%%

[ ~, ixa, ixc ] = uniquetol( angles, eps(100) );

%

%% "unique triangles"

M1 = M(ixa,:);

%

%% Replace rows by the smallest congruent triangle

for jj = 1 : length( ixa )

ix_congruent = find( ixc(ixa(jj)) == ixc );

if length( ix_congruent ) >= 2

[ ~, ix ] = min( M(ix_congruent,1) );

M1(jj,:) = M( ix_congruent(ix), : );

end

end

%% Order the triangles by the length of the hypotenuse

[ ~, ix ] = sort( M1(:,1), 'ascend' );

M2 = M1( ix, : );

Inspect the result

>> M

M =

17 15 8

15 12 9

13 12 5

10 8 6

5 4 3

>> M2

M2 =

5 4 3

13 12 5

17 15 8

>>

The first five rows of K1 contain three "unique" triangles

Another variant, which uses uniquetol( ____, 'OutputAllIndices',true )

function M3 = variant2( M )

%%

cosx = M(:,3)./M(:,1);

[ ~, ixa, ~ ] = uniquetol( cosx, eps(100), 'OutputAllIndices',true );

%%

len = length( ixa );

M3 = nan( len, 3 );

for jj = 1 : len

if length( ixa{jj} ) >= 2

[ ~, ix ] = min( M([ixa{jj}],1) );

M3(jj,:) = M( ixa{jj}(ix), : );

else

M3(jj,:) = M( ixa{jj}, : );

end

end

M3 = sortrows( M3, 1, 'ascend' );

end

A last variant that relies on that uniquetol returns the first occurence of a repeated value. Thus by first sorting with respect to the hypotenuse there is no need compare the hypotenuse of the equal values

function M3 = variant3( M )

%%

[ ~, ix ] = sort( M(:,1), 'ascend' );

M = M( ix, : );

%%

cosx = M(:,3)./M(:,1);

[ ~, ixa, ~ ] = uniquetol( cosx, eps(100) );

%%

M3 = M( ixa, : );

[ ~, ix ] = sort( M3(:,1), 'ascend' );

M3 = M3( ix, : );

end

per isakson
on 31 Dec 2018

per isakson
on 1 Jan 2019

[ ~, ix ] = sort( M3(:,1), 'ascend' );

M3 = M3( ix, : );

and

M3 = sortrows( M3, 1, 'ascend' );

do the same thing, but sortrows is slower.

Oskar Larsson
on 2 Jan 2019

Thank you very much Per, for your detailed and varied answers. What I ended up using, heavily inspired by your approaches, is this (after a matrix K1 as in my first post is generated):

K2 = K1;

% Allocate matrix K2 for speed.

zerocolK2 = zeros(size(K1,1),1);

% create zero vector (column) with the same number of rows as K1, 1 column.

K2 = cat(2,K2,zerocolK2);

% Concatenate zero column to K2.

for l = 1 : 1 : size(K1,1)

% Go through l from 1 to the number of rows in matrix K1, in steps of 1.

leg1L = K1(l,2);

% Variable leg1L is the 1st leg of the triangle described in K1 on row l.

leg2L = K1(l,3);

% Variable leg2L is the 2nd leg of the triangle described in K1 on row l.

frac1 = leg1L/leg2L;

% Variable frac1 is:

% the 1st leg of the triangle described in K1 on row l,

% divided by

% 2nd leg of the triangle described in K1 on row l.

K2(l,4) = frac1;

% Row l, column 4 of K2 equals zeroes.

end

% To eliminate congruent triangles:

% Add a 4th column, consisting of the fraction (L1/L2)

% for legs 1 and 2 in a triangel (row).

% Use unique to filter any rows that share the same 4th value.

[~, IA, ~] = unique(K2(:,4));

% Finds the unique values of column 4 in K2, for each row. IA is the

% index-vector for the unique values.

K3 = K2(IA,:);

% K3 is every indexed row from K2 with a unique value in the fourth

% column.

K3 = sortrows(K3,1);

% K3 is sorted in ascending order based on the values of the first column.

K3(:,4) = [];

% The fourth column is deleted.

Which graphically results in this:

If the full code would interest you, or anyone else, I have attached the final file to this post.

Again - many thanks for most valuable help!

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.