在一个数组中，如何知道选定的索引可以创建一个矩形或正方形？

Question

我有一个数组是这样的。

array = [
0, 1, 2, 3,
4, 5, 6, 7,
8, 9, 10, 11,
12, 13, 14, 15
];

还有一个输入，就像下面这样

input = [5,6,9,10]

当我们把这个输入和数组进行比较时 我们可以看到这个输入实际上在数组上创建了一个正方形。

input = [6,9,10]

而这个则相反，创建的是一个三角形。

我想写一个函数，检查给定的输入是否创建了一个正方形。矩形. 如果是返回true，否则返回false。我怎么写这个函数呢？

Answer 1

你需要事先确定源数组是一个正方形还是一个矩形。

即使数组不是正方形，W=4，H=4，但内部表示方法是相同的，如

[ 0, 1,  2,  3,  4,  5,  6,  7,
  8, 9, 10, 11, 12, 13, 14, 15 ];

是一个矩形，W=8，H=2。

你可以看到，如果W=4，(5,6,9,10)是一个正方形，但如果W=8，则什么都不是。

假设你知道数组的宽度 W 因此它的高度H，也就是数组的大小除以W），那么如果你有一个元素N，比如5，它在WH系统中的二维坐标是

{ 
  x: N % W, 
  y: floor(N / W)
}

所以你看到N=5变成了（1,1）。一旦你有了所有元素的二维坐标，检查形状就很简单了。

正方形和矩形：你有四个元素，（x1，y1），（x2，y2），（x3，y3），（x4，y4）。如果x1=x3，y1=y2，x2=x4，y3=y4，则它是一个正方形或矩形，方向像数组。如果，那么，x2-x1等于y3-y1，它是一个正方形；否则是一个矩形。

你可以添加更复杂的条件来检查其他排列方式。例如，1-2边是（x2-x1）的平方根。(x2-x1)+(y2-y1)(y2-y1)。1-3和2-4的对角线和其他所有的边也是如此。如果对角线长度相等，则是长方形（或正方形）。如果，另外，1-2和2-3的边相等，那么它是一个正方形。无论正方形的方向如何，这个更复杂的条件都适用（例如，(2,6,8,10)将被认为是一个正方形）。

三点总是一个三角形，除非三条边中的两条边之和恰好等于第三条边（这是个 退化三角形). 如果一条边的长度的平方等于另外两条边的平方之和，就得到一个长方形。检查等腰三角形和等边形是很直接的。

如果你不知道W，那么你需要将数组的大小S因式化，尝试所有的可能性。16是2*2*2*2，所以你需要检查W=2，W=4，W=8和W=16。

Answer 2

假设矩形必须是轴对齐的，而且输入是有序的，那么 [a, b, c, d] 形成一个矩形，如果 (4096*a + 256*b + 16*d + c) % 17 = 0.

这只适用于0到15的特殊排列。如果你有25个值(0-24)类似的排列，你可以使用 (15625*a + 625*b + 25*d + c) % 26 = 0 而不是。这个模式是可以通用的。

Answer 3

你可以通过定义两个方法来检查给定的输入是一个矩形还是一个三角形 isRectangle 和 isTriangle 并称

return isTriangle(input) OR is Rectangle(input)

与

isRectangle(input):
   return length(input) == 4 AND input[0] < input [1] < input[2] < input [3]

和

isTriangle(input):
   return length(input) == 3 AND input[0] < input [1] < input[2]