5

我有一张地图，它像世界地图上的国家一样，被边界（轮廓）分割成多个区域。每个区域都有一定的地表覆盖等级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的各种值代表离散的类别（例如草或水），并且不是可以平均的值（即没有湿草！）。

另请注意，并非所有边界都是像上面的示例一样的闭环。这有点像国家边界：例如，美国-加拿大边界不是一个封闭的循环，而是一条在每一端与另外两个边界相连的线：加拿大-海洋和美国-海洋“边界”。（尽管如此，闭环边界确实存在！）

谁能指出我可以做到这一点的算法？我不想重新发明轮子！

4

5 回答 5

6

以矢量形式处理这种几何图形的一般情况可能非常困难，特别是因为您描述的结构不需要几何图形是一致的。但是，由于您只想对其进行栅格化，因此将问题视为线段的 Voronoi 图可能会更加稳健。

可以在 OpenGL 中通过将每个线段绘制为一对构成帐篷形状的四边形来以图形方式逼近 Voronoi 图。z 缓冲区用于使最近的四边形优先，从而根据最接近的线对像素进行着色。此处的不同之处在于，您将希望根据多边形所在的直线的哪一侧而不是它们代表的直线为多边形着色。一篇讨论类似算法的好论文是 Hoff 等人的Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware

3d 几何看起来像这个草图，有 3 个红色/黄色段和 1 个蓝色/绿色段：

3d 几何草图

此过程不需要您将任何东西转换为闭环，也不需要任何花哨的几何库。一切都由 z-buffer 处理，并且应该足够快以在任何现代显卡上实时运行。一种改进是使用齐次坐标使基础投影到无穷大。

我在http://www.pasteall.org/9062/python的 Python 脚本中实现了这个算法。一个有趣的警告是，在不扭曲锥体形状的情况下，使用锥体来覆盖线的末端是行不通的，因为表示线段端点的锥体是 z-fighting。对于您提供的示例几何图形，输出如下所示：

voronoi 渲染输出

于 2009-11-09T04:13:24.363 回答
1

我建议您使用像CGAL这样的几何算法库。特别是参考手册的“2D Polygons”页面中的第二个示例应该为您提供所需的内容。您可以将每个“边界”定义为多边形并检查某些点是否在多边形内。所以基本上它会像

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

我不太确定如何处理outside_color，因为外部区域会重叠，不是吗？无论如何，看看你的例子，每个外部区域都可能是水，所以你可以做一个决赛

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

（或者作为替代方案，在遍历多边形列表之前将 pixel[X][Y] 设置为 water_value）

于 2009-11-06T11:49:55.603 回答
0

我解决这个问题的方法如下：

  1. 沿着每一段行进；定期停止L。
  2. 在每个停靠点，立即在路段的左侧和右侧放置一个跟踪点（距路段一定的小距离d）。示踪点分别归属于左右 S 值。
  3. 进行最近邻插值。栅格网格上的每个点都归属于最近的示踪点的 S。

即使有非闭合线，例如在地图边缘，这也有效。

这不是一个“完美”的分析算法。有两个参数：L和d。只要d << L ，该算法就可以很好地工作。否则，您可能会在段交叉点附近出现不准确（通常是单像素），尤其是那些具有锐角的点。

于 2011-05-21T13:15:54.713 回答
0
  • 首先，将所有边界转换为闭环（可能包括地图的边缘），并识别内部颜色。这必须是可能的，否则您的数据会不一致
  • 使用 bresenham 算法在地图上以一种未使用的颜色绘制所有边界线
    • 在执行此操作时存储所有“边框像素”的列表
  • 然后对于每个边界
    • 对其进行三角测量（delaunay）
    • 遍历三角形，直到找到一个中心在边界内的三角形（多边形点测试）
    • 在边界的内部颜色中填充您的地图
  • 填写完所有内部区域后，遍历边框像素列表，查看每个像素应该是哪种颜色
于 2009-11-06T12:09:36.500 回答
0
  • 选择两种未使用的颜色作为标记“空”和“边框”
  • 用“空”颜色填充所有区域
  • 通过“边框”颜色绘制所有区域边框
  • 遍历点以找到第一个具有“空”颜色的点
  • 确定它属于哪个区域（谷歌“点在多边形内”，可能您需要按照 Martin DeMello 的建议关闭边界）
  • 使用区域的颜色从该点执行洪水填充算法
  • 转到下一个“空”点（无需重新开始搜索 - 继续）
  • 依此类推，直到没有“空”点仍然存在
于 2009-11-06T14:10:43.547 回答