将矢量轮廓区域（边界）转换为栅格地图（像素网格）
我有一张地图，它被边界（轮廓）分成多个区域，就像世界地图上的国家一样。每个区域都有特定的表面覆盖类别S（例如，水为0，草为0.03...）。边框由以下内容定义：
- 其两侧的 S 值（一侧为 0.03，另一侧为 0.0，在下面的示例中）
- 边框由多少个点组成（n=7（在下面的示例中），以及
- n 个坐标对（x、y）。
这是一个例子。
0.0300 0.0000 7
2660607.5 6332685.5 2660565.0 6332690.5 2660541.5 6332794.5
2660621.7 6332860.5 2660673.8 6332770.5 2660669.0 6332709.5
2660607.5 6332685.5
我想制作一个栅格地图，其中每个像素的值 S 对应于像素中心所在的区域。
请注意，边框代表 S 中的步骤变化。 S 的各种值代表离散类别（例如草或水），并且不是可以平均的值（即没有湿草！）。
另请注意，并非所有边框都是像上面的示例那样的闭环。这有点像国家边界：例如，美国-加拿大边界不是一个闭环，而是一条在两端与其他两个边界相连的线：加拿大-海洋和美国-海洋“边界”。 （尽管如此，闭环边界确实存在！）
任何人都可以向我指出一种可以做到这一点的算法吗？这？我不想重新发明轮子！
I have a map that is cut up into a number of regions by borders (contours) like countries on a world map. Each region has a certain surface-cover class S (e.g. 0 for water, 0.03 for grass...). The borders are defined by:
- what value of S is on either side of it (0.03 on one side, 0.0 on the other, in the example below)
- how many points the border is made of (n=7 in example below), and
- n coordinate pairs (x, y).
This is one example.
0.0300 0.0000 7
2660607.5 6332685.5 2660565.0 6332690.5 2660541.5 6332794.5
2660621.7 6332860.5 2660673.8 6332770.5 2660669.0 6332709.5
2660607.5 6332685.5
I want to make a raster map in which each pixel has the value of S corresponding to the region in which the center of the pixel falls.
Note that the borders represent step changes in S. The various values of S represent discrete classes (e.g. grass or water), and are not values that can be averaged (i.e. no wet grass!).
Also note that not all borders are closed loops like the example above. This is a bit like country borders: e.g. the US-Canada border isn't a closed loop, but rather a line joining up at each end with two other borders: the Canada-ocean and the US-ocean "borders". (Closed-loop borders do exist nevertheless!)
Can anyone point me to an algorithm that can do this? I don't want to reinvent the wheel!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
以矢量形式处理此类几何图形的一般情况可能非常困难，特别是因为您描述的结构不需要几何图形保持一致。但是，由于您只想对其进行栅格化，因此将问题视为线段的 Voronoi 图可能会更加稳健。
通过将每条线段绘制为一对形成帐篷形状的四边形，可以在 OpenGL 中以图形方式完成 Voronoi 图的近似。 z 缓冲区用于使最接近的四边形优先，从而根据最接近的线对像素进行着色。这里的区别在于，您需要根据多边形所在线的哪一侧而不是它们代表的线来为多边形着色。讨论类似算法的一篇好论文是 Hoff 等人的 快速计算使用图形硬件的广义 Voronoi 图
3D 几何图形将类似于此草图，具有 3 个红色/黄色部分和 1 个蓝色/绿色部分：
此过程不需要您将任何内容转换为闭环，也不需要任何花哨的几何库。一切都由 z 缓冲区处理，并且应该足够快，可以在任何现代显卡上实时运行。一种改进是使用齐次坐标使基底投影到无穷大。
我在Python脚本中实现了这个算法 http://www.pasteall.org/9062/python。一个有趣的警告是，使用圆锥体来覆盖线的末端不会在不扭曲圆锥体形状的情况下起作用，因为代表线段端点的圆锥体是 Z 轴冲突的。对于您提供的示例几何体，输出如下所示：
The general case for processing this sort of geometry in vector form can be quite difficult, especially since nothing about the structure you describe requires the geometry to be consistent. However, since you just want to rasterize it, then treating the problem as a Voronoi diagram of line segments can be more robust.
Approximating the Voronoi diagram can be done graphically in OpenGL by drawing each line segment as a pair of quads making a tent shape. The z-buffer is used to make the closest quad take precedence, and thus color the pixel based on whichever line is closest. The difference here is that you will want to color the polygons based on which side of the line they are on, instead of which line they represent. A good paper discussing a similar algorithm is Hoff et al's Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware
The 3d geometry will look something like this sketch with 3 red/yellow segments and 1 blue/green segment:
This procedure doesn't require you to convert anything into a closed loop, and doesn't require any fancy geometry libraries. Everything is handled by the z-buffer, and should be fast enough to run in real time on any modern graphics card. A refinement would be to use homogeneous coordinates to make the bases project to infinity.
I implemented this algorithm in a Python script at http://www.pasteall.org/9062/python. One interesting caveat is that using cones to cap the ends of the lines didn't work without distorting the shape of the cone, because the cones representing the end points of the segments were z-fighting. For the sample geometry you provided, the output looks like this:
我建议您使用几何算法库，例如 CGAL。特别是“二维多边形”中的第二个示例参考手册的页面应该可以提供您所需要的内容。您可以将每个“边界”定义为多边形，并检查某些点是否在多边形内部。所以基本上这就像
我不太确定如何处理 Outside_color 因为外部区域会重叠，不是吗？无论如何，看看你的例子，每个外部区域都可能是水，所以你可以做一个最终的
（或者作为替代方案，在迭代多边形列表之前将像素[X][Y]设置为water_value）
I'd recommend you to use a geometry algorithm library like CGAL. Especially the second example in the "2D Polygons" page of the reference manual should provide you what you need. You can define each "border" as a polygon and check if certain points are inside the polygons. So basically it would be something like
I'm not so sure about what to do with the outside_color because the outside regions will overlap, won't they? Anyway, looking at your example, every outside region could be water, so you just could do a final
(or as an alternative, set pixel[X][Y] to water_value before iterating through the polygon list)
我解决这个问题的方法如下：
即使存在非闭合线（例如在地图边缘），此功能也有效。
这不是一个“完美”的分析算法。有两个参数：L 和 d。只要 d << ，该算法就可以完美地工作。 L。否则，您可能会在段连接处（尤其是那些具有锐角的连接处）附近出现不准确的情况（通常为单像素）。
The way I've solved this is as follows:
This works even when there are non-closed lines, e.g. at the edge of the map.
This is not a "perfect" analytical algorithm. There are two parameters: L and d. The algorithm works beautifully as long as d << L. Otherwise you can get inaccuracies (usually single-pixel) near segment junctions, especially those with acute angles.