我想我会检查矩阵中的每个点,并根据它的邻居找出它的质量。点的质量会随着距离的平方而下降。然后你可以选择距离彼此最小的前四个点。
下面是一些Python代码,我一起试着说明找出每个点的质量的方法。
matrix = [[1.0 if x == "X" else 0.0 for x in y] for y in """.XX......
.XXX..X..
.....XXX.
......X..
.XX......
.X.......
.X.......
....XX...
....XX...""".split("\n")]
HEIGHT = len(matrix)
WIDTH = len(matrix[0])
Y_RADIUS = HEIGHT/2
X_RADIUS = WIDTH/2
要计算质量对于给定的点:
def distance(x1, y1, x2, y2):
'Manhattan distance http://en.wikipedia.org/wiki/Manhattan_distance'
return abs(y1 - y2) + abs(x1 - x2)
def mass(m, x, y):
_mass = m[y][x]
for _y in range(max(0, y - Y_RADIUS), min(HEIGHT, y + Y_RADIUS)):
for _x in range(max(0, x - X_RADIUS), min(WIDTH, x + X_RADIUS)):
d = max(1, distance(x, y, _x, _y))
_mass += m[_y][_x]/(d * d)
return _mass
注:我使用Manhattan距离(又名Cityblock,又名出租车几何)在这里,因为我不使用你的榜样矩阵一些设置认为使用欧几里德距离的附加精度值得调用sqrt()的代价。
迭代通过我们的矩阵和建立一个元组列表像(X,Y,质量(X,Y)):
point_mass = []
for y in range(0, HEIGHT):
for x in range(0, WIDTH):
point_mass.append((x, y, mass(matrix, x, y)))
排序的质量对每个点的地址列表:
from operator import itemgetter
point_mass.sort(key=itemgetter(2), reverse=True)
望着在排序列表顶部9点:
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 1, 4.6736111111111107)
(1, 4, 4.5938888888888885)
(2, 0, 4.54)
(4, 7, 4.4480555555555554)
(1, 5, 4.4480555555555554)
(5, 7, 4.4059637188208614)
(4, 8, 4.3659637188208613)
如果我们将努力从最高到最低,并过滤接[R远点过于接近已经看到了,我们会得到点(我做手工,因为我已经用完了时间,现在做在代码中...):
(6, 2, 6.1580555555555554)
(2, 1, 5.4861111111111107)
(1, 4, 4.5938888888888885)
(4, 7, 4.4480555555555554)
哪个一个非常直观的结果,只需查看矩阵(请注意,与您的示例进行比较时,坐标为零)。