algorithm - 将矢量轮廓区域(边界)转换为栅格 map (像素网格)

Question

我有一张 map ，它像世界地图上的国家一样被边界(等高线)分割成许多区域。每个区域都有特定的地表覆盖等级 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

我想制作一个栅格 map ，其中每个像素的值 S 对应于像素中心所在的区域。

请注意，边框代表 S 中的步 变化。 S 的各种值代表离散类别(例如草或水)，并且不是可以平均的值(即没有湿草!)。

另请注意，并非所有边界都是如上例所示的闭环。这有点像国家边界:例如美加边界不是一个闭环，而是一条在两端与另外两条边界相连的线:加拿大洋和美国洋“边界”。 (闭环边界 do exist 尽管如此!)

谁能告诉我一个可以做到这一点的算法？我不想重新发明轮子!

Answer 1

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

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

3d 几何体看起来像这个草图，有 3 个红色/黄色部分和 1 个蓝色/绿色部分:

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

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