地图权重计算（算法题）_二维地图左上角到右下角最小权重

问题描述

题目：权重计算

描述：

考虑一个19x19的网格，每个网格都可以赋予一个权重。现在，给定一个坐标范围在 (−1500,1500),(−1500,1500)(−1500,1500),(−1500,1500) 之内的数据点，你的任务是为这个数据点在19x19的网格中确定权重。

数据点可能的位置与相应的权重计算如下：

1. 数据点在某个网格的中心：此时，该数据点所在的那个网格权重为1，其余所有网格的权重为0。
2. 数据点位于四个网格的交点：这四个相交的网格各自的权重为0.25，其余所有网格的权重为0。
3. 数据点在网格的内部边界但非交点上：此时，数据点位于两个网格的共同边界上。例如，如果数据点在两个网格的水平共同边界上，则这两个网格的权重各为0.5，其余所有网格的权重为0。同理，如果数据点在两个网格的垂直边界上，这两个网格的权重也各为0.5。
4. 数据点位于整体网格系统的边界上：在这种特殊情况下，所有网格的权重都为0，因为数据点在整个网格系统的外部边界上。
5. 数据点在某个网格的内部角上但非交点需要安装距离来分配权重：例如，如果数据点在左下角上但不在四个网格的交点，你需要计算与该点相邻的左侧、下方、左下角和当前所在的网格的权重，使得总权重为1，需要计算当前点和这四个网格中心的距离，然后根据这个距离的比例来分配这个权值。

输入：

• 一个元组，代表数据点的坐标 (x,y) ，其中 x,y∈[−1500,1500]x,y∈[−1500,1500]。

输出：

• 一个 19×19 的二维数组，表示每个网格的权重。

思路分析

测试数据

1. 数据点在某个网格的中心：

测试点： (0,0)

解释： 这是整个19x19网格系统的中心点。在这种情况下，中心网格权重为1，其余网格权重为0。

预测结果： 19x19的二维数组中，中心格权重为1，其余为0。

测试通过

---

2. 数据点位于四个网格的交点：

测试点： (-1184.22, -1184.22)

解释： 数据点位于第一个行和第一个列的交点上。

**预测结果：**其中(1,1)、(1,2)、(2,1)和(2,2)的权重都是0.25。

测试通过

---

**3. **数据点在网格的内部边界但非交点上

• 输入：(0, -1500 + CELL_SIZE)
• 输出：一个19x19的二维数组，其中两个相邻网格的权重为0.5，其余网格的权重为0。
• 解释：数据点 (-1184.22, -1294.22) 位于两个相邻网格的内部边界上，其中一个网格在左侧，另一个在右侧。因此，这两个相邻网格的权重都为0.5，其余网格的权重都是0。

测试通过，需要注意的是，编程里面的坐标相对于数学里面的是倒过来的

---

4. 数据点位于整体网格系统的边界上：

测试点： (-1500, 0)

解释： 数据点位于整个网格系统的左边界上。

预测结果： 所有网格权重为0。

通过测试

---

5.数据点在某个网格的内部角上但非交点需要安装距离来分配权重：

测试点： (-1125, 1125)

解释： 给定的数据点 (−1125,1125)位于第 2 列和第 16 行的网格内部角上。

预测结果： （当前网格）的权重应该最大，（左侧网格）的权重次之，网格（上方网格）的权重再次之，网格 （左上角网格）的权重最小，其余为0。

测试通过

测试代码

下面的代码，是用来通过测试数据，获得测试数据结果的。测试数据就是上面写的

import numpy as np

# 定义单元格大小
CELL_SIZE = 3000 / 19  # 单元格的尺寸
epsilon = 1e-3  # 容差


def get_grid_position_and_distances(x, y):
    """
    计算给定点的网格位置以及到四个边界的距离。
    """
    # 计算x和y坐标所对应的格子位置
    grid_x = int((x + 1500) // CELL_SIZE)
    grid_y = int((y + 1500) // CELL_SIZE)

    # 计算到四个边界的距离
    dist_left = x - (-1500 + grid_x * CELL_SIZE)
    dist_right = (-1500 + (grid_x + 1) * CELL_SIZE) - x
    dist_top = y - (-1500 + grid_y * CELL_SIZE)
    dist_bottom = (-1500 + (grid_y + 1) * CELL_SIZE) - y

    return grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom


def calculate_weight(x, y):
    """
    根据点的位置计算权重矩阵。
    """
    # 获取点的网格位置和距离信息
    grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom = get_grid_position_and_distances(x, y)
    weight_matrix = np.zeros((19, 19))  # 初始化权重矩阵为全零

    # 判断是否为外部边界点
    if x == 1500 or x == -1500 or y == 1500 or y == -1500:
        return weight_matrix  # 返回全零矩阵

    # 判断是否为中心点
    if np.isclose(x, -1500 + (grid_x + 0.5) * CELL_SIZE) and np.isclose(y, -1500 + (grid_y + 0.5) * CELL_SIZE):
        weight_matrix[grid_y, grid_x] = 1
        return weight_matrix

    # 判断是否为交叉点
    if (np.isclose(x, -1500 + grid_x * CELL_SIZE) or np.isclose(x, -1500 + (grid_x + 1) * CELL_SIZE)) and \
            (np.isclose(y, -1500 + grid_y * CELL_SIZE) or np.isclose(y, -1500 + (grid_y + 1) * CELL_SIZE)):
        weight_matrix[grid_y, grid_x] = 0.25
        weight_matrix[grid_y + 1, grid_x] = 0.25
        weight_matrix[grid_y, grid_x + 1] = 0.25
        weight_matrix[grid_y + 1, grid_x + 1] = 0.25
        return weight_matrix

    # 判断是否为内部边界点
    if np.isclose(dist_left, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x - 1] = 0.5
        return weight_matrix
    if np.isclose(dist_right, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x + 1] = 0.5
        return weight_matrix
    if np.isclose(dist_top, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y - 1, grid_x] = 0.5
        return weight_matrix
    if np.isclose(dist_bottom, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y + 1, grid_x] = 0.5
        return weight_matrix

    # 重新计算内部角落点的权重
    # 计算到四个近邻格子中心的距离
    distances = [
        np.sqrt(dist_left ** 2 + dist_top ** 2),
        np.sqrt(dist_right ** 2 + dist_top ** 2),
        np.sqrt(dist_left ** 2 + dist_bottom ** 2),
        np.sqrt(dist_right ** 2 + dist_bottom ** 2)
    ]
    # 计算距离的倒数
    inverse_distances = [1 / (d + epsilon) for d in distances]  # 添加epsilon以防止除以零
    total_inverse_distance = sum(inverse_distances)
    # 根据距离的倒数分配权重
    weights = [idist / total_inverse_distance for idist in inverse_distances]

    weight_matrix[grid_y, grid_x] = weights[0]
    weight_matrix[grid_y, grid_x - 1] = weights[1]
    weight_matrix[grid_y - 1, grid_x] = weights[2]
    weight_matrix[grid_y - 1, grid_x - 1] = weights[3]

    return weight_matrix

# 定义测试点
test_points = [
    (0, 0), (-1184.22, -1184.22),(0, -1500 + CELL_SIZE), (-1500, 0), (-1125, 1125)
]


for point in test_points:
    print(f"Test point: {point}")
    print(calculate_weight(*point))
    print("=" * 40)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

测试结果

---

权重计算问题代码设计思路

1. get_grid_position_and_distances函数:
   • 该函数接收一个点的x和y坐标作为输入。
   • 它首先计算给定点在网格系统中的位置(grid_x和grid_y)。
   • 然后，它计算点到其包含网格的四个边界的距离（dist_left, dist_right, dist_top, dist_bottom）。
   • 函数返回这些值。
2. calculate_weight函数:
   • 该函数接收一个点的x和y坐标作为输入。
   • 它首先调用get_grid_position_and_distances函数来获取网格位置和边界距离。
   • 接下来，它根据不同的情况为每个网格分配权重：
     • 如果点位于网格系统的外部边界上，所有网格的权重都为0。
     • 如果点位于某个网格的中心，那个网格的权重为1，其他网格的权重为0。
     • 如果点位于四个网格的交点，这四个网格的权重都为0.25。
     • 如果点位于两个网格的内部边界上，这两个网格的权重都为0.5。
     • 如果点位于某个网格的内部角上但不在交点上，它计算点到四个邻近格子的中心的距离，并根据这些距离分配权重。

完整的代码

需要注意的是，这个代码不能够在jupyter里面运行，因为print函数对于特别费时间，数据量大容易拖垮浏览器，所以用的pycharm展示的，算法运行效率很高，如果去掉print那么一秒不到就可以出结果

import numpy as np

# 定义单元格大小
CELL_SIZE = 3000 / 19  # 单元格的尺寸
epsilon = 1e-3  # 容差

def get_grid_position_and_distances(x, y):
    """
    计算给定点的网格位置以及到四个边界的距离。
    """
    # 计算x和y坐标所对应的格子位置
    grid_x = int((x + 1500) // CELL_SIZE)
    grid_y = int((y + 1500) // CELL_SIZE)

    # 计算到四个边界的距离
    dist_left = x - (-1500 + grid_x * CELL_SIZE)
    dist_right = (-1500 + (grid_x + 1) * CELL_SIZE) - x
    dist_top = y - (-1500 + grid_y * CELL_SIZE)
    dist_bottom = (-1500 + (grid_y + 1) * CELL_SIZE) - y

    return grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom

def calculate_weight(x, y):
    """
    根据点的位置计算权重矩阵。
    """
    # 获取点的网格位置和距离信息
    grid_x, grid_y, dist_left, dist_right, dist_top, dist_bottom = get_grid_position_and_distances(x, y)
    weight_matrix = np.zeros((19, 19))  # 初始化权重矩阵为全零

    # 判断是否为外部边界点
    if x == 1500 or x == -1500 or y == 1500 or y == -1500:
        return weight_matrix  # 返回全零矩阵

    # 判断是否为中心点
    if np.isclose(x, -1500 + (grid_x + 0.5) * CELL_SIZE) and np.isclose(y, -1500 + (grid_y + 0.5) * CELL_SIZE):
        weight_matrix[grid_y, grid_x] = 1
        return weight_matrix

    # 判断是否为交叉点
    if (np.isclose(x, -1500 + grid_x * CELL_SIZE) or np.isclose(x, -1500 + (grid_x + 1) * CELL_SIZE)) and \
            (np.isclose(y, -1500 + grid_y * CELL_SIZE) or np.isclose(y, -1500 + (grid_y + 1) * CELL_SIZE)):
        weight_matrix[grid_y, grid_x] = 0.25
        weight_matrix[grid_y + 1, grid_x] = 0.25
        weight_matrix[grid_y, grid_x + 1] = 0.25
        weight_matrix[grid_y + 1, grid_x + 1] = 0.25
        return weight_matrix

    # 判断是否为内部边界点
    if np.isclose(dist_left, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x - 1] = 0.5
        return weight_matrix
    if np.isclose(dist_right, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y, grid_x + 1] = 0.5
        return weight_matrix
    if np.isclose(dist_top, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y - 1, grid_x] = 0.5
        return weight_matrix
    if np.isclose(dist_bottom, 0, atol=epsilon):
        weight_matrix[grid_y, grid_x] = 0.5
        weight_matrix[grid_y + 1, grid_x] = 0.5
        return weight_matrix

    # 重新计算内部角落点的权重
    # 计算到四个近邻格子中心的距离
    distances = [
        np.sqrt(dist_left ** 2 + dist_top ** 2),
        np.sqrt(dist_right ** 2 + dist_top ** 2),
        np.sqrt(dist_left ** 2 + dist_bottom ** 2),
        np.sqrt(dist_right ** 2 + dist_bottom ** 2)
    ]
    # 计算距离的倒数
    inverse_distances = [1 / (d + epsilon) for d in distances]  # 添加epsilon以防止除以零
    total_inverse_distance = sum(inverse_distances)
    # 根据距离的倒数分配权重
    weights = [idist / total_inverse_distance for idist in inverse_distances]

    weight_matrix[grid_y, grid_x] = weights[0]
    weight_matrix[grid_y, grid_x - 1] = weights[1]
    weight_matrix[grid_y - 1, grid_x] = weights[2]
    weight_matrix[grid_y - 1, grid_x - 1] = weights[3]
    
    return weight_matrix


# 加载数据
data = np.load('D:\系统默认\桌面\永信\B4013-算法题\part.npy')

# 遍历数据并计算权重
for point in data:
    source_x, source_y = point
    print(compute_weights_for_point(source_x, source_y))

print("运行完了")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

运行结果