问题描述
题目：权重计算
描述：
考虑一个19x19的网格，每个网格都可以赋予一个权重。现在，给定一个坐标范围在 (−1500,1500),(−1500,1500)(−1500,1500),(−1500,1500) 之内的数据点，你的任务是为这个数据点在19x19的网格中确定权重。
数据点可能的位置与相应的权重计算如下：
- 数据点在某个网格的中心：此时，该数据点所在的那个网格权重为1，其余所有网格的权重为0。
- 数据点位于四个网格的交点：这四个相交的网格各自的权重为0.25，其余所有网格的权重为0。
- 数据点在网格的内部边界但非交点上：此时，数据点位于两个网格的共同边界上。例如，如果数据点在两个网格的水平共同边界上，则这两个网格的权重各为0.5，其余所有网格的权重为0。同理，如果数据点在两个网格的垂直边界上，这两个网格的权重也各为0.5。
- 数据点位于整体网格系统的边界上：在这种特殊情况下，所有网格的权重都为0，因为数据点在整个网格系统的外部边界上。
- 数据点在某个网格的内部角上但非交点需要安装距离来分配权重：例如，如果数据点在左下角上但不在四个网格的交点，你需要计算与该点相邻的左侧、下方、左下角和当前所在的网格的权重，使得总权重为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)
测试结果
权重计算问题代码设计思路
- get_grid_position_and_distances函数:
- 该函数接收一个点的x和y坐标作为输入。
- 它首先计算给定点在网格系统中的位置(grid_x和grid_y)。
- 然后，它计算点到其包含网格的四个边界的距离（dist_left, dist_right, dist_top, dist_bottom）。
- 函数返回这些值。
- 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("运行完了")
运行结果
