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

[(0, 0), (1, 0), (1, 1), (0, 1)]
[(-1, 0), (2, 1), (1, 4), (-2, 3)]

Graph

Output

Truthy

Input

[(2, 3), (0, 0), (4, 0)]
[(-3, 0), (-2, 2), (0, 1), (1, -1), (-1, -2), (-2, -2)]

Graph

Output

Falsy

Input

[(1, 4), (1, 3), (0, 2), (1, 1), (-3, 2)]
[(2, 0), (2, -1), (3, -1), (4, -2), (-2, -2)]

Graph

Output

Falsy

Input

[(-1, 0), (2, 1), (1, 4), (-2, 3)]
[(1, 4), (2, 1), (-1, 0), (-2, 3)]

Graph

Output

Truthy

Input

[(-2, 0), (-1, 1), (0, 1), (1, 3), (1, 0)]
[(5, 4), (4, 2), (3, 2), (2, 1), (5, 1)]

Graph

Output

Truthy

Input

[(2, 13), (4, 8), (2, 3), (0, 8)]
[(0, 0), (5, 0), (8, 4), (3, 4)]

Graph

Output

Falsy

Input

[(-1, 0), (-5, 3), (-5, 9), (-1, 6)]
[(0, 0), (5, 0), (8, 4), (3, 4)]

Graph

Output

Falsy

Input

[(0, 0), (1, 2), (1, 0)]
[(2, 0), (2, 2), (3, 0)]

Graph

Output

Truthy
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\$
    – Grimmy
    Feb 13, 2020 at 17:44
  • 1
    \$\begingroup\$ @Grimmy, thanks for the suggestions working on more testcases. \$\endgroup\$
    – Mukundan314
    Feb 13, 2020 at 17:52
  • 1
    \$\begingroup\$ Ok @Mukundan and what about the fact that the tests might have different lengths? \$\endgroup\$
    – RGS
    Feb 13, 2020 at 19:15
  • 1
    \$\begingroup\$ Are all vertices of each polygon guaranteed to be different? \$\endgroup\$
    – Luis Mendo
    Feb 13, 2020 at 22:39
  • 1
    \$\begingroup\$ Is the penultimate test case really falsy? \$\endgroup\$
    – Arnauld
    Feb 13, 2020 at 22:58

1 Answer 1

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\$
    – RGS
    Feb 13, 2020 at 18:08
  • \$\begingroup\$ a[l_]:= is a@l_:=... Also you don't need the parentheses around Norm \$\endgroup\$
    – ZaMoC
    Feb 13, 2020 at 18:36
  • 2
    \$\begingroup\$ Are you considering reversals of the list on addition to rotations? \$\endgroup\$
    – xnor
    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\$
    – RGS
    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\$
    – Mukundan314
    Feb 14, 2020 at 22:15

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.