搜索/排序多维数组

Question

我已经创建了一个基于圆周长的x/y坐标的多维数组。一个对象可以沿着弧线拖动(在javascript中)，然后‘放到’它的任何地方。问题是，我需要找到与对象“放置”位置最接近的x和y坐标。

我目前的解决方案包括遍历数组并找到与x最接近的值，然后再次循环以找到y坐标，但它看起来不是很干净，而且存在问题。

有人有什么建议吗？

谢谢!

Answer 1

那么，让我们看看。我们假设一组预定义的(x，y)坐标。您被给予另一个点，并且必须找到数组中离该给定点最近的元素。我假设“最近”是指从给定点到其他每个点的最小毕达哥拉斯距离或欧几里得距离。

最简单的算法可能是最好的(如果你想看看Wikipedia中的其他算法，那就试试吧)。由于您没有为我们提供任何结构代码，因此我将假设一个对象数组，每个对象都有一个x和一个y属性，对于给定点也是如此。

var findNearestPoint = function (p, points) {
  var minDist = Number.POSITIVE_INFINITY,
      minPoint = -1,
      i,
      l,
      curDist,
      sqr = function(x) { return x * x; };

  for (i = 0, l = points.length; i < l; i++) {
    curDist = sqr(p.x - points[i].x) + sqr(p.y - points[i].y);
    if (curDist < minDist) {
      minDist = curDist;
      minPoint = i;
    }
  } 
  return points[i];
};

(未经测试，但您已经明白了这一点。)

Answer 2

如果您的数组是按顺序创建的(即从最小到最大或从最大到最小)，则可以使用引入二进制搜索算法。

1. 获取x数组的中间元素。
2. 如果x等于您的值，则停止并查找y，否则。
   1. 如果x较低，则在数组的下半部分搜索(从步骤1开始)。
   2. 如果x较高，则在数组的上半部分搜索(从步骤1).

开始

​

然后在y上使用相同的公式，你可能需要稍微修改一下算法，这样它才能与最匹配的元素一起工作。由于没有看到您的数组，我无法提供解决问题的代码。