标签：solver list 高度介绍道路 len 计算

介绍

做这样的事情的原因是因为玩“ 城市：天际线 ”，游戏中的互通建设既繁琐又重要。于是，就产生了制作一个工具，将现有的二维地图道路数据自动生成三维立交道路的想法。

以延安东路立交桥为例，第一个是平面展示效果，第二个是立体展示效果：

1. 平面效果，截取自苹果地图

2. 立体效果，截取自百度地图

如果能把第二张图中的道路数据导入到游戏中，那一定非常实用。因此，接下来的内容就是介绍一下我对如何从图1中的数据计算出图2中的数据的想法。

计算原理

道路在平面上的坐标是已知的，但是如何计算道路在垂直方向的坐标呢？换句话说，道路的哪些属性可以帮助我们？

如果您在 OSM 上编辑了更复杂的道路数据，您可能会注意到反映道路之间覆盖水平的属性。

例1：东西向A路为高架路，南北向B路为普通地面道路，A路等级高于B路。
例2：东西向C路为地下隧道，南北向D路为普通地面道路，C路等级低于D路。

在 OSM 中编辑地图数据时，此封顶级别命名为“” 层》，进入后台数据库后，体现在“z_order”字段中。这个属性最直接的意义就是在渲染地图的时候，渲染引擎可以知道叠加在同一位置上的道路的渲染顺序。

既然可以知道道路的垂直顺序，那么结合一些额外的信息，就可以计算出道路上一个节点的高度值，或者至少是一个节点的取值范围。

此处的附加信息是指以下内容：

两条相邻道路之间存在最小高度差，假设为 4 米。
道路上两个相邻节点之间的坡度值小于固定值，假定为 6%。
该物业为地面类型，高度固定为0米。
该物业为高架式，高度至少为4米。

还有一个假设：

立交桥所在范围内地面高度均为0米，不考虑地形对道路的影响。

根据上述条件，将每条道路上各点的高度值作为未知数，可以列出不等式方程组。

那么问题又来了，怎么解决呢？似乎无法弄清楚。然后我们必须引入另一个假设：

形成交叉口的每条道路都尽可能低，以降低成本。

上面的这个假设实际上是一个目标函数。因此，问题变成了，有约束，找到目标函数的最优解，一个普通的线性规划问题。

数据准备

数据采集

OSM的数据可以很方便的下载，这里不再赘述。我选择了上海、约翰内斯堡和西雅图三个城市各一个立交桥作为测试数据。（其实我只在上海延安东路立交桥和莘庄立交试过）

OSM 中上海市延安东路立交的数据

数据处理

单次计算仅针对一个立交桥，不涉及立交桥道路以外的道路，如立交桥下的普通城市道路。所以需要对数据进行过滤和提取。

在按道路属性进行过滤时，需要注意快速路和城市快速路的道路类型可能不同。

数据命名

道路高度值的计算其实就是计算道路上每个点的高度值。为了方便计算，需要将道路上的点分为4类：

交叉点：缩写

.两条不同的道路相交时形成交叉口，但实际上，由于两条道路的高度必然不同，因此在实践中并不交叉。这样，同一个路口最终对应了两个需要计算的未知数，分别对应了两条不同的道路。
触点：缩写

.坡道与主干道汇合时形成的点，一个接触点实际上对应2条道路。
终点：缩写

.在道路的两端点。
法线点：缩写

.上述三种类型以外的点。

最后需要计算前三类点，线性规划完成后可以通过插值计算第四类点。

算法实现

空间关系

所有提到的涉及空间关系的计算都是由 PostGIS 完成的。这不是文章的重点，我就不赘述了，详细请参考文档” postgis.net/docs/manual… ”。仅列出一些使用的功能。

计算道路交叉口：ST_Intersection()
删除重复点：ST_Removerepeatedpoints() （由于精度问题，需要用 PostGIS 函数实现，而不是 SQL）
合并多行：ST_LineMerge()
判断特征是否有共同点：ST_Touches()

限制

以下公式可能写得不正确，如有错误请指出。

根据道路属性，如果是地面道路，高度比例设置为0，如果是高架道路，高度大于等于3。隧道类型的道路暂不考虑。

$[\begin{cases} Height(P_i) = 0, & Type(road_i) = Bridge \ Height(P_i) >= 3, & Type(road_i) Bridge \end{cases}]$

两点之间的斜率应小于或等于指定值。请注意，

LENGTH

它不是指两点之间的直线距离，而是指曲线沿道路的距离。

$[\mid Height(P_i) - Height(P_{i+1})\mid * LENGTH <= MAX_SLOPE]$

上面提到的两条不同高度的道路，朝上时会有一个交叉路口。这个交点其实是两个点，平面坐标相同，但高度不同。根据道路的“z_order”属性，可以知道这两个点中哪个在上面，哪个在下面。

$[Height(CP_{high}) - Height(CP_{low}) >= MIN_ELEVATION]$

目标函数

目标是“让每条道路尽可能低，以降低成本”。所以需要最小化道路线数据中所有点的高度值之和：

$[S=\sum_{i=1}m\Height(CP_m)+\sum_{i=1}n\Height(TP_n)+\sum_{i=1}p\Height(EP_p)+\sum_{i=1}q\Height(NP_q)]$

线性规划求解器

使用谷歌解决线性规划工具库，参考文档链接：线性优化，以下代码中的英文注释在文档中，我就不翻译了，以免造成误解。

创建一个解决线性规划问题的对象：

 从 ortools.linear_solver 导入 linear_solver_pb2，pywraplp  
  
 # 使用 GLOP 后端创建线性求解器。  
 求解器 = pywraplp.Solver('road_3D', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)  
 复制代码

定义一个变量，可以在初始化时指定变量的取值范围：

 对于范围内的_n（0，len（cross_points））：  
 cp_list.append(solver.NumVar(0,solver.infinity(),'cp_{id:02d}'.format(id=_n)))  
  
 对于范围内的_n（0，len（touch_points））：  
 tp_list.append(solver.NumVar(0,solver.infinity(),'tp_{id:02d}'.format(id=_n)))  
  
 对于范围内的_n（0，len（end_points））：  
 ep_list.append(solver.NumVar(0,solver.infinity(),'ep_{id:02d}'.format(id=_n)))  
 复制代码

实现上述约束的表达式，以“两点之间的斜率小于等于指定值”为例：

 约束=求解器.约束（-距离* MAX_SLOPE，距离* MAX_SLOPE）  
 约束.SetCoefficient(cp_list[m], 1)  
 约束.SetCoefficient(cp_list[n], - 1)  
 复制代码

声明目标函数的一个对象并将其设置为最小化：

 目标=求解器。目标（）  
 目标.SetMinimization()  
  
 对于范围内的_n（0，len（cross_points））：  
 Objective.SetCoefficient(cp_list[_n], 1)  
  
 对于范围内的_n（0，len（touch_points））：  
 Objective.SetCoefficient(tp_list[_n], 1)  
  
 对于范围内的_n（0，len（end_points））：  
 Objective.SetCoefficient(ep_list[_n], 1)  
 复制代码

解决：

 求解器.Solve()  
  
 # 输出求解结果  
 打印(cp_list[_n].solution_value())  
 复制代码

“异常下降”

这种模型实际上存在问题。假设在一条道路上连续选取三个点，分别是A、B、C，以及A点和C点下方。因为有道路，所以最终计算高度为4米。，B点以下没有路，B点的高度是多少？

按照常识，B点的高度也应该是4米。但是根据上面的模型，B点会在坡度限制内尽可能低，那么实际生成的道路会出现异常下降，根据我简单的日常经验，这不应该是这样。

目前的做法是在线性规划计算完成后再次检查数据，以弥补此类问题。

结果预览

得到上面的结果后，还需要一些后续的处理过程，比如积分、插值、指定格式输出等。目前数据保存到PostgreSQL数据库，并以kml格式输出，方便在Google Earth中查看。

存在的问题

有个别点
值计算错误问题。这个问题有几个原因，一个是上面提到的“异常下降”；二是并非所有立交都符合方案设定的最小高度差和最大坡度；不排除程序本身有bug，会造成一些
值为 0。
所有的计算都是以地面为平面，但在现实生活中并非完全如此。
因为我不知道《城市：天际线》中的数据规范，所以我无法将现有数据导入到游戏中。

项目地址： github.com/BranZhang/i…

这篇文章的链接： https://homecpp.art/1622/10143/1134

本文链接：https://www.qanswer.top/38698/47552212

标签：solver,list,高度,介绍,道路,len,计算
From： https://www.cnblogs.com/amboke/p/16718851.html

介绍

介绍