0

我试图找到切比雪夫距离下的一组点的质心。我编写了一个程序，该程序显然适用于我尝试过的情况，但显然对我无法访问的某些边缘情况给出了错误的答案。[元备注：我会标记这个作业，但标签已被淘汰]

为了达到目的，质心是与一组点具有最小平均距离的点。二维上两点 p 和 q 的切比雪夫距离为

切比雪夫距离

此外，我仅限于具有积分坐标的点。

这是我的代码：

sum_x=0; sum_y=0
for p in points:
    sum_x = sum_x + p[0]
    sum_y = sum_y + p[1]
center_x = int(sum_x/N)
center_y = int(sum_y/N)

directions = [(-1,-1),
     (-1,0),
     (-1,1),
     (0,-1),
     (0,0),
     (0,1),
     (1,-1),
     (1,0),
     (1,1)]

distances = [0] * len(directions)
for p in points:
    for i in range(len(directions)):
        distances[i] = distances[i] + max(abs(center_x+directions[i][0]-p[0]),abs(center_y+directions[i][1]-p[1]))

best_direction = min(range(len(directions)), key = lambda i:distances[i])

print "centroid = (", center_x+directions[best_direction][0],",", center_y+directions[best_direction][1],")"

print "total distance = ", distances[best_direction]

这是我的理由：切比雪夫度量与二维旋转下的曼哈顿距离相同。我基本上找到曼哈顿质心，这与点的常规平均值相同，然后在相邻的积分点中搜索以获得实际的切比雪夫质心。但我似乎无法在我的代码中找到错误。

4

1 回答 1

1

你的理由在一个方面是不正确的。曼哈顿质心不是点的平均值。例如，取点集 (0, 0)；(1, 0); (100, 0)。平均值为 (33.66, 0)，但我们可以通过选择 (1, 0) 来做得更好。再做几个例子，你应该很容易看到真正的答案。

此外，您提到 Chebyshev 度量等效于旋转下的曼哈顿距离，但您不会在代码中的任何位置旋转点。这似乎至少不一致：您不应该在旋转空间中计算曼哈顿质心吗？

于 2012-10-05T02:31:01.473 回答