Given is a grid polygon by the list of its integer vertex coordinates arranged along the perimeter, in the form
\$(x_1,y_1), (x_2,y_2), \cdots , (x_n,y_n)\$ with \$n \ge 3\$.
The polygon is completed by connecting point \$n\$ to point \$1\$.
For simplicity, it may be assumed that the polygon is simple and does not have interior angles \$\gt \pi\$.
The diameter D is defined here as the largest Euclidean distance between any two points on the circumference of the polygon.
A polygon can be deformed by applying shear while the area remains the same. The area \$A\$ of a polygon can be calculated in a known way, but it is not needed for the task at hand, because the area will not be changed by any shear.
See Wikipedia Shear Mapping.
Challenge
Your task is to create a function that, given a polygon, finds an arbitrary sequence of such shears so that the diameter d of the transformed polygon becomes as small as possible.
This is related to a question in mathoverflow and this challenge.
Only those shears should be considered that are parallel to the coordinate axes and that result in a polygon with integer coordinates, i.e., with integer, but potentially negative, \$m\$ in the transformation matrices
\$ \\ \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 & m \\ 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \hspace {3mm}or \hspace {3mm} \begin{pmatrix} x' \\ y' \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ m & 1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} \$
The program shall return the value of the minimum possible squared diameter \$d^2\$ and the transformed vertex coordinates, such that \$min(x'_i) = min(y'_i) = 0\$.
The coordinates can be passed to the function in whatever form seems most appropriate, e.g., as a matrix or as vectors or as a reference to a data structure. It is permissible to overwrite the input coordinates in the result.
If it is possible in the selected language with little effort, then a framework program should be made available that reads and outputs the results in the following format:
\$(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\$
The commas between \$x\$ and \$y\$ and between \$),(\$ are mandatory. The calculated squared diameter shall also be output.
A framework program must not perform any pre- or post-processing other than reading and displaying the data and conversion to/from the required form for the transformation function.
The program should be able to handle polygons with at least 40 vertices.
This is Code Golf, i.e., the shortest code (in bytes) able to solve the problem wins. However, only the length of the transformation function is used for the Code Golf score.
The described form of output is chosen in order to be able to be used as input for a visualization program, e.g., Markus Sigg's PolygonalAreasViewer
Example
Input, a polygon with n=15 and D^2=2810:
(1,1),(3,2),(6,4),(16,11),(23,16),(34,24),(38,27),(43,31),(44,32),(42,31),(39,29),(32,24),(21,16),(6,5),(2,2)
First shear x' = x - y
d^2=1105: (0,1),(1,2),(2,4),( 5,11),( 7,16),(10,24),(11,27),(12,31),(12,32),(11,31),(10,29),( 8,24),( 5,16),(1,5),(0,2)
Second shear y' = y - 2*x'
d^2=193: (0,1),(1,0),(2,0),( 5, 1),( 7, 2),(10, 4),(11, 5),(12, 7),(12, 8),(11, 9),(10, 9),( 8, 8),( 5, 6),(1,3),(0,2)
Third shear: x'' = x' - y'
d^2=82: (-1,1),(1,0),(2,0),( 4, 1),( 5, 2),( 6, 4),( 6, 5),( 5, 7),( 4, 8),( 2, 9),( 1, 9),( 0, 8),(-1, 6),(-2,3),(-2,2)
No further reduction of diameter possible; normalize position x''' = x'' + 2, y''' = y'
Expected return value: 82 (=d^2) and coordinates printed:
(1,1),(3,0),(4,0),(6,1),(7,2),(8,4),(8,5),(7,7),(6,8),(4,9),(3,9),(2,8),(1,6),(0,3),(0,2)
Test Cases
n = 3
A=1/2, D^2=26: (0,0),(1,0),(5,1)
-> d^2= 2: (0,0),(1,0),(1,1)
A=1/2, D^2=74: (0,0),(3,2),(7,5)
-> d^2= 2: (0,0),(1,0),(1,1)
A=50, D^2=233: (-3,2),( 3,-2),(10,10)
-> d^2=169: ( 0,4),(10, 0),( 5,12)
n = 7
A=6.5, D^2=13: (1,0),(2,0),(3,1),(3,2),(1,3),(0,3),(0,2)
-> d^2=13: (1,0),(2,0),(3,1),(3,2),(1,3),(0,3),(0,2)
(input unchanged)
n = 8
A=7, D^2=149: (0,0),(1,1),(-1,0),(-4,-2),(-8,-5),(-9,-6),(-7,-5),(-4,-3)
-> d^2= 10: (3,1),(3,2),( 2,3),( 1, 3),( 0, 2),( 0, 1),( 1, 0),( 2, 0)
n = 15
A=51.5, D^2=18853: (0,0),(13,9),(36,25),(46,32),(43,30),(21,15),(2,2),(-14,-9),(-27,-18),(-50,-34),(-60,-41),(-67,-46),(-64,-44),(-45,-31),(-29,-20)
-> d^2= 82: (9,4),( 9,5),( 8, 7),( 7, 8),( 6, 8),( 3, 7),(1,6),( 0, 5),( 0, 4),( 1, 2),( 2, 1),( 4, 0),( 5, 0),( 7, 1),( 8, 2)
n = 17
A=75.5, D^2=1361: (1,-13),(1,-14),(2,-14),(3,-13),(6,-9),(8,-6),(13,2),(16,7),(20,14),(21,16),(21,17),(20,16),(17,12),(12, 5),(10, 2),(5,-6),(2,-11)
-> d^2= 137: (0, 7),(1, 5),(3, 2),(4, 1),(6, 0),(7, 0),( 9,1),(10,2),(11, 4),(11, 5),(10, 7),( 9, 8),( 7, 9),( 4,10),( 3,10),(1, 9),(0, 8)
n = 19
A=106.5, D^2=11240: (1,1),(2,2),(7,6),(11,9),(26,20),(37,28),(44,33),(61,45),(71,52),(84,61),(87,63),(86,62),(82,59),(67,48),(56,40),(38,27),(31,22),(14,10),(4,3)
-> d^2= 202: (2,3),(1,5),(0,8),( 0,9),( 1,11),( 2,12),( 3,12),( 6,11),( 8,10),(11, 8),(12, 7),(13, 5),(13, 4),(12, 2),(11, 1),( 9, 0),( 8, 0),( 5, 1),(3,2)
n = 20:
A=121: D^2=394: ( 0,0),( 1,0),( 2,1),( 2,2),( 1, 5),( 0, 7),(-2,10),(-3,11),(-6,13),(-8,14),(-11,15),(-12,15),(-13,14),(-13,13),(-12,10),(-11,8),(-9,5),(-8,4),(-5,2),(-3,1)
-> d^2=241: (13,4),(14,5),(15,7),(15,8),(14,10),(13,11),(11,12),(10,12),( 7,11),( 5,10),( 2, 8),( 1, 7),( 0, 5),( 0, 4),( 1, 2),( 2,1),( 4,0),( 5,0),( 8,1),(10,2)
n = 24:
A=260, D^2=937: ( 0, 0),( 2, 3),( 2, 4),(1, 5),(-1, 6),(-2, 6),(-5, 5),(-7, 4),(-10, 2),(-14,-1),(-15,-2),(-18,-6),(-20,-9),(-21,-11),(-22,-14),(-22,-15),(-21,-16),(-19,-17),(-18,-17),(-15,-16),(-13,-15),(-9,-12),(-8,-11),(-5,-7)
-> d^2=578: (13,17),(12,20),(11,21),(9,22),( 6,23),( 5,23),( 3,22),( 2,21),( 1,19),( 0,16),( 0,15),( 1,11),( 2, 8),( 3, 6),( 5, 3),( 6, 2),( 8, 1),( 11, 0),( 12, 0),( 14, 1),( 15, 2),(16, 5),(16, 6),(15,10)
A=238.5, D^2=657: (6,1),(5,1),(3,2),(2,3),(1, 5),(1, 6),(2,10),(3,13),(4,15),(6,18),(9,22),(10,23),(13,25),(14,25),(15,24),(16,22),(17,19),(17,17),(16,13),(15,10),(14,8),(12,5),(11,4),(8,2)
-> d^2=409: (5,2),(4,3),(2,6),(1,8),(0,11),(0,12),(1,15),(2,17),(3,18),(5,19),(8,20),( 9,20),(12,19),(13,18),(14,16),(15,13),(16, 9),(16, 7),(15, 4),(14, 2),(13,1),(11,0),(10,0),(7,1)
n = 27:
A=343.5, D^2=1233: ( 0,0),( 1,0),( 4,1),( 5,2),( 5,3),( 4,5),( 2,8),( 1,9),(-2,11),(-4,12),(-9,14),(-12,15),(-16,16),(-21,17),(-22,17),(-25,16),(-27,15),(-28,14),(-28,13),(-27,10),(-26,8),(-25,7),(-23,6),(-18,4),(-15,3),(-11,2),(-6,1)
-> d^2= 788: (18,0),(19,0),(23,1),(25,2),(26,3),(27,5),(28,8),(28,9),(27,11),(26,12),(23,14),( 21,15),( 18,16),( 14,17),( 13,17),( 9,16),( 6,15),( 4,14),( 3,13),( 1,10),( 0,8),( 0,7),( 1,6),( 4,4), (6,3), (9,2),(13,1)
n = 38:
A=360, D^2=71444: (1,1),(11,9),(21,19),(31,29),(41,39),(51,49),(61,59),(71,69),(81,79),(91,89),(101,99),(111,109),(121,119),(131,129),(141,139),(151,149),(161,159),(171,169),(181,179),(191,189),(181,181),(171,171),(161,161),(151,151),(141,141),(131,131),(121,121),(111,111),(101,101),(91,91),(81,81),(71,71),(61,61),(51,51),(41,41),(31,31),(21,21),(11,11)
-> d^2=32404: (0,0),( 2,0),( 2,10),( 2,20),( 2,30),( 2,40),( 2,50),( 2,60),( 2,70),( 2,80),( 2, 90),( 2,100),( 2,110),( 2,120),( 2,130),( 2,140),( 2,150),( 2,160),( 2,170),( 2,180),( 0,180),( 0,170),( 0,160),( 0,150),( 0,140),( 0,130),( 0,120),( 0,110),( 0,100),( 0,90),( 0,80),( 0,70),( 0,60),( 0,50),( 0,40),( 0,30),( 0,20),( 0,10)
