gralhix004 | 使用几何和CUDA GPU编程对随机小岛图像进行地理定位 2026年8月16日 注意：这是真正的人类作品，没有使用大型语言模型生成。我编写此页面作为Sofia Santos | Gralhix创建的挑战gralhix 004的总结。您可以在此处查看、克隆并本地试用所有代码文件和包含所有说明的最终报告，网址为github。任务简介：这是一张位于一个岛屿上的度假村的照片。 a) 度假村的名字是什么？ b) 岛屿的坐标是多少？ c) 拍摄照片时相机朝向哪个方向？ 在我看来，使用谷歌镜头解决这个挑战是在浪费一个有趣的机会，所以我决定用数学和编程来解决它。 a] 元数据 当然，首先要查看的是元数据。我在我的Linux系统上运行了这个命令： > exiftool main.png 文件类型：WEBP（无损） MIME类型：image/webp 图像宽度：736 图像高度：515 正如预期，没有有用的信息。没有EXIF，没有GPS，没有相机品牌或型号。 b] 构建指纹 从图片中可以看到有3个陆地块：P0：小岛本身，P1：右侧的岛屿，P2：左侧的前方岛屿（有山峰）。我无法为此图像制作正确的鸟瞰图透视模型，因为显然这张照片是由无人机拍摄的，根本无法估计高度（元数据中也没有找到）。所以我必须凭直觉进行估计，我只想要这3个岛屿之间的相对距离和那个三角形的角度。我构建了一个小的点击GUI 01_triangle_gui.py，让用户按顺序记录每个点的像素坐标，并计算三角形的几何形状。由于凭眼睛点击准确中心并不是完全精确的，因此我在搜索时对两个值添加了±20%的容差带。 c] 搜索 指纹确定后，下一步就是检查地球上的每个真实陆地块！我使用OpenStreetMap的分割土地多边形集作为数据集land-polygons-split-4326，这是包含全球海岸线矢量的完整WGS84，大小为882 MB。我创建了启发式过滤器（完全是凭直觉和无形证据），花了几天（是的，整整几天）调整数值和大量试验，直到我得到了有效的过滤器配方。 01] 热带纬度边界框 $$ -30° ext{到} 30° $$ 照片中的小岛看起来是热带的，所以我决定将任何在热带以外的地方立即排除，然后再进行任何昂贵的几何工作。恰好有141,131个土地多边形通过了这一过滤。 02] 局部密度过滤 $$ N_{5 ext{km}}(p) ext{小于或等于} 10 $$ $ N_{5 ext{km}}(p) $ 计算有多少其他重心落在点（p）的5公里范围内。上限是10：如果某个小岛在此范围内有超过10个邻居，它就位于密集的礁石场、拥挤的海岸线或群岛杂乱中，而不是像照片所示的那样小而孤立的3-4个岛屿群。这将候选者减少到51,576。 03] 聚类 对于每个生存点，找到20公里范围内的每个其他点（启发式，根据图像观察）。如果它有至少2个相邻点（总共有3个点），那么它就是一个聚类。没有3个以上相邻的点将被丢弃，它们根本无法形成三角形。 tree = cKDTree(f_coords) neigh = tree.query_ball_point(f_coords, CLUSTER_RADIUS_KM / 111.0) clusters = set(tuple(sorted(n)) for n in neigh if len(n) >= 3) $$ ext{点的数量} ext{满足} ext{distance}(p,q) ext{小于等于} 20 ext{km} ext{的集合大于等于} 3 $$ 这将聚类数量减少到23,500。 04] 生成三元组 对于每个聚类，成为候选三角形的每组三个点的组合。那是 $ C(n, 3) $，对于大聚类来说爆炸性增加。例如：一个由60个点组成的聚类单独就能产生34,220个三元组。因此，每个聚类首先被限制到60个点，通过大小进行采样，而不是随机选择。 $$ inom{n}{3} = rac{n(n-1)(n-2)}{6} $$ def stratified_sample(idx_arr, area_arr, cap): order = np.argsort(area_arr[idx_arr]) n_small = cap // 3 n_large = cap // 3 n_mid = cap - n_small - n_large mid_start = max(0, (len(idx_arr) - n_large - n_mid) // 2) keep = np.unique(np.concatenate([order[:n_small], order[-n_large:], order[mid_start:mid_start + n_mid]])) return idx_arr[keep] def gen_cluster_triples(idx_arr): local = np.array(list(itertools.combinations(range(len(idx_arr)), 3)), dtype=np.int64) return idx_arr[local] 这个采样方法获取三分之一小岛屿、三分之一大岛屿和三分之一中型岛屿，而不是使用完整聚类或随机切割。23,500个聚类总共产生了80,690,777个三元组！！ 05] 匹配，基于GPU 我为每个三元组分配了一个CUDA线程。每个线程按土地面积对其3个点进行排序，以找出P0（最小，即度假村小岛），然后使用另两个点的缠绕方向来分配P1和P2： long long i = blockIdx.x * (long long)blockDim.x + threadIdx.x; if (i >= n_triples) return; int pos[3] = {0, 1, 2}; for (int a1 = 1; a1 < 3; a1++) { int key = pos[a1]; double keyval = a[key];