25
3
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]]
Reflect
ABC
in the x-axis:[[0,0],[-1,0],[0,1]]
Reflect in the y-axis:
[[0,0],[-1,0],[0,-1]]
Enlarge by a factor of 2:
[[0,0],[-2,0],[0,-2]]
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]]
Are flat-list input formats allowed, i.e.
[1,2,3,4,5,6]
instead of[[1,2],[3,4],[5,6]]
? – Mama Fun Roll – 2019-10-10T11:24:09.4832@MamaFunRoll Sure. – Adám – 2019-10-10T11:24:34.507
Suggested test case: two similar isosceles triangles
[[-1,0],[1,0],[0,2]]
and[[-2,5],[2,5],[0,1]]
– Jitse – 2019-10-10T13:11:30.1473@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. – Jitse – 2019-10-10T13:59:12.683
@Jitse Added both similar and dissimilar isosceles triangles. – Adám – 2019-10-11T07:19:38.453
it looks like a number of solutions unfortunately will reject some similar triangles due to float limitation if a few more test cases are tried. For example, passing in the first test case with inputs swapped can reveal this. I think this applies to any solution that uses square roots or abs for distance in a language that represents it with finite precision. – xnor – 2019-10-13T01:46:36.450
1@xnor Thank you for pointing that out. I've added a clause to permit such failures. – Adám – 2019-10-13T07:38:59.587