一种管道敷设技术领域的发动机管道敷设系统，本发明中，接口模块负责实现发动机管道敷设系统与三维设计软件之间的数据交换，三维敷设空间的二维展开模块负责用二维方式表示三维的敷设空间，管道敷设密集区域识别排序模块负责进行管道敷设区域的疏密识别和管道的敷设顺序的设定，不可敷设区域图生成模块将管道敷设的条件和约束转化为统一可见的不可敷设区域图表示在二维展开图上，将每个条件和约束转化为图上的一个不可敷设区域，凸包绕障计算模块是指利用凸包方法获得管道在不可敷设区域图中绕障的最短路径并生成管道中心线轨迹。本发明能够得到绕过障碍物的最短的管道路径，简化了以往发动机管道敷设的计算复杂度。
1.一种发动机管道敷设系统，其特征在于，包括：接口模块、三维敷设空间的二维展开模块、管道敷设密集区域识别排序模块、不可敷设区域图生成模块、凸包绕障计算模块，其中：
接口模块负责实现发动机管道敷设系统与三维设计软件之间的数据交换，将三维设计软件中的设计参数生成发动机管道敷设系统能够识别的TXT文本格式并进行储存，将发动机管道敷设系统得到的管道敷设结果生成三维设计软件能够识别的TXT文本格式并由三维设计软件生成三维管道敷设模型；
三维敷设空间的二维展开模块是指将发动机及其附件的设计模型经过接口模块转化成TXT文本并从中提取几何信息，沿发动机轴流方向周向展开，将其原有正交的笛卡儿坐标转换成正交的柱坐标，用二维方式表示三维的敷设空间；
管道敷设密集区域识别排序模块是指根据发动机及其附件的设计模型的要求以及管道属性的要求进行管道敷设区域的疏密识别和管道的敷设顺序的设定，设定的顺序依次序包括：先由内而外分层顺序、再由密到疏分区域顺序、然后由粗到细分管径顺序、最后由短到长顺序；
不可敷设区域图生成模块是根据三维敷设空间的二维展开模块和管道敷设密集区域识别排序模块得到的结果，将管道敷设的条件和约束转化为统一可见的不可敷设区域图表示在二维展开图上，将每个条件和约束转化为图上的一个不可敷设区域，每条管道在敷设前都会生成各自的不可敷设区域图，不可敷设区域图包括该管道敷设的各种设计信息和约束信息；
凸包绕障计算模块是指利用凸包方法获得管道在不可敷设区域图中绕障的最短路径并生成管道中心线轨迹，具体是指当得到了每根管道的不可敷设空间并将其在圆柱坐标(θ，r，h)的(θ，h)平面中进行了投影以后，布管工作是在二维可敷设区域图中，起点到终点连成的直线段穿过一个或多个不可敷设区域，在可敷设区域中寻找最短路径绕过这些不可敷设区域；
所述的凸包绕障计算模块，其寻找最短路径绕过一个不可敷设区域时，具体如下：连接管道起点到终点，将两点间最靠近起点和终点两个不可敷设区域点记为穿入点和穿出点，将穿入点和穿出点的中点记为内点，获得所有与内点相邻的不可敷设点，记为点集合K，求该点集合K的凸包，得到凸包集合B；针对凸包集合B与所有起点终点一起再次求凸包得到点序列P，P为有序点集合，其中从起点到终点的点序列即为管道绕过该不可敷设区域的最短路线；
所述的凸包绕障计算模块，其寻找最短路径绕过多个不可敷设区域，具体如下：连接管道起点到终点，将两点间最靠近起点和终点的两个不可敷设区域点以及可敷设区域与不可敷设区域的交界点，记为穿入点集合和穿出点集合，穿入每个不可敷设区域的点和穿出每个不可敷设区域的点记为一对点，共n对点，其中n为穿过的独立的不可敷设区域的个数；
所述的穿入点集合和穿出点集合分别包括从可敷设区域进入不可敷设区域的点以及从不可敷设区域进入可敷设区域的点；然后根据每对点计算中点，记为内点集合，求取所有与内点集合相邻的不可敷设点，记为点集合[K1，K2，K3，...，Kn]，分别对点集合[K1，K2，K3，...，Kn]求凸包，得到凸包集合序列[B1，B2，B3，...，Bn]，针对凸包集合和起点、终点再次计算凸包，得到有序点序列Q，取Q中从起点到终点的点序列，从中取出可敷设区域与不可敷设区域的交界点与起点终点组成新的点序列Q’，其中除了起点和终点，依然还有n对点，取Q’中相邻的n-1对点，作为新的起点和终点反复上面操作，每个循环过程直到新起点和终点的连线不再穿过不可敷设区域中止，得到的折线是管道起点到终点绕过所有不可敷设区域的最短路线；
所述的求凸包的具体步骤为：根据求取点的h或者θ坐标对所有点形成有序序列，并从最小h或者θ坐标向最大h或者θ坐标扫描，计算倒数三个点，如果构成右拐，则记为凸包点；如果构成左拐，则剔除前一点，依次生成根据h升序排列的点集，称为上凸包，反相扫描计算h或者θ坐标的降序排列的点集，称为下凸包，与上凸包一起构成整个凸包。
2.根据权利要求1所述的发动机管道敷设系统，其特征是，所述的三维敷设空间的二维展开模块，是指将三维笛卡儿空间模型用圆柱坐标进行两位展开，将三维甚至更高维的问题映射到二维平面中，以降低问题建模的复杂程度，对于轴流式发动机，发动机和安装舱都为类柱体，而管道的敷设走向都在类柱面上，管道的中心线是在类柱面上形成的三维空间曲线，将发动机及其附件的设计模型沿其轴流方向周向展开，将其原有正交的笛卡儿坐标(x，y，z)转换成同样正交的柱坐标(θ，r，h)，其中以x方向作为θ的起点和终点。
3.根据权利要求1所述的发动机管道敷设系统，其特征是，所述的管道敷设密集区域识别排序模块，其按照由内而外分层顺序敷设管道，具体如下：对内机匣表面到安装短舱之间的空间沿r方向分成n+1个层，每根管道根据每两次维修更换的平均间隔小时数由长到短排序，根据数量级分配到n+1个层里使每根管道都对应一个层；相反的每个层都对应相应的管道。
4.根据权利要求3所述的发动机管道敷设系统，其特征是，所述的管道敷设密集区域识别排序模块，其按照由密到疏分区域顺序敷设管道，具体如下：针对沿r方向分成的每一层，对其上的管道的起始点和终止点连测地曲线，在柱面展开后表现为直线段，求其相互的交点，具体采用输出敏感的平衡二分查找树方法，使用一条扫描线沿θ或h增大方向进行扫描，与当前扫描线相交的每条线段，都按照次序，存放在平衡二分查找树T的某片叶子处，只要输入始末点集S，经过计算就得到S中各线段之间的所有交点及穿过各交点的线段信息，对其沿(θ，h)进行网格划分，划分以该层最粗管道直径的三倍作为依据，即d θ和d h为管道直径的三倍，每个始末点及交点都落在某个(d θ，d h)的网格内，根据每个区域内包含的始末点和交点个数对网格进行编号，数字越大表示交点越多，也意味着该区域管路越密集，先敷设管路密集的区域，后敷设管道稀疏的区域。
5.根据权利要求3所述的发动机管道敷设系统，其特征是，所述的管道敷设密集区域识别排序模块，其按照由粗到细分管径顺序以及短管优先于长管顺序敷设管道，具体如下：
针对同一层同一密集区域的管道，先敷设粗管后敷设细管，细管沿着粗管敷设，并用管卡固定在粗管上；对于相同直径的管路，则短管优先于长管，短管是指始末点连线段较短的管道。
6.根据权利要求1所述的发动机管道敷设系统，其特征是，所述的不可敷设区域图生成模块，是指将每个约束管道敷设的因素和条件都转化成空间上的一个区域划分，将空间上管道不可以通过的区域用“1”，可以通过的区域用“0”表示，“1”的区域是各种对管道敷设的约束，包括振动、工艺、维修方面的条件，包括如下：①不符合振动要求的空间区域都被划分为“1”区域，②将干涉维修孔和工艺孔的空间区域都划分为“1”区域；③既可以是人为的分层、分区域造成的，也可以是真实的发动机附件障碍生成的，所有已经存在的物理障碍占据的空间和人为设置的不能通过的区域都被划分为“1”区域，每个不可敷设空间形成一个封闭的空间集合，其并集的补集就是该管道最终的三维可敷设空间。
发动机管道敷设系统
技术领域
[0001] 本发明涉及的一种管道敷设技术领域的系统，特别是一种发动机管道敷设系统。
背景技术
[0002] 发动机外部有数以百计的导管和电缆以及各种形式的卡箍，导管空间走向非常复杂，因此管道敷设工作非常复杂。而且由于集成了全部发动机零组件，导管空间曲线的确定很困难。管道敷设时，要考虑导管和导管、导管和附件之间的最小距离要求以及对发动机外廓尺寸限制。目前发动机管道敷设依然主要依靠设计人员人工知识和经验甚至是直觉，通过试制金属样机的试验方法对管道敷设的结果予以验证，工作量繁重。发动机管道系统设计不同于一般系统设计，是大量建立在知识和经验的基础上的复杂综合系统。发动机管道系统的设计难度巨大，逻辑复杂，主要表现在以下几个方面：管道数量巨大：一般发动机包括100～200余根管道，数百个固定管道的卡箍，数十组线缆；需要在受限狭小不规则空间进行三维走向敷设，长短不一、粗细不等、多层次交叉；附件多功能复杂：发动机的外部附件数量多达50余个，系统复杂，结构外形不规则，实现功能包括燃油供应、润滑、冷却、防冰、控制、传动、液压动作、信号传输等；多种工艺要求：管道系统需要满足制造工艺、安装、维护和更换要求、振动及强度要求、热力疲劳及热变形要求和电气要求等；多学科交叉：管道的设计计算涉及流体力学、热力学、材料力学、结构力学、振动力学、控制学、测试技术、计算机仿真技术和制造技术等多种学科。某些要求严格的管道还涉及流固耦合等复杂热力计算。
[0003] 经对现有技术文献的检索发现，日本德岛大学科技学院的Ito，Teruaki在《Journal of Intelligent Manufacturing》(智能制造期刊)(1999年3月第一期)上发表的(“Genetic algorithm approach to piping route path planning”)(用于管道敷设规划的遗传方法)，该文中首先提出在管道敷设规划中使用遗传方法，在二维平面内搜索管道的最优路径取得了进展。但该编码方式和遗传操作算子，导致在杂交和变异操作中产生了大量的非法解，引起十分繁琐的修补工作，影响了方法的收敛性能，该方法只考虑管道路径最短，只解决了管道的物理干涉问题，但并没有顾及管道系统的实际工艺要求和普通技术人员实际经验。
发明内容
[0004] 本发明的目的在于克服现有管道敷设技术中的不足，提出了一种发动机管道敷设系统，根据多种管道敷设约束条件在更短的时间内解决管道敷设绕障的最短路径问题，有效解决复杂管道敷设问题。
[0005] 本发明是通过以下技术方案实现的，本发明包括：接口模块、三维敷设空间的二维展开模块、管道敷设密集区域识别排序模块、不可敷设区域图生成模块、凸包绕障计算模块，其中：
[0006] 接口模块负责实现发动机管道敷设系统与三维设计软件之间的数据交换，将三维设计软件中的设计参数生成发动机管道敷设系统能够识别的TXT文本格式并进行储存，将发动机管道敷设系统得到的管道敷设结果生成三维设计软件能够识别的TXT文本格式并由三维设计软件生成三维管道敷设模型；
[0007] 三维敷设空间的二维展开模块是指将发动机及其附件的设计模型经过接口模块转化成TXT文本并从中提取几何信息，沿发动机轴流方向周向展开，将其原有正交的笛卡儿坐标转换成正交的柱坐标，用二维方式表示三维的敷设空间；
[0008] 管道敷设密集区域识别排序模块是指根据发动机及其附件的设计模型的要求以及管道属性的要求进行管道敷设区域的疏密识别和管道的敷设顺序的设定，设定的顺序包括：由内而外分层顺序、由密到疏分区域顺序、由粗到细分管径顺序、由短到长顺序；
[0009] 不可敷设区域图生成模块是根据三维敷设空间的二维展开模块和管道敷设密集区域识别排序模块得到的结果，将管道敷设的条件和约束转化为统一可见的不可敷设区域图表示在二维展开图上，将每个条件和约束转化为图上的一个不可敷设区域，每条管道在敷设前都会生成各自的不可敷设区域图，不可敷设区域图包括该管道敷设的各种设计信息和约束信息；
[0010] 凸包绕障计算模块是指利用凸包方法获得管道在不可敷设区域图中绕障的最短路径并生成管道中心线轨迹。
[0011] 所述的三维敷设空间的二维展开模块，是指将三维笛卡儿空间模型用圆柱坐标进行两位展开，将三维甚至更高维的问题映射到二维平面中予以解决，以降低问题建模的复杂程度。对于常见的轴流式发动机，发动机和安装舱都为类柱体，而管道的敷设走向都在类柱面上，管道的中心线是在类柱面上形成的三维空间曲线。因此，将发动机及其附件的设计模型沿其轴流方向周向展开，将其原有正交的笛卡儿坐标转换成同样正交的柱坐标，即(x，y，z)变成(θ，r，h)，其中以x方向作为θ的起点和终点。
[0012] 所述的管道敷设密集区域识别排序模块，其按照由内而外分层顺序敷设管道，具体如下：对内机匣表面到安装短舱之间的空间沿r方向分成n+1个层，每根管道根据每两次维修更换的平均间隔小时数由长到短排序，根据数量级分配到n+1个层里使每根管道都对应一个层；相反的每个层都对应相应的管道。敷设的时候根据由内层到外层的顺序进行，层别是管道敷设顺序的第一因素。
[0013] 所述的管道敷设密集区域识别排序模块，其按照由密到疏分区域顺序敷设管道，具体如下：针对每一层，对其上的管道的起始点和终止点连测地曲线，在柱面展开后表现为直线段，求其相互的交点，具体采用输出敏感算的平衡二分查找树方法，使用一条扫描线沿θ或h增大方向进行扫描，与当前扫描线相交的每条线段，都按照次序，存放在平衡二分查找树T的某片叶子处，只要输入始末点集S，经过计算就得到输出S中各线段之间的所有交点及穿过各交点的线段信息。对其沿(θ，h)进行网格划分，划分以该层最粗管道直径的三倍作为依据。每个始末点及交点都落在某个(dθ，dh)的网格内，根据每个区域内包含的始末点和交点个数对网格进行编号，数字越大表示交点越多，也意味着该区域管路越密集，先敷设管路密集的区域，后敷设管道稀疏的区域。
[0014] 所述的管道敷设密集区域识别排序模块，其按照由粗到细分管径顺序以及短管优先于长管顺序敷设管道，具体如下：针对同一层同一密集区域的管道，先敷设粗管后敷设细管，细管沿着粗管敷设，并用管卡固定在粗管上；对于相同直径的管路，则短管优先于长管，短管是指始末点连线段较短的管道。
[0015] 所述的不可敷设区域图生成模块，是指将每个约束管道敷设的因素和条件都转化成空间上的一个区域划分，将空间上管道不可以通过的区域用“1”，可以通过的区域用“0”表示，“1”的区域是各种对管道敷设的约束，包括振动、工艺、维修等方面的条件，包括如下：①不符合振动要求的空间区域都被划分为“1”区域，②将干涉维修孔和工艺孔的空间区域都划分为“1”区域；③既可以是人为的分层、分区域造成的，也可以是真实的发动机附件障碍生成的，所有已经存在的物理障碍占据的空间和人为设置的不能通过的区域都被划分为“1”区域，每个不可敷设空间形成一个封闭的空间集合，其并集的补集就是该管道最终的三维可敷设空间。
[0016] 所述的凸包绕障计算模块，是指当得到了每根管道的不可敷设空间并将其在(θ，h)平面中进行了投影以后，布管工作是在二维可敷设区域图中，起点到终点连成的直线段穿过一个或多个不可敷设区域，在可敷设区域中寻找最短路径绕过这些不可敷设区域。
[0017] 所述的凸包绕障计算模块，其寻找最短路径绕过一个不可敷设区域时，具体如下：连接管道起点到终点，将两点间最靠近起点和终点两个不可敷设区域点记为穿入点和穿出点，将穿入点和穿出点的中点记为内点，获得所有与内点相邻的不可敷设点，记为点集合K，求该点集合K的凸包，得到凸包集合B；针对凸包集合B与所有起点终点一起再次求凸包得到点序列P，P为有序点集合，其中从起点到终点的点序列即为管道绕过该不可敷设区域的最短路线。
[0018] 所述的凸包绕障计算模块，其寻找最短路径绕过多个不可敷设区域，具体如下：连接管道起点到终点，将两点间最靠近起点和终点的两个不可敷设区域点以及可敷设区域与不可敷设区域的交界点，记为穿入点集合和穿出点集合，共n对点，其中n为穿过的独立的不可敷设区域的个数；再根据每对点计算中点，记为内点集合，求取所有与内点集合相邻的不可敷设点，记为点集合[K1，K2，K3，...，Kn]，分别对点集合Kn求凸包，得到凸包集合序列[B1，B2，B3，...，Bn]，针对凸包集合和起点、终点再次计算凸包，得到有序点序列P，取P中从起点到终点的点序列，从中取出可敷设区域与不可敷设区域的交界点与起点终点组成新的点序列P’，其中除了起点和终点，依然还有n对点，取P’中相邻的n-1对点，作为新的起点和终点反复上面操作，每个循环过程直到新起点和终点的连线不再穿过不可敷设区域中止，得到的折线是管道起点到终点绕过所有不可敷设区域的最短路线。
[0019] 所述凸包绕障计算模块，其求取凸包具体如下：根据求取点的h或者θ坐标对所有点形成有序序列，并从最小h或者θ坐标向最大h或者θ坐标扫描，计算倒数三个点，如果构成右拐，则记为凸包点；如果构成左拐，则剔除前一点，依次生成根据h升序排列的点集，称为上凸包，反相扫描计算h或者θ坐标的降序排列的点集，称为下凸包，与上凸包一起构成整个凸包。
[0020] 本发明的工作过程如下：
[0021] 第一步，管道敷设条件和约束表示：管道敷设涉及的因素很多，包括管道功能、制造工艺、安装工艺、维修要求、振动要求、热力要求、电气要求、美观要求、管内流体流速和流阻、流体泄漏预防等等因素，将各种影响管道布局的上述因素抽象量化成为管道敷设的条件和约束，在不违反这些条件的情况下将最短路径和靠近机匣作为优化敷设的设计目标和评价指标，通过三维敷设空间的二维展开模块和管道敷设密集区域识别模块进行管道敷设条件和约束的表示；
[0022] 第二步，模式识别：通过不可敷设区域图生成模块将管道敷设的种种条件和约束转化为统一可见的不可敷设区域图，每个约束和规则相应的转化为图上的一个不可敷设区域。每条管道在敷设前都会生成各自的不可敷设区域图，该图包括该管道敷设的各种设计信息和约束信息，管道敷设路径就是对这张不可敷设区域图的路径识别；
[0023] 第三步，生成管道的敷设路径：对模式识别的结果进行演绎，把盲目性变为有目的地去找解，让计算机达到具有一定程度的综观全局的归纳能力，利用对不可敷设区域图识别，通过凸包绕障计算模块生成管道的敷设路径，而并非盲目搜索，利用了管道实际敷设的多种约束条件和优化目标。
[0024] 与现有技术相比，本发明具有如下有益效果：
[0025] 本发明沿测地线敷设，与传统沿正交直角路径相比路径更短；本发明绕障时沿障碍即不可敷设区域切线敷设，比走折线路径更短；本发明在不可敷设区域之间沿直线敷设，比沿曲线敷设路径更短；另外，由于本发明的绕障过程由最短的直线开始不断变长，且每次变长的过程都在保证绕过障碍的条件下最小限度的变长，因此本发明得到绕过障碍物的最短的管道路径。本发明大大简化了以往发动机管道敷设的计算复杂度，本发明的时间复杂度为O(nlogn)，为线性级。
[0026] 总体上来说，本发明与传统方法相比，综合利用了多种管道敷设约束条件在更短的时间内解决了管道敷设绕障的最短路径问题，有效地解决了发动机复杂管路敷设问题。
[0027] 附图说明
[0028] 图1是本发明中的三维敷设空间的二维展开模块获得的立体平面图。
[0029] 图2是本发明中的管道敷设密集区域识别排序模块使用的平衡二分查找树方法示意图；
[0030] 图中，(a)为树形结构图，(b)为查找到的线段示意图。
[0031] 图3是本发明中的管道敷设密集区域识别排序模块进行的同层管道密集区域识别及划分方法示意图。
[0032] 图4是本发明的不可敷设区域的三维划分示意图。
[0033] 图5是本发明凸包绕障计算模块采用三维凸包绕障最短路径方法示意图；
[0034] 图中，(a)为绕过一个不可敷设区域的最短路径示意图，(b)为绕过多个不可敷设区域的最短路径示意图。
具体实施方式
[0035] 下面结合附图对本发明的实施例作详细说明：本实施例在以本发明技术方案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限于下述的实施例。
[0036] 本实施例包括：接口模块、三维敷设空间的二维展开模块、管道敷设密集区域识别排序模块、不可敷设区域图生成模块、凸包绕障计算模块，其中：
[0037] 接口模块负责实现发动机管道敷设系统与三维设计软件之间的数据交换，将三维设计软件中的设计参数生成发动机管道敷设系统能够识别的TXT文本格式并进行储存，将发动机管道敷设系统得到的管道敷设结果生成三维设计软件能够识别的TXT文本格式并由三维设计软件生成三维管道敷设模型；
[0038] 三维敷设空间的二维展开模块是指将发动机及其附件的设计模型经过接口模块转化成TXT文本并从中提取几何信息，沿发动机轴流方向周向展开，将其原有正交的笛卡儿坐标转换成正交的柱坐标，用二维方式表示三维的敷设空间；
[0039] 管道敷设密集区域识别排序模块是指根据发动机及其附件的设计模型的要求以及管道属性的要求进行管道敷设区域的疏密识别和管道的敷设顺序的设定，设定的顺序包括：由内而外分层顺序、由密到疏分区域顺序、由粗到细分管径顺序、由短到长顺序；
[0040] 不可敷设区域图生成模块是根据三维敷设空间的二维展开模块和管道敷设密集区域识别排序模块得到的结果，将管道敷设的条件和约束转化为统一可见的不可敷设区域图表示在二维展开图上，将每个条件和约束转化为图上的一个不可敷设区域，每条管道在敷设前都会生成各自的不可敷设区域图，不可敷设区域图包括该管道敷设的各种设计信息和约束信息；
[0041] 凸包绕障计算模块是指利用凸包方法获得管道在不可敷设区域图中绕障的最短路径并生成管道中心线轨迹。
[0042] 本实施例中，将在三维设计软件(如CAD、UG等)中生成的发动机机匣曲面、安装短舱及各发动机外部附件的几何信息通过接口模块将数据传输到三维敷设空间的二维展开模块并转化到MATLAB或者VC环境下的管道敷设模块的敷设曲面数据库中，该敷设曲面数据库将发动机机匣曲面、安装短舱及发动机附件的几何信息以离散的点的形式用三维数组存储。
[0043] 其次，将所有管道的起点、终点的几何位置信息以及管道的内外径信息输入管道参数数据库中，该管道参数数据库用二维数组将每根管道的起点、终点的位置和方向信息以及管道的材质、密度管道规格、管道编号、管内流质、管道极限温度等参数存储起来，作为后面管道敷设的计算依据。
[0044] 所述的三维敷设空间的二维展开模块，是指将三维笛卡儿空间模型用圆柱坐标进行两位展开，将三维甚至更高维的问题映射到二维平面中予以解决，以降低问题建模的复杂程度。对于常见的轴流式发动机，发动机和安装舱都为类柱体，而管道的敷设走向都在类柱面上，管道的中心线是在类柱面上形成的三维空间曲线。因此，将发动机及其附件的设计模型沿其轴流方向周向展开，将其原有正交的笛卡儿坐标转换成同样正交的柱坐标，即(x，y，z)变成(θ，r，h)，其中以x方向作为θ的起点和终点，如图1所示。
[0045] 所述的管道敷设密集区域识别排序模块，其按照由内而外分层顺序敷设管道，具体如下：对内机匣表面到安装短舱之间的空间沿r方向分成n+1个层，每根管道根据每两次维修更换的平均间隔小时数由长到短排序，根据数量级分配到n+1个层里使每根管道都对应一个层；相反的每个层都对应一定数量的管道。敷设的时候根据由内层到外层的顺序进行，层别是管道敷设顺序的第一因素；
[0046] 所述的管道敷设密集区域识别排序模块，其按照由密到疏分区域顺序敷设管道，具体如下：针对每一层，对其上的管道的起始点和终止点连测地曲线，在柱面展开后表现为直线段，求其相互的交点，具体采用输出敏感算的平衡二分查找树方法，如图2所示，使用一条扫描线沿θ或h增大方向进行扫描，与当前扫描线相交的每条线段，都按照次序，存放在平衡二分查找树T的某片叶子处，只要输入始末点集S，经过计算就得到输出S中各线段之间的所有交点及穿过各交点的线段信息。对其沿(θ，h)进行网格划分，划分以该层最粗管道直径的三倍作为依据。每个始末点及交点都落在某个(dθ，dh)的网格内，根据每个区域内包含的始末点和交点个数对网格进行编号，数字越大表示交点越多，也意味着该区域管路越密集，如图3所示，先敷设管路密集的区域(数字大的区域涉及的管道)，后敷设管道稀疏的区域(数字小的区域涉及的管道)。
[0047] 所述的管道敷设密集区域识别排序模块，其按照由粗到细分管径顺序以及短管优先于长管顺序敷设管道，具体如下：针对同一层同一密集区域的管道，先敷设粗管后敷设细管，细管沿着粗管敷设，并用管卡固定在粗管上；对于相同直径的管路，则短管优先于长管，短管是指始末点连线段较短的管道。
[0048] 所述的不可敷设区域图生成模块，是指将每个约束管道敷设的因素和条件都转化成空间上的一个区域划分，将空间上管道不可以通过的区域用“1”，可以通过的区域用“0”表示，“1”的区域是各种对管道敷设的约束，包括振动、工艺、维修等方面的条件，包括如下：①不符合振动要求的空间区域都被划分为“1”区域，②将干涉维修孔和工艺孔的空间区域都划分为“1”区域；③既可以是人为的分层、分区域造成的，也可以是真实的发动机附件障碍生成的，所有已经存在的物理障碍占据的空间和人为设置的不能通过的区域都被划分为“1”区域，每个不可敷设空间形成一个封闭的空间集合，其并集的补集就是该管道最终的三维可敷设空间。
[0049] 本实施例中，三维敷设空间的二维展开模块将发动机及其附件的外曲面模型经过柱坐标转化成为了一张包含模型几何参数的立体平面图，平面图是指该图不再是柱状曲面，立体是指该图的高度方向表示的是发动机表面距展开轴的距离，原本在发动机表面复杂的三维空间障碍信息被简化为二维等高图。工作空间被(dθ，dr，dh)三个微分分量分成一个个小单元，每个小单元有两个状态，即“1”和“0”，“1”表示该单元表示的空间为不可敷设空间，“0”表示该单元为可敷设空间。如图4所示，黑色方块表示不可敷设空间，白色方块表示可敷设空间。将同一(θ，h)坐标的空间柱沿r方向进行综合统筹，根据该空间柱是否足够通过一定管径的管道以及该柱与周围柱是否连通，在二维平面图上再用“1”和“0”来表示该点的可敷设性。这样就通过二维平面图表示了三维空间的不可敷设区域。由于发动机布管空间根据半径被分成了若干布管的层，不同的分层的不可敷设区域的大小和位置呈现不同的形状。
[0050] 所述的凸包绕障计算模块，是指当得到了每根管道的不可敷设空间并将其在(θ，h)平面中进行了投影以后，布管工作是在二维可敷设区域图中，起点到终点连成的直线段穿过一个或多个不可敷设区域，在可敷设区域中寻找最短路径绕过这些不可敷设区域。
[0051] 如图5(a)所示，所述的凸包绕障计算模块，其寻找最短路径绕过一个不可敷设区域时，具体如下：连接管道起点到终点，将两点间最靠近起点和终点两个不可敷设区域点(即标号“1”点)记为穿入点和穿出点，将穿入点和穿出点的中点记为内点，获得所有与内点相邻的不可敷设点，记为点集合K，求该点集合K的凸包，得到凸包集合B；针对凸包集合B与所有起点终点一起再次求凸包得到点序列P，P为有序点集合，其中从起点到终点的点序列即为管道绕过该不可敷设区域的最短路线。
[0052] 如图5(b)所示，所述的凸包绕障计算模块，其寻找最短路径绕过多个不可敷设区域，具体如下：连接管道起点到终点，将两点间最靠近起点和终点的两个不可敷设区域点以及可敷设区域与不可敷设区域的交界点(即从可敷设区域进入不可敷设区域的点或者从不可敷设区域进入可敷设区域的点)，记为穿入点集合和穿出点集合，共n对点，其中n为穿过的独立的不可敷设区域的个数；再根据每对点计算中点，记为内点集合，求取所有与内点集合相邻的不可敷设点，记为点集合[K1，K2，K3，...，Kn]，分别对点集合Kn求凸包，得到凸包集合序列[B1，B2，B3，...，Bn]，针对凸包集合和起点、终点再次计算凸包，得到有序点序列P，取P中从起点到终点的点序列，从中取出可敷设区域与不可敷设区域的交界点(即从可敷设区域进入不可敷设区域的点或者从不可敷设区域进入可敷设区域的点)与起点终点组成新的点序列P’，其中除了起点和终点，依然还有n对点，取P’中相邻的n-1对点，作为新的起点和终点反复上面操作，每个循环过程直到新起点和终点的连线不再穿过不可敷设区域中止，得到的折线是管道起点到终点绕过所有不可敷设区域的最短路线。
[0053] 所述凸包绕障计算模块，其求取凸包具体如下：根据求取点的h或者θ坐标对所有点形成有序序列，并从最小h或者θ坐标向最大h或者θ坐标扫描，计算倒数三个点，如果构成右拐，则记为凸包点；如果构成左拐，则剔除前一点，依次生成根据h升序排列的点集，称为上凸包，反相扫描计算h或者θ坐标的降序排列的点集，称为下凸包，与上凸包一起构成整个凸包。
[0054] 本实施例可以通过MATLAB或者VC环境编译实现，但不限于上述编译环境。
[0055] 本实施例大大简化了以往发动机管道敷设的计算复杂度，本实施例的时间复杂度为O(nlogn)，为线性级。总体上来说，本实施例方法与传统方法相比，综合利用了多种管道敷设约束条件在更短的时间内解决了管道敷设绕障的最短路径问题，有效地解决了发动机复杂管路敷设问题。
