快速查找并渲染给定海拔以上的地形
给定由纬度/经度/高程对组成的高程图，找到高于给定高程水平的所有点的最快方法是什么（或者更好，只是二维凹壳）？
我正在开发一个 GIS 应用程序，我需要在地图顶部渲染叠加层，以直观地指示海拔较高的区域；它正在确定这个让我困惑的多边形/区域（目前）。我有一个简单的纬度/经度/高程对数组（更具体地说，GTOPO30 DEM 文件），但我可以随意将其转换为您建议的任何数据结构。
我们已经提到了不规则三角网络 (TIN)，但我不确定生成 TIN 后如何有效查询该数据。如果我们的问题可以像生成等高线图一样得到解决，我不会感到惊讶，但我对此没有任何经验。任何建议都会很棒。
Given an elevation map consisting of lat/lon/elevation pairs, what is the fastest way to find all points above a given elevation level (or better yet, just the the 2D concave hull)?
I'm working on a GIS app where I need to render an overlay on top of a map to visually indicate regions that are of higher elevation; it's determining this polygon/region that has me stumped (for now). I have a simple array of lat/lon/elevation pairs (more specifically, the GTOPO30 DEM files), but I'm free to transform that into any data structure that you would suggest.
We've been pointed toward Triangulated Irregular Networks (TINs), but I'm not sure how to efficiently query that data once we've generated the TIN. I wouldn't be surprised if our problem could be solved similarly to how one would generate a contour map, but I don't have any experience with it. Any suggestions would be awesome.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
听起来您正在尝试创建高地边界的多边形表示。
如果您正在使用栅格数据（在矩形网格上采样），请尝试此操作。
将网格视为直角三角形的组合。
假设你有一个 3x3 的点网格
你的三角形是：
你的算法有这些步骤。
构建高于标高阈值的三角形列表。
将这些三角形的并集形成一个多边形区域。
确定多边形的边界。
如有必要，请平滑多边形边界以使图层在显示时看起来正常。
如果您想生成美观的轮廓线，则步骤 4 很难正确执行。
第1步是解决这个问题的关键。
对于每个三角形，如果所有三个顶点都高于阈值，则将整个三角形包含在列表中。如果全部都在下面，请忘记三角形。如果某些顶点在上方而其他顶点在下方，则通过添加精确位于高程线上的新顶点（通过插值高程）将三角形分成三个。将这些新三角形中的一两个添加到您的高地列表中。
对于其余的步骤，您将需要一个像样的二维几何处理库。
如果您的点不在规则网格上，请首先使用 Delaunay 算法（您可以查找该算法）将您的点组织成三角形。然后遵循我上面提到的相同算法。警告。如果你没有很多点，这看起来会有点粗略。
It sounds like you're attempting to create a polygonal representation of the boundary of the high land.
If you're working with raster data (sampled on a rectangular grid), try this.
Think of your grid as an assembly of right triangles.
Let's say you have a 3x3 grid of points
Your triangles are:
Your algorithm has these steps.
Build a list of triangles that are above the elevation threshold.
Take the union of these triangles to make a polygonal area.
Determine the boundary of the polygon.
If necessary, smooth the polygon boundary to make your layer look ok when displayed.
If you're trying to generate good looking contour lines, step 4 is very hard to to right.
Step 1 is the key to this problem.
For each triangle, if all three vertices are above the threshold, include the whole triangle in your list. If all are below, forget about the triangle. If some vertices are above and others below, split your triangle into three by adding new vertices that lie precisely on the elevation line (by interpolating elevation). Include the one or two of those new triangles in your highland list.
For the rest of the steps you'll need a decent 2d geometry processing library.
If your points are not on a regular grid, start by using the Delaunay algorithm (which you can look up) to organize your pointss in into triangles. Then follow the same algorith I mentioned above. Warning. This is going to look kind of sketchy if you don't have many points.
假设您将纬度/经度/海拔数据存储在一个数组（或三个单独的数组）中，您应该能够使用数组查询技术来选择海拔高于特定阈值的所有点。例如，在使用
numpy的 python 中，您可以执行以下操作：并且
indices变量将包含大于阈值的array的所有元素的索引 <代码>值。类似的命令在其他各种语言中也可用（例如 IDL 有WHERE()命令，类似的事情可以在 Matlab 中完成）。获得此索引列表后，您可以创建一个新的二进制数组，其中满足阈值的每个位置都设置为 1：（
假设您创建了一个与原始纬度/经度/高程大小相同的空白数组并将其命名为
binary_array。如果您正在使用栅格数据（我建议将其用于此类工作），您可能会发现只需将此数组覆盖在地图上即可获得一个不错的集合。但是，如果您需要将高于高程阈值的区域转换为矢量多边形，那么您可以使用许多内置 GIS 方法之一来转换栅格->矢量。
Assuming you have the lat/lon/elevation data stored in an array (or three separate arrays) you should be able to use array querying techniques to select all of the points where the elevation is above a certain threshold. For example, in python with
numpyyou can do:And the
indicesvariable will contain the indices of all elements ofarraygreater than the thresholdvalue. Similar commands are available in various other languages (for example IDL has theWHERE()command, and similar things can be done in Matlab).Once you've got this list of indices you could create a new binary array where each place where the threshold was satisfied is set to 1:
(Assuming you've created a blank array of the same size as your original lat/long/elevation and called it
binary_array.If you're working with raster data (which I would recommend for this type of work), you may find that you can simply overlay this array on a map and get a nice set of regions appearing. However, if you need to convert the areas above the elevation threshold to vector polygons then you could use one of many inbuilt GIS methods to convert raster->vector.
我将使用嵌套的 C-squares 排列，每个方块都有一个预先计算的最大值地面高度。这将使我能够在高水平上进行扫描，丢弃最大高度不高于搜索高度的任何方块，并进一步钻入地面部分高于搜索高度的那些方块。
如果您正在处理各种设置级别的搜索高度，则可以为您决定使用的最小正方形（或所有正方形）的各种预定义级别预先计算凸包。
I would use a nested C-squares arrangement, with each square having a pre-calculated maximum ground height. This would allow me to scan at a high level, discarding any squares where the max height is not above the search height, and drilling further into those squares where parts of the ground were above the search height.
If you're working to various set levels of search height, you could precalculate the convex hull for the various predefined levels for the smallest squares that you decide to use (or all the squares, for that matter.)
我不确定你的纬度/经度/海拔点是否在规则网格上，但如果不是，也许它们可以插值来表示甚至 100 英尺的高度增量，并且统一
纬度/经度划分（请记住，这并没有给出统一的距离划分）。但如果这可行，为什么不预先计算一个三维数组，其中索引分别代表海拔、纬度和经度。然后，当飞机需要某个高度或以上的点的数据时，对于特定的一块地形，代码只需要读出这个数组中的一小部分数据，并对其进行索引，以使连续的“体素”在数组中连续。索引方案。
当然，经度的增量不必是均匀的：如果需要均匀的距离，则可以使用相同的方案，但经度的索引将指向一组不均匀间隔的经度。
我认为没有更快的方法来搜索这些数据。
I'm not sure whether your lat/lon/alt points are on a regular grid or not, but if not, perhaps they could be interpolated to represent even 100' ft altitude increments, and uniform
lat/lon divisions (bearing in mind that that does not give uniform distance divisions). But if that would work, why not precompute a three dimensional array, where the indices represent altitude, latitude, and longitude respectively. Then when the aircraft needs data about points at or above an altitude, for a specific piece of terrain, the code only needs to read out a small part of the data in this array, which is indexed to make contiguous "voxels" contiguous in the indexing scheme.
Of course, the increments in longitude would not have to be uniform: if uniform distances are required, the same scheme would work, but the indexes for longitude would point to a nonuniformly spaced set of longitudes.
I don't think there would be any faster way of searching this data.
从您的问题中不清楚这组点是否是静态的，并且您需要多次查找哪些点高于给定的海拔，或者您是否只需要执行一次查询。
最简单的解决方案是将点存储在数组中，按高程排序。查找某个高程范围内的所有点只是二分查找，只需要排序一次。
如果您只需要执行一次查询，只需按照获得的顺序对数组进行线性搜索即可。无论如何，从数组构建一个更奇特的数据结构将是 O(n)，所以你不会通过使事情复杂化来获得更好的结果。
如果您有其他一些要求，例如您需要有效地列出用户正在查看的某个矩形内的所有点，或者可以在运行时添加或删除点，那么不同的数据结构可能会更好。大概是某种树或网格。
如果您关心的只是渲染，那么您可以使用图形硬件非常有效地执行此操作，并且根本不需要使用花哨的数据结构，您只需将三角形发送到 GPU 并让它杀死高于或低于某个特定值的片段即可海拔。
It's not clear from your question if the set of points is static and you need to find what points are above a given elevation many times, or if you only need to do the query once.
The easiest solution is to just store the points in an array, sorted by elevation. Finding all points in a certain elevation range is just binary search, and you only need to sort once.
If you only need to do the query once, just do a linear search through the array in the order you got it. Building a fancier data structure from the array is going to be O(n) anyway, so you won't get better results by complicating things.
If you have some other requirements, like say you need to efficiently list all points inside some rectangle the user is viewing, or that points can be added or deleted at runtime, then a different data structure might be better. Presumably some sort of tree or grid.
If all you care about is rendering, you can perform this very efficiently using graphics hardware, and there is no need to use a fancy data structure at all, you can just send triangles to the GPU and have it kill fragments above or below a certain elevation.