使用几何和 CUDA 编程对随机岛屿进行地理定位

格拉希克斯004 |使用几何和 CUDA GPU 编程对随机岛图像进行地理定位 16-08-2026 注意：这是真正的人类工作，没有使用 LLM 生成。我写此页是为了应对 Sofia Santos 发起的 gralhix 004 挑战 |格拉尔希克斯。您可以在 github 上查看、克隆和本地尝试所有代码文件和最终报告以及所有说明。任务简介：这是一张位于岛上的度假村的照片。 a) 度假村的名称是什么？ b) 该岛的坐标是多少？ c) 拍摄照片时相机面向哪个基本方向？在我看来，用谷歌镜头解决这个挑战是浪费一个有趣的机会，所以决定用数学和编程来解决它。 a] 元数据 当然，您首先要寻找的是元数据。在我的 linux void :> exiftool main 上运行它。 png 文件类型：WEBP（无损） MIME 类型：image / webp 图像宽度：736 图像高度：515 正如预期的那样，这里没有任何用处。没有 EXIF、没有 GPS、没有相机品牌或型号。 b]构建指纹U可以从img中看到，有3个陆地：P0：小岛本身，P1：右岛，P2：左前岛（有山峰）我无法制作该图像的正确鸟瞰透视模型，因为显然该图像是由无人机拍摄的，根本无法估计海拔（并且在元数据中没有找到）。所以我必须凭直觉估计，我只想要 3 个岛屿之间的相对距离和该三角形的角度。我构建了一个小型点击 GUI 01_triangle_gui.py，它按顺序记录每个点的像素坐标并计算三角形的几何形状。由于通过肉眼点击精确中心并不完全精确，因此我在搜索时在两个值周围添加了 ±20% 的公差带。 c] 搜索 指纹锁定后，下一步就是对照指纹检查地球上每一个真实的陆地！我使用 OpenStreetMap 的分割土地多边形集作为数据集 land-polygons-split-4326 ，WGS84 中的完整全球海岸线向量，大小为 882 MB 。我创建了启发式过滤器（全部通过直觉和无形的证据），花了几天（是的一整天）调整值和大量的试验和错误，直到我得到了这个有效的过滤器配方。 01] 热带纬度边界框 $$ -30° \le latitude \le 30° $$ 照片中的小岛看起来像热带地区，所以我决定在进行任何昂贵的几何工作之前立即扔掉热带地区以外的任何东西。正好有 141,131 个陆地多边形在带状滤波器中幸存下来。 02] 局部密度过滤器 $$ N_{5\text{km}}(p) \le 10 $$ $ N_{5\text{km}}(p) $ 计算有多少个其他质心落在点 (p) 的 5 公里范围内。上限为 10：如果一个小岛有超过 10 个相邻的岛屿，则它位于茂密的珊瑚礁区、拥挤的海岸线或杂乱的群岛中，而不是像照片所示的由 3-4 个岛屿组成的小型孤立岛屿群。这使得候选人减少至 51,576 人。 03] 聚类 对于每个幸存点，找到 20 公里内的所有其他点（启发式，通过图像观察）。如果它至少有 2 个相邻的邻居（总共 3 分），则它是一个簇。附近没有 3+ 簇的点将被丢弃，它们根本无法形成三角形。树 = cKDTree ( f_coords ) neigh = 树 . query_ball_point ( f_coords , CLUSTER_RADIUS_KM / 111.0 ) Clusters = set ( tuple ( Sorted ( n )) for n in neigh if len ( n ) >= 3 ) $$ \left|\{q : \text{dist}(p,q) \le 20\,\text{km}\}\right| \ge 3 $$ 缩减为 23,500 个簇。 04]生成三元组对于每个簇，其内部3个点的每个组合都成为候选三角形。这就是 $ C(n, 3) $，对于大簇来说它会快速爆炸，例如：60 个点的簇本身已经给出了 34,220 个三元组。因此，每个簇首先被限制为 60 个点，按大小采样，而不是随机采样。 $$ \binom{n}{3} = \frac{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 * (长长) blockDim 。 x + 线程Idx 。 x ; if ( i >= n_triples ) 返回 ; int pos [ 3 ] = { 0 , 1 , 2 }; for ( int a1 = 1 ; a1 < 3 ; a1 ++ ) { int key = pos [ a1 ];双 keyval = a [ key ];