21
\$\begingroup\$

Task

Given the x,y coordinates (coordinates are guaranteed to be integers) of the vertices of two simple polygons in clockwise or anti-clockwise order. Output a Truthy value if both the polygons are similar otherwise a Falsy value

A simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple. Two edges meeting at a corner are required to form a an angle that is not not straight (180°)

Two polygons are similar if either polygon can be rescaled, repositioned, and reflected, so as to coincide precisely with the other polygon.

Testcases

Input Output Image
[(0, 0), (1, 0), (1, 1), (0, 1)]
[(-1, 0), (2, 1), (1, 4), (-2, 3)]		 Truthy
[(-1, 0), (2, 1), (1, 4), (-2, 3)]
[(1, 4), (2, 1), (-1, 0), (-2, 3)]		 Truthy
[(-2, 0), (-1, 1), (0, 1), (1, 3), (1, 0)]
[(5, 4), (4, 2), (3, 2), (2, 1), (5, 1)]		 Truthy
[(0, 0), (1, 2), (1, 0)]
[(2, 0), (2, 2), (3, 0)]		 Truthy
[(2, 3), (0, 0), (4, 0)]
[(-3, 0), (-2, 2), (0, 1), (1, -1), (-1, -2), (-2, -2)]		 Falsey
[(1, 4), (1, 3), (0, 2), (1, 1), (-3, 2)]
[(2, 0), (2, -1), (3, -1), (4, -2), (-2, -2)]		 Falsey
[(2, 13), (4, 8), (2, 3), (0, 8)]
[(0, 0), (5, 0), (8, 4), (3, 4)]		 Falsey
[(-1, 0), (-5, 3), (-5, 9), (-1, 6)]
[(0, 0), (5, 0), (8, 4), (3, 4)]		 Falsey
Improve this question
\$\endgroup\$
11
  • 3
    \$\begingroup\$ This needs way more falsy test cases! For starters: non-similar rhombi (defeats submissions that only check side lengths); non-similar rectangles (defeats submissions that only check angles). Also, I'd suggest cutting down on the diagrams: one or two are enough to get the idea, beyond that I'd rather have all the test data in a convenient text format. \$\endgroup\$ Commented Feb 13, 2020 at 17:44
  • 1
    \$\begingroup\$ @Grimmy, thanks for the suggestions working on more testcases. \$\endgroup\$ Commented Feb 13, 2020 at 17:52
  • 1
    \$\begingroup\$ Ok @Mukundan and what about the fact that the tests might have different lengths? \$\endgroup\$ Commented Feb 13, 2020 at 19:15
  • 1
    \$\begingroup\$ Are all vertices of each polygon guaranteed to be different? \$\endgroup\$ Commented Feb 13, 2020 at 22:39
  • 2
    \$\begingroup\$ Related: Similar triangles \$\endgroup\$ Commented Feb 14, 2020 at 9:10

3 Answers 3

Reset to default
5
\$\begingroup\$

Mathematica, 97 bytes (SBCS)

Or@@(Equal@@(a@u/#)&/@(a/@NestList[RotateLeft,v,Length@v]))
a@l_:=Norm[#〚1〛-#〚2〛]&/@l~Subsets~{2}

You can try it online!

The function a computes all the pairwise distances between any two vertices of the polygon.

The main function applies this to the first list and to every rotation of the second list, to try and find the corresponding vertices. The rotation of the second list is correct if all the corresponding distances have been scaled accordingly.

Thanks to @J42161217 for saving me some 3 bytes

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ @Grimmy I was still updating the link :) It should be correct now! \$\endgroup\$ Commented Feb 13, 2020 at 18:08
  • \$\begingroup\$ a[l_]:= is a@l_:=... Also you don't need the parentheses around Norm \$\endgroup\$ Commented Feb 13, 2020 at 18:36
  • 2
    \$\begingroup\$ Are you considering reversals of the list on addition to rotations? \$\endgroup\$ Commented Feb 14, 2020 at 21:20
  • \$\begingroup\$ No, I am not. Are you saying that I should..? I would say it is more than fair to assume that the lists give a path around the polygon in the same direction... I would argue the heart of the challenge is to check for polygon similarity, not to reverse a list... \$\endgroup\$ Commented Feb 14, 2020 at 21:25
  • 2
    \$\begingroup\$ @RGS also you code does not work for testcases where reflections are needed like u = {{0, 0}, {1, 1}, {1, 0}} v = {{2, 0}, {2, 1}, {3, 0}} Try it online! \$\endgroup\$ Commented Feb 14, 2020 at 22:15
1
\$\begingroup\$

Python, 141 bytes

lambda a,b:max(h(a:=a[1:]+[i],max(d:=h(b))/max(h(a)))in[d,d[::-1]]for i in a)
h=lambda a,d=1:[d*((i-k)**2+(j-l)**2)for i,j in a for k,l in a]

Attempt This Online!

Port of @RGS's answer, modified to properly handle cases that require reflections or scenarios where one polygon is clockwise and the other is counterclockwise.

Python, 126 bytes

lambda a,b:max(h(a:=a[1:]+[i],max(d:=h(b))/max(h(a)))in[d,d[::-1]]for i in a)
h=lambda a,d=1:[d*abs(i-j)for i in a for j in a]

Attempt This Online!

Takes input as complex numbers, it fails the first testcase due to rounding errors.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 180 bytes

A=>g=(B,k=0)=>new Set(A.flatMap((x,i)=>B.map((y,j)=>A[j]&&B[i]&&D(x,A[j])/D(B[i],y)))).size<3||B[k>>1]&&g(B.reverse(),++k,k&1&&B.push(B.shift()))
D=([a,b],[c,d])=>(c-a)**2+(d-b)**2

Try it online!

Each pair of distance in ratio

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.