给定一个由 lat/lon/elevation 对组成的高程图，找到高于给定高程水平的所有点的最快方法是什么（或者更好的是，只是 2D 凹壳）？
我正在开发一个 GIS 应用程序，我需要在地图顶部呈现叠加层，以直观地指示海拔较高的区域；它正在确定这个让我难过的多边形/区域（现在）。我有一个简单的 lat/lon/elevation 对数组（更具体地说，是GTOPO30 DEM 文件），但我可以自由地将其转换为您建议的任何数据结构。
我们一直指向不规则三角网络 (TIN)，但我不确定在生成 TIN 后如何有效地查询该数据。如果我们的问题可以像生成等高线图一样得到解决，我不会感到惊讶，但我对此没有任何经验。任何建议都会很棒。
听起来您正在尝试创建高地边界的多边形表示。
如果您正在使用栅格数据（在矩形网格上采样），请尝试此操作。
把你的网格想象成一个直角三角形的集合。
假设您有一个 3x3 的点网格
你的三角形是：
你的算法有这些步骤。
建立一个高于高程阈值的三角形列表。
将这些三角形联合起来形成一个多边形区域。
确定多边形的边界。
如有必要，平滑多边形边界以使您的图层在显示时看起来不错。
如果你想生成好看的轮廓线，步骤 4 很难正确。
第一步是解决这个问题的关键。
对于每个三角形，如果所有三个顶点都高于阈值，则将整个三角形包括在列表中。如果都在下面，请忘记三角形。如果某些顶点在上方而其他顶点在下方，则通过添加精确位于高程线上的新顶点（通过插值高程）将三角形分成三个。在你的高地列表中包括一两个新三角形。
对于其余步骤，您将需要一个不错的 2d 几何处理库。
如果您的点不在规则网格上，请首先使用 Delaunay 算法（您可以查找）将您的点组织成三角形。然后按照我上面提到的相同算法。警告。如果你没有很多点，这看起来有点粗略。
从您的问题中不清楚这组点是否是静态的，并且您需要多次查找高于给定海拔的点，或者您是否只需要进行一次查询。
最简单的解决方案是将点存储在一个数组中，按高程排序。查找某个高程范围内的所有点只是二分查找，只需要排序一次。
如果您只需要执行一次查询，只需按照您得到的顺序对数组进行线性搜索。无论如何，从数组构建一个更漂亮的数据结构将是 O(n)，所以你不会通过使事情复杂化来获得更好的结果。
如果您有其他要求，例如您需要有效地列出用户正在查看的某个矩形内的所有点，或者可以在运行时添加或删除点，那么不同的数据结构可能会更好。大概是某种树或网格。
如果您只关心渲染，您可以使用图形硬件非常有效地执行此操作，并且根本不需要使用花哨的数据结构，您只需将三角形发送到 GPU 并让它杀死高于或低于某个特定值的片段海拔。
我会使用嵌套的C 方格排列，每个方格都有预先计算的最大地面高度。这将允许我进行高水平扫描，丢弃最大高度不高于搜索高度的任何方格，并进一步钻入那些部分地面高于搜索高度的方格。
如果您正在使用各种设置级别的搜索高度，您可以为您决定使用的最小正方形（或所有正方形，就此而言）预先计算各种预定义级别的凸包。
假设您将 lat/lon/elevation 数据存储在一个数组（或三个单独的数组）中，您应该能够使用数组查询技术来选择海拔高于某个阈值的所有点。例如，在 python 中numpy你可以这样做：
indices = where(array > value)
并且该indices变量将包含array大于阈值的所有元素的索引value。类似的命令可以在其他各种语言中使用（例如 IDL 有WHERE()命令，类似的事情可以在 Matlab 中完成）。
获得此索引列表后，您可以创建一个新的二进制数组，其中满足阈值的每个位置都设置为 1：
binary_array[indices] = 1
（假设您创建了一个与原始 lat/long/elevation 大小相同的空白数组并将其命名为binary_array.
如果您正在使用栅格数据（我会推荐这种类型的工作），您可能会发现您可以简单地将这个数组覆盖在地图上并获得一组不错的区域。但是，如果您需要将高于高程阈值的区域转换为矢量多边形，那么您可以使用许多内置 GIS 方法之一来转换栅格->矢量。
我不确定您的 lat/lon/alt 点是否在常规网格上，但如果不是，也许它们可以被插值以表示甚至 100 英尺的高度增量，以及统一的 lat/lon 划分（请记住没有给出统一的距离划分）。但如果这样可行，为什么不预先计算一个三维数组，其中的索引分别代表海拔、纬度和经度。那么当飞行器需要某个高度或以上的点的数据时，对于特定的一块地形，代码只需要读出这个数组中的一小部分数据，通过索引使连续的“体素”在索引方案。
当然，经度的增量不必是统一的：如果需要统一的距离，同样的方案也可以工作，但经度的索引将指向一组非均匀间隔的经度。
我认为不会有更快的方法来搜索这些数据。