我试图找到切比雪夫距离下的一组点的质心。我编写了一个程序,该程序显然适用于我尝试过的情况,但显然对我无法访问的某些边缘情况给出了错误的答案。[元备注:我会标记这个作业,但标签已被淘汰]
为了达到目的,质心是与一组点具有最小平均距离的点。二维上两点 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]
这是我的理由:切比雪夫度量与二维旋转下的曼哈顿距离相同。我基本上找到曼哈顿质心,这与点的常规平均值相同,然后在相邻的积分点中搜索以获得实际的切比雪夫质心。但我似乎无法在我的代码中找到错误。