我无法形成一种算法来确定用户以任何顺序输入的 12 个顶点是否会在 2D 平面中形成十字形。 从我的角度来看，它可以是两个相交的矩形。
我是否应该选择通过比较距离来暴力破解它， 我最终会得到与 12 个顶点的 67 个距离，要比较所有顶点是不可行的。 我可以使用十字形或形状的任何特征吗？
最佳答案
您想要的是由两个相交的直线矩形定义的十字形状，所有四个边的突起都大于零。我相信以下算法将完全为您确定。
确保 12 个点中没有一个是相同的。
12 个点中应该只有 4 个不同的 X 值。将它们按升序放入我们称为 X 向量的数组中。
对 Y 值执行相同操作，创建具有 4 个不同值的 Y 向量。
制作一个 4x4 数组，将所有单元格初始化为零。
使用 X 和 Y 值以及 X 向量和 Y 向量遍历 12 个值中的每一个，以选择 4x4 数组中的一个单元格进行递增。因此，如果您有一个点 (12,9)，并且 12 在 X 向量的 [0] 条目中，而 9 在 Y 向量的 [2] 条目中，您将递增 [0,2] 单元格4x4 阵列。
现在您的 4x4 阵列应该看起来完全像这样:
0, 1, 1, 0 1, 1, 1, 1 1, 1, 1, 1 0, 1, 1, 0
如果是这样，那么它就是您所定义的十字。如果不是，或者如果它在任何前面的步骤都失败了，那么它就不是一个十字。
关于algorithm - 如何确定具有给定顶点的十字形状，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52916611/