24
\$\begingroup\$

Given (in any structure; flat list, two lists of lists, a tuple of matrices, a 3D array, complex numbers,…) the coordinates for two non-degenerate triangles ABC=[[Ax,Ay],[Bx,By],[Cx,Cy]] and PQR=[[Px,Py],[Qx,Qy],[Rx,Ry]], determine if they are similar, that is,

they both have the same shape, or one has the same shape as the mirror image of the other. More precisely, one can be obtained from the other by uniformly scaling (enlarging or reducing), possibly with additional translation, rotation and reflection.[Wikipedia]

You may assume that all coordinates are integers.

You must either return a truthy/falsey value indicating similar/dissimilar respectively, or two consistent values; please state your choice.

Failing on some cases due to limitations in floating point precision is acceptable so long as the algorithm is correct in principle.

Bonus task: Add a comment to this post stating whether you would like the same challenge generalised to polygons in N-space.

Walked-through example case

ABC=[[0,0],[1,0],[0,1]] and PQR=[[1,0],[-1,0],[1,-2]]

  1. Reflect ABC in the x-axis: [[0,0],[-1,0],[0,1]]

  2. Reflect in the y-axis: [[0,0],[-1,0],[0,-1]]

  3. Enlarge by a factor of 2: [[0,0],[-2,0],[0,-2]]

  4. Translate right by 1 unit: [[1,0],[-1,0],[1,-2]]

This gives us PQR.

Test cases

Similar

[[8,4],[5,-5],[0,0]] and [[-4,-1],[5,-1],[-1,5]]

[[-2,1],[4,-2],[6,2]] and [[-1,-1],[2,-1],[-1,1]]

[[-1,0],[1,0],[0,2]] and [[-2,5],[2,5],[0,1]]

Dissimilar

[[0,0],[-1,0],[0,1]] and [[1,0],[-1,0],[2,-3]]

[[2,1],[4,2],[6,2]] and [[-1,-1],[2,-1],[-1,1]]

[[-1,0],[1,0],[0,3]] and [[-2,5],[2,5],[0,1]]

\$\endgroup\$
  • \$\begingroup\$ Are flat-list input formats allowed, i.e. [1,2,3,4,5,6] instead of [[1,2],[3,4],[5,6]]? \$\endgroup\$ – Mama Fun Roll Oct 10 at 11:24
  • 2
    \$\begingroup\$ @MamaFunRoll Sure. \$\endgroup\$ – Adám Oct 10 at 11:24
  • \$\begingroup\$ Suggested test case: two similar isosceles triangles [[-1,0],[1,0],[0,2]] and [[-2,5],[2,5],[0,1]] \$\endgroup\$ – Jitse Oct 10 at 13:11
  • 3
    \$\begingroup\$ @Adám Isosceles triangles have fewer unique edges and angles. This may pose a problem when your approach includes counting the number of unique features of the triangles. \$\endgroup\$ – Jitse Oct 10 at 13:59
  • 1
    \$\begingroup\$ @xnor Thank you for pointing that out. I've added a clause to permit such failures. \$\endgroup\$ – Adám Oct 13 at 7:38

14 Answers 14

11
\$\begingroup\$

MATL, 15 12 bytes

,i4:)d|S]/da

The program inputs two 3×1 vectors of complex numbers representing the coordinates; and outputs 0 for similar, 1 for not similar.

Try it online! Or verify all test cases.

Explanation

The code checks if the side lengths, sorted for each triangle, are proportional between the two triangles.

,      % Do twice
  i    %   Take input: 3×1 vector of complex numbers
  4:)  %   Modular index to repeat 1st number after the 3rd. Gives a 4×1 vector
  d    %   Consecutive differences
  |    %   Absolute value, element-wise
  S    %   Sort
]      % End
/      % Divide, element-wise
d      % Consecutive differences
a      % Any: gives 0 if and only if all values are 0
       % Implicit display
\$\endgroup\$
5
\$\begingroup\$

Jelly, 9 bytes

ṁ4IAṢ)÷/E

A monadic Link accepting a list of two triangles - lists of complex numbers (coordinates on the Cartesian plane). Similar triangles yield 1, dissimilar ones yield 0.

Try it online! (includes footer to translate from coordinate pairs for ease of use)
Or see the test-suite.

How?

ṁ4IAṢ)÷/E - Link: list       [[a, b, c], [d, e, f]]
     )    - for each:
ṁ4        -   mould like 4   [[a, b, c, a], [d, e, f, d]]
  I       -   deltas         [[b-a,c-b,a-c],[e-d,f-e,d-f]] (i.e. vectors of sides as complex numbers)
   A      -   absolute value (i.e. side lengths)
    Ṣ     -   sort           (ordered side lengths = [[G, H, I], [J, K, L]])
       /  - reduce by:
      ÷   -   division       [G÷J, H÷K, I÷L]
        E - all equal?
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 11 bytes

Port of Luis Mendo's MATL answer.

Outputs 1 for similar, 0 otherwise.

vyĆüαnO{}/Ë

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES7),  122 120 117  112 bytes

Takes input as (a)(b), where both parameters are in the format used in the challenge.

Returns false for similar or true for dissimilar.

a=>b=>(g=a=>a.map((c,i)=>(h=j=>(c[j]-a[-~i%3][j])**2)(0)+h(1)).sort((a,b)=>a-b))(a).some((x,i)=>a-(a=x/g(b)[i]))

Try it online!

Commented

a => b =>                    // a[] = 1st triangle; b[] = 2nd triangle
  ( g = a =>                 // g is a helper function that computes the squared lengths
                             // of the sides of the triangle a[] and sorts them:
      a.map((c, i) =>        //   for each pair c[] of coordinates [x,y] at position i:
        ( h = j =>           //     h is a helper function that computes ...
          ( c[j] -           //       ... the difference between either x(i) and x(i+1)
            a[-~i % 3][j]    //           or y(i) and y(i+1) (in a circular way)
          ) ** 2             //       and squares it
        )(0)                 //     compute (x(i) - x(i+1))²
        + h(1)               //     add (y(i) - y(i+1))²
      )                      //   end of map()
      .sort((a, b) => a - b) //   sort the results in numerical order
  )(a)                       // computes the squared lengths for a[]
  .some((x, i) =>            // for each squared length x at position i:
    a -                      //   compute the difference between the previous ratio
    (a = x / g(b)[i])        //   and the new ratio defined as x / g(b)[i]
                             //   (always NaN for the 1st iteration)
  )                          // end of some()
\$\endgroup\$
3
\$\begingroup\$

Python 3, 85 bytes

lambda a:len({i/j for i,j in zip(*[sorted(map(abs,[p-q,q-r,r-p]))for p,q,r in a])})<2

Try it online!

-17 bytes thanks to FlipTack

-7 bytes thanks to tsh

Takes a list of lists of coordinates represented by complex numbers as input. Calculates the distances between all points in each set and sorts by magnitude. Then, it checks for all pairs of distances between the two sets if there is a common scaling factor. If so, the triangles are similar.

\$\endgroup\$
  • 2
    \$\begingroup\$ 103 bytes with complex numbers. \$\endgroup\$ – FlipTack Oct 10 at 17:19
  • \$\begingroup\$ @FlipTack very nice, thanks! \$\endgroup\$ – Jitse Oct 11 at 5:51
  • \$\begingroup\$ 85 bytes \$\endgroup\$ – tsh Oct 11 at 9:05
  • \$\begingroup\$ @tsh Thanks, good find! \$\endgroup\$ – Jitse Oct 11 at 11:54
2
\$\begingroup\$

J, 39 34 32 bytes

1=[:#@~.%&([:/:~#:@3 5 6|@-/@#])

Try it online!

Takes input as 3 complex numbers for each triangle.

For each triangle, we get each possible pair of points using a boolean mask filter. Ie, #:@3 5 6 translates 3, 5, and 6 to their binary representations, and each row selects one possible pair:

0 1 1
1 0 1
1 1 0

We then get the euclidean distances between of each of these pairs |@-/ and then sort them /:~.

Finally we pairwise divide the 3 sorted sides of the triangle %, take the length of the unique elements of that result #@~. and test if it equals one 1=.

\$\endgroup\$
2
\$\begingroup\$

APL+WIN, 40 bytes

Prompts for the co-ordinates of each triangle as a 4 x 2 matrix with first row repeated as last row. Confirmed with OP that this is compliant with the input rules

 0=+/2-/(y[⍋y←⍎c])÷x[⍋x←⍎c←'+/(-2-⌿⎕)*2']

Try it online! Courtesy of Dyalog Classic

\$\endgroup\$
  • \$\begingroup\$ @Adám Thanks for your clarification I will edit it back to the original. \$\endgroup\$ – Graham Oct 11 at 11:35
2
\$\begingroup\$

Python 3, 84 bytes

lambda*M:len({x/y for x,y in zip(*[sorted(abs(3*x-sum(l))for x in l)for l in M])})<2

Try it online!

Takes input as 3 complex numbers. Outputs True for similar, False for dissimilar. The first test case fails due to a float precision issue with two extremely close float values being unequal; the challenge allows this.

This uses a bit of a different method than other answers that fingerprint congruent triangles by their edges having equal length. Instead of taking the distance between pairs of vertices, we use the distance between each vertex and the center-of-mass of the three vertices, that is their average.

To demonstrate that a unique triangle satisfies this up to congruence, note that the three vectors emanating from the center of mass to the vertices must add by zero by definition, which means these vectors must themselves be able to make a triangle. Since their lengths are fixed and we only get to choose their angles (slopes), this is the same as arranging three sticks as the edges of a triangle, which as noted before is unique up to congruence.

To check similarity, we sort the respective distances and check that their ratios are all equal.

This alternative method is shorter, but I haven't proved that it doesn't give false positives.

79 bytes

lambda a,b:g(a)==g(b)
g=lambda l:{abs((x-y)/(3*x-sum(l)))for x in l for y in l}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 23 21 bytes

{{{⊇Ċ-^₂}ᶠ}ᵐz+ᵐo}ᵐz/ᵛ

-2 bytes thanks to Unrelated String

A predicate that only accepts similar triangles. Note that for negative values you have to type _1 instead of -1

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ -2 bytes using instead of ᵐ= and taking each triangle as [[x1,x2,x3],[y1,y2,y3]] instead of [[x1,y1],[x2,y2],[x3,y3]] (input can be "in any structure") \$\endgroup\$ – Unrelated String Oct 11 at 0:13
1
\$\begingroup\$

Ruby, 87 82 77 bytes

->*a{a.map!{|a,b,c|(w=[a-b,b-c,a-c].map &:abs).map{|x|x/w.sum}.sort}.uniq!=a}

Try it online!

Given the 2 triangles as vectors of 3 complex numbers, calculate length of the three sides as distance between points, then normalize and check if the result is the same.

\$\endgroup\$
1
\$\begingroup\$

Julia 1.0, 65 bytes

!x=sort(abs.(diff(push!(x,x[1]))))
g(a,b,z=!a./!b)=all(z.≈z[1])

Revised to not abuse the "any input structure" statement, as people seemed down on that. Found extra golfing, so it's only 1 byte longer. The input is two vectors of complex numbers. ! is a helper function that appends the first element to the end of each input list and returns the result, then takes the difference ob subsequent elements, elementwise absolute value, and sorts. Then calculate the ratios of the sorted lengths of the sides and check that they are all approximately equal. It costs the same number of bytes to compare square side lengths (replace abs with abs2 and by ==).

Try it online!

\$\endgroup\$
  • 4
    \$\begingroup\$ I disagree with your input method being within the rules. Instead of requiring the coordinates as input, you require the coordinates plus a bit, which is not valid per meta consensus. Other answers (1,2,3,4,5) in this thread would also benefit from this, but have worked around it inside their code. \$\endgroup\$ – Jitse Oct 11 at 7:35
  • \$\begingroup\$ I've revised my answer to take only 3 points as input. I would disagree that that conensus applies (the example is including the answer in the input, not redundancy), but the limit of "any structure" would include a custom data structure with methods defined such that all work is in part of the structure, which is an useless limit. \$\endgroup\$ – gggg Oct 11 at 15:10
1
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

Equal@@Sort/@PolygonAngle/@Polygon/@#&

Try it online!

Takes a list containing two lists of coordinates.

Checks if the two triangles' angles are equal. As PolygonAngle was introduced in version 12.0, this code does not (yet) work on TIO.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 46 bytes

≔EAEιΣXEλ⁻ν§§ι⊕μξ²θUMθ×⟦⌊ι⌈ιΣι⟧Σ§θ¬κ⬤⊟θ⁼駧θ⁰κ

Try it online! Link is to verbose version of code. Outputs - for similar, nothing for dissimilar. Accepts triangles in any N-dimensional space. Explanation:

≔EAEιΣXEλ⁻ν§§ι⊕μξ²θ

Input the two triangles and calculate the squared lengths of their sides.

UMθ×⟦⌊ι⌈ιΣι⟧Σ§θ¬κ

Calculate the shortest, longest and sum of the squared sides of each triangle, then scale by the sum of the squared sides of the other triangle.

⬤⊟θ⁼駧θ⁰κ

Check that the shortest and longest and sum of the squared sides are equal. (The middle squared side is the difference between the sum and the other two sides individually, so if they are all equal then the middle squared sides are also equal.)

\$\endgroup\$
0
\$\begingroup\$

Zsh, 156 122 116 bytes

s(){m=
for a b x y;m+=($[(a-x)**2+(b-y)**2])
n+=(${(n)m})}
s $=1
s $=2
((r=(n[1]+0.)/n[4],r*n[5]-n[2]||r*n[6]-n[3]))

Try it online! Try it online! Try it online!

Saves 34 bytes by abusing "any structure" for input. Given a pair of triangles:

[[1,2],[3,4],[5,6]] and [[7,8],[9,10],[11,12]]

The input should be the two strings:

'1 2 3 4 3 4 5 6 5 6 1 2' '7 8 9 10 9 10 11 12 11 12 7 8'

I believe this is within the rules; there is no calculation done beforehand, simply duplication. No sorting criteria is applied either.

I provide a helper function in the TIO link to prepare an argument list from a string in almost any format (it removes all non-numeric characters and splits).

Here is the first 156 byte answer, which takes the input in a less abusive format. The abusive format removes line 2 in s, and reduces line 3:

s() { # helper function, calculates squares and sorts them for one triangle
    m=                             # unset m in case it was already used
    t=(${@:^argv} $1)              # t=('x1 y1' 'x1 y1' 'x2 y2' 'x2 y2' 'x3 y3' 'x3 y3' 'x1 y1'
    for a b x y (${=t:1})          # Remove first element of $t, and split on spaces:
        m+=($[(a-x)**2+(b-y)**2])  # (a b x y): (x1 y1 x2 y2) (x2 y2 x3 y3) (x3 y3 x1 y1)
    m=(${(n)m})                    # sort squared lengths in numeric order
}

s $@[1,3]                          # run s with the first three arguments
n=($m)                             # save first result in n
s ${@:4}                           # run s with the last three arguments
((r=(n[1]+0.)/m[1], r*m[2]-n[2] || r*m[3]-n[3]))  # returns truthy if not similar
\$\endgroup\$
  • 2
    \$\begingroup\$ I disagree with your input method being within the rules. Instead of requiring the coordinates as input, you require the coordinates plus a bit, which is not valid per meta consensus. Other answers (1,2,3,4,5) in this thread would also benefit from this, but have worked around it inside their code. \$\endgroup\$ – Jitse Oct 11 at 7:39
  • \$\begingroup\$ I agree that allowing this is invalid in general. However, I wrote it after seeing this answer using repeated input, which was allowed by OP. If I wrote the challenge, I would not have allowed that answer or mine. But I make the case that allowing that answer would allow mine. If I am simply way off the mark, and the APL answer isn't abusing extended input, then I will gladly revert. \$\endgroup\$ – GammaFunction Oct 11 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.