20
\$\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

\$\endgroup\$
  • 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 at 17:44
  • 1
    \$\begingroup\$ @Grimmy, thanks for the suggestions working on more testcases. \$\endgroup\$ – Mukundan Feb 13 at 17:52
  • 1
    \$\begingroup\$ Ok @Mukundan and what about the fact that the tests might have different lengths? \$\endgroup\$ – RGS Feb 13 at 19:15
  • 1
    \$\begingroup\$ Are all vertices of each polygon guaranteed to be different? \$\endgroup\$ – Luis Mendo Feb 13 at 22:39
  • 1
    \$\begingroup\$ Is the penultimate test case really falsy? \$\endgroup\$ – Arnauld Feb 13 at 22:58
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\$
  • \$\begingroup\$ @Grimmy I was still updating the link :) It should be correct now! \$\endgroup\$ – RGS Feb 13 at 18:08
  • \$\begingroup\$ a[l_]:= is a@l_:=... Also you don't need the parentheses around Norm \$\endgroup\$ – J42161217 Feb 13 at 18:36
  • 2
    \$\begingroup\$ Are you considering reversals of the list on addition to rotations? \$\endgroup\$ – xnor Feb 14 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 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\$ – Mukundan Feb 14 at 22:15
-1
\$\begingroup\$

Python 3, 321 bytes

def s(l,m):
 r,n=range,len(l)
 if n^len(m):return 0
 d=lambda p,q:((p[0]-q[0])**2+(p[1]-q[1])**2)**0.5
 a=lambda p,q,r:(d(p,q)**2+d(q,r)**2-d(p,r)**2)/(2*d(p,q)*d(q,r))
 c=lambda o:[a(o[(i-1)%n],o[i],o[(i+1)%n])for i in r(n)]
 return any([all([c(l)[i]-c(m)[::z][(i+o)%n]<1e-15for i in r(n)])for z in (1,-1)for o in r(n)])

First time golfing!

To determine the similarity between the two shapes, I considered the angle at each vertex (between the line segments formed by each vertex with the previous and next). I initially planned to only look at the distances between each vertex, but the scaling transformations would cause that to be pretty tricky.

Before anything else, I checked to make sure the shapes have the same number of vertices. I calculated the angles for each shape (lambda function c) using the distance formula (lambda function d) and the law of cosines (lambda function a). I omitted the final arccosine from the angle calculation as it was unnecessary for simple comparison. Finally, I looped through the first shape's angles and every possible slice (direction and offset) of the second shape's angles. If all the values match (or have a difference of less than 1e-15, thanks floating point...) for any iteration, the shapes are similar.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Two polygon having same angles do not mean they are similar. Take a square and a rectangle through all angles in both the polygons are 90 deg they are not similar shapes. Similarity means that one of the two polygons can be made into the other by only uniformly scaling, translating, rotating and reflecting it. \$\endgroup\$ – Mukundan Feb 22 at 4:43
  • \$\begingroup\$ Can't believe I didn't think of that—thanks! I had better rework it then. \$\endgroup\$ – M. Boligsou Feb 22 at 6:28

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.