Movatterモバイル変換

[0]ホーム
URL:

CN101996516A - Path planning pretreatment method based on vector method - Google Patents

Path planning pretreatment method based on vector methodDownload PDF

Info

Publication number
CN101996516A
CN101996516ACN 201010552741CN201010552741ACN101996516ACN 101996516 ACN101996516 ACN 101996516ACN 201010552741CN201010552741CN 201010552741CN 201010552741 ACN201010552741 ACN 201010552741ACN 101996516 ACN101996516 ACN 101996516A
Authority
CN
China
Prior art keywords
polygon
path planning
convex
polygons
distance
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN 201010552741
Other languages
Chinese (zh)
Inventor
赵英男
孟宪权
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nanjing University of Information Science and Technology
Original Assignee
Nanjing University of Information Science and Technology
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nanjing University of Information Science and TechnologyfiledCriticalNanjing University of Information Science and Technology
Priority to CN 201010552741priorityCriticalpatent/CN101996516A/en
Publication of CN101996516ApublicationCriticalpatent/CN101996516A/en
Pendinglegal-statusCriticalCurrent

Links

Images

Landscapes

Abstract

Translated fromChinese

本发明公开了一种基于矢量法的路径规划预处理方法，用于矢量法表示的仿真系统路径规划。本发明方法首先将仿真环境中的每个障碍物均模型化为凸多边形；然后将凸多边形中距离小于预先设定的阈值的任意两个凸多边形融合处理为一个新的凸多边形，并依次迭代处理，直到最终得到的凸多边形中任意两个的距离均大于上述预先设定的阈值，其中，所述阈值是根据路径规划中最大移动主体的尺寸进行设置；最后将融合的结果作为仿真系统中路径规划的初始状态。本发明针对仿真环境中的移动主体不能够穿越距离小于自身的障碍物这一事实，将距离小于移动主体尺寸的障碍物进行合并，从而降低了仿真系统中后续路径规划的工作量，提高了整个系统的实时处理能力。

Figure 201010552741

The invention discloses a path planning preprocessing method based on a vector method, which is used for path planning of a simulation system represented by a vector method. The method of the present invention first models each obstacle in the simulation environment as a convex polygon; then fuses and processes any two convex polygons whose distance is smaller than a preset threshold in the convex polygon into a new convex polygon, and iterates successively Process until the distance between any two of the finally obtained convex polygons is greater than the above-mentioned preset threshold, wherein the threshold is set according to the size of the largest moving subject in path planning; finally, the fusion result is used as The initial state of path planning. Aiming at the fact that the mobile body in the simulation environment cannot pass through the obstacles whose distance is smaller than itself, the present invention combines the obstacles whose distance is smaller than the size of the mobile body, thereby reducing the workload of subsequent path planning in the simulation system and improving the overall The real-time processing capability of the system.

Figure 201010552741

Description

Translated fromChinese
基于矢量法的路径规划预处理方法 Path planning preprocessing method based on vector method

技术领域technical field

本发明涉及路径规划预处理方法，尤其涉及一种基于矢量法的路径规划预处理方法，用于仿真技术领域。The invention relates to a path planning preprocessing method, in particular to a path planning preprocessing method based on a vector method, which is used in the technical field of simulation.

背景技术Background technique

路径规划(Path Planning)是指按照某个评价标准(如最短路径长度、最短行进时间、最小能量消耗等)，满足某个约束条件(如避免与障碍物碰撞等)，规划一条从起始点位置到达目标点位置最优(或次优)的路径（详细内容可参考文献[戴光明. 避障路径规划的算法研究[D]. 武汉: 华中科技大学, 2004]）。路径规划作为一个经典的人工智能问题，在仿真、机器人、无人驾驶车辆等领域得到了广泛而深入的研究。目前，在这些领域使用的路径规划方法主要有图搜索算法（如A*算法[苏浩，李钦富，蔡骏. A*算法在基于道路网的路径规划中的应用. 中国电子科学研究院学报, 2010, 5(4): 419-422.]，Dijkstra算法[WAN Ming, ZHANG Wei, MURRAY Marie O., KAUFMAN Arie. Automatic target tracking on multi-resolution terrain. Journal of Zhejiang University, 2006, 7(7): 1275-1281.]、基于软计算的规划方法（如遗传算法[梁晓辉，吴威，赵沁平. 大规模真实地形数据中的全局路径规划方法——基于遗传算法的研究. 计算机研究与发展, 2002, 39(3): 301-306.]，蚁群算法[TAN Guan-zheng, HE Huan, Aaron Sloman. Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm. Journal of Central South University of Technology, 2006, 13(1): 80-86]、基于随机采样的规划方法（如快速扩展随机树(Rapidly-exploring Random Tree，RRT[樊晓平，彭展，张恒，罗熊. 基于快速扩展随机树的机器人路径规划仿真实验平台研究. 铁道科学与工程学报, 2005, 2(2): 86-92])等。上述方法都建立在一定的空间数据结构表示方法之上，常用的有矢量法和栅格法。Path planning (Path Planning) refers to planning a route from the starting point according to a certain evaluation standard (such as the shortest path length, shortest travel time, minimum energy consumption, etc.) and satisfying a certain constraint condition (such as avoiding collision with obstacles, etc.). The optimal (or suboptimal) path to the target point (for details, please refer to [Dai Guangming. Algorithm Research on Obstacle Avoidance Path Planning [D]. Wuhan: Huazhong University of Science and Technology, 2004]). As a classic artificial intelligence problem, path planning has been widely and deeply studied in the fields of simulation, robotics, and unmanned vehicles. At present, the path planning methods used in these fields mainly include graph search algorithms (such as A* algorithm [Su Hao, Li Qinfu, Cai Jun. Application of A* algorithm in path planning based on road network. Journal of China Institute of Electronic Science, 2010, 5(4): 419-422.], Dijkstra algorithm [WAN Ming, ZHANG Wei, MURRAY Marie O., KAUFMAN Arie. Automatic target tracking on multi-resolution terrain. Journal of Zhejiang University, 2006, 7(7) : 1275-1281.], planning methods based on soft computing (such as genetic algorithms [Liang Xiaohui, Wu Wei, Zhao Qinping. Global path planning methods in large-scale real terrain data - research based on genetic algorithms. Computer Research and Development, 2002 , 39(3): 301-306.], Ant Colony Algorithm [TAN Guan-zheng, HE Huan, Aaron Sloman. Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm. Journal of Central South University of Technology, 2006, 13(1): 80-86], planning methods based on random sampling (such as Rapidly-exploring Random Tree, RRT [Fan Xiaoping, Peng Zhan, Zhang Heng, Luo Xiong. Based on Rapidly-exploring Random Tree Research on the robot path planning simulation experiment platform of trees. Journal of Railway Science and Engineering, 2005, 2(2): 86-92]), etc. The above methods are all based on a certain spatial data structure representation method, and the vector method is commonly used and grid method.

在仿真系统中，实时性是非常重要的因素。如果出现滞后或延迟，会导致仿真系统的真实感下降。而在路径规划这方面，已有的技术专注于系统运行期间的一些优化技术，而未关注前期的数据预处理。In the simulation system, real-time performance is a very important factor. If there is lag or delay, it will cause a loss of realism to the simulated system. In terms of path planning, existing technologies focus on some optimization techniques during system operation, but do not pay attention to early data preprocessing.

发明内容Contents of the invention

本发明目的是针对目前仿真系统的路径规划时间过长，提出一种基于矢量法的路径规划预处理方法，该方法可以有效提高仿真系统路径规划时的实时处理速度。The purpose of the present invention is to propose a path planning preprocessing method based on a vector method for the long path planning time of the current simulation system, which can effectively improve the real-time processing speed of the path planning of the simulation system.

本发明的思路是针对仿真环境中的移动主体不能够穿越距离小于自身的障碍物这一事实，根据路径规划中最大移动主体的尺寸设置一个阈值，将距离小于该阈值的障碍物进行合并，从而降低仿真系统中后续路径规划的工作量，提高整个系统的实时处理能力。The idea of the present invention is to aim at the fact that the moving subject in the simulation environment cannot pass through obstacles whose distance is smaller than itself, and set a threshold according to the size of the largest moving subject in path planning, and combine the obstacles whose distance is smaller than the threshold, so that Reduce the workload of subsequent path planning in the simulation system and improve the real-time processing capability of the entire system.

具体而言，本发明采用以下技术方案：Specifically, the present invention adopts the following technical solutions:

一种基于矢量法的路径规划预处理方法，用于矢量法表示的仿真系统路径规划，该方法包括以下步骤：A path planning preprocessing method based on a vector method is used for path planning of a simulation system represented by a vector method, and the method includes the following steps:

步骤A、将仿真环境中的每个障碍物均模型化为凸多边形；Step A, modeling each obstacle in the simulation environment as a convex polygon;

步骤B、将步骤A中得到的凸多边形中距离小于预先设定的阈值的任意两个凸多边形融合处理为一个新的凸多边形，并依次迭代处理，直到最终得到的凸多边形中任意两个的距离均大于上述预先设定的阈值；其中，所述预先设定的阈值等于路径规划中最大移动主体的尺寸；Step B, merging any two convex polygons whose distance is smaller than a preset threshold in the convex polygon obtained in step A into a new convex polygon, and iteratively processing in turn until any two of the convex polygons finally obtained The distances are all greater than the aforementioned preset threshold; wherein, the preset threshold is equal to the size of the largest moving subject in path planning;

步骤C、将步骤B得到的结果作为仿真系统中路径规划的初始状态。Step C, using the result obtained in step B as the initial state of path planning in the simulation system.

仿真系统中的建模方法有很多，如三维建模、栅格法等，为了简化计算并便于后续的相交判断和融合处理，本发明在将障碍物模型化为凸多边形时优选在欧式平面中实现。There are many modeling methods in the simulation system, such as three-dimensional modeling, grid method, etc., in order to simplify the calculation and facilitate the subsequent intersection judgment and fusion processing, the present invention preferably models the obstacle as a convex polygon in the Euclidean plane accomplish.

其中，凸多边形之间的距离采用最小距离法定义，即两个凸多边形上距离最小的两个点之间的距离。Among them, the distance between convex polygons is defined by the minimum distance method, that is, the distance between two points with the smallest distance on two convex polygons.

步骤B具体包括以下各步骤：Step B specifically includes the following steps:

步骤B1、设置变量的初始值为步骤A得到的凸多边形的数量；Step B1, the initial value of setting variable is the quantity of the convex polygon that step A obtains;

步骤B2、设置变量、                                                

Figure 2010105527412100002DEST_PATH_IMAGE001
的值为：
Figure 433753DEST_PATH_IMAGE002
，
Figure 2010105527412100002DEST_PATH_IMAGE003
；Step B2, setting variables,
Figure 2010105527412100002DEST_PATH_IMAGE001
The value is:
Figure 433753DEST_PATH_IMAGE002
,
Figure 2010105527412100002DEST_PATH_IMAGE003
;

步骤B3、计算第

Figure 69265DEST_PATH_IMAGE001
个凸多边形与第
Figure 273982DEST_PATH_IMAGE004
个凸多边形的距离并判断该距离是否大于一个预先设定的阈值，如是，则转步骤B5；如否，则转步骤B4；Step B3, calculate the first
Figure 69265DEST_PATH_IMAGE001
convex polygon and the
Figure 273982DEST_PATH_IMAGE004
convex polygon and judge whether the distance is greater than a preset threshold, if so, then go to step B5; if not, then go to step B4;

步骤B4、将第

Figure 410565DEST_PATH_IMAGE001
个凸多边形与第
Figure 946021DEST_PATH_IMAGE004
个凸多边形融合为一个新的凸多边形并删除原第个与第
Figure 877068DEST_PATH_IMAGE004
个凸多边形，将
Figure 2010105527412100002DEST_PATH_IMAGE005
的值修改为
Figure 506763DEST_PATH_IMAGE006
后转步骤B2；Step B4, the first
Figure 410565DEST_PATH_IMAGE001
convex polygon and the
Figure 946021DEST_PATH_IMAGE004
Convex polygons are merged into a new convex polygon and the original th and th are deleted
Figure 877068DEST_PATH_IMAGE004
a convex polygon, the
Figure 2010105527412100002DEST_PATH_IMAGE005
The value of is changed to
Figure 506763DEST_PATH_IMAGE006
Turn to step B2;

步骤B5、判断是否

Figure 2010105527412100002DEST_PATH_IMAGE007
，如是，则转步骤B6；如否，则将的值修改为后转步骤B3；Step B5, determine whether
Figure 2010105527412100002DEST_PATH_IMAGE007
, if yes, go to step B6; if no, modify the value of to Turn to step B3;

步骤B6、判断是否

Figure 2010105527412100002DEST_PATH_IMAGE011
，如是，则结束；如否，则将
Figure 2010105527412100002DEST_PATH_IMAGE013
的值修改为并将
Figure 929261DEST_PATH_IMAGE015
的值修改为
Figure 2010105527412100002DEST_PATH_IMAGE017
并后转步骤B3。Step B6, determine whether
Figure 2010105527412100002DEST_PATH_IMAGE011
, if yes, end; if no, then
Figure 2010105527412100002DEST_PATH_IMAGE013
The value of is changed to and will
Figure 929261DEST_PATH_IMAGE015
The value of is changed to
Figure 2010105527412100002DEST_PATH_IMAGE017
And turn to step B3.

本发明中，将两个凸多边形融合处理为一个新的凸多边形，具体按照以下方法：In the present invention, two convex polygons are fused and processed into a new convex polygon, specifically according to the following method:

以其中一个多边形的中心为原点，该多边形的两个顶点的连线为纵轴，两个多边形的中心连线为横轴，建立相对坐标系；在该相对坐标系中，在两个多边形中寻找进行纵坐标绝对值最大的4个顶点作为一级融合点；如果一级融合点的连线与多边形相交，则在一级融合点集合中寻找二级融合点，使之连线与多边形不相交，同时删除该二级融合点取代的一级融合点；将现有融合点连在一起合成一个凸多边形，完成两个多边形的融合。Taking the center of one of the polygons as the origin, the line connecting the two vertices of the polygon as the vertical axis, and the line connecting the centers of the two polygons as the horizontal axis, establish a relative coordinate system; in this relative coordinate system, in the two polygons Find the 4 vertices with the largest absolute value of the ordinate as the first-level fusion point; if the connection line of the first-level fusion point intersects the polygon, then find the second-level fusion point in the first-level fusion point set so that the connection line and the polygon do not Intersect, and delete the first-level fusion point replaced by the second-level fusion point; connect the existing fusion points together to form a convex polygon, and complete the fusion of the two polygons.

本发明基于常用的路径规划空间矢量表示法，首先将仿真环境中的障碍物模型化为欧氏平面中的凸多边形；然后对距离小于某一阈值的任意两个凸多边形融合处理为一个新的凸多边形，并依次迭代处理，直到最终得到的凸多边形中任意两个的距离均大于上述预先设定的阈值。即将距离小于阈值的多障碍物合成一个，从而有效降低路径规划的计算量。相比现有技术，本发明的优点在于针对仿真环境中的移动主体不能够穿越距离小于自身的障碍物这一事实，将距离小于某一阈值的障碍物进行合并，对路径规划进行预处理，从而有效加快实际的路径规划时间，提高系统的实时处理速度。Based on the commonly used path planning space vector representation method, the present invention first models the obstacles in the simulation environment as convex polygons in the Euclidean plane; then fuses and processes any two convex polygons whose distance is less than a certain threshold into a new convex polygons, and iteratively process them in turn until the distance between any two of the finally obtained convex polygons is greater than the above-mentioned preset threshold. That is to combine multiple obstacles whose distance is less than the threshold into one, so as to effectively reduce the calculation amount of path planning. Compared with the prior art, the present invention has the advantage of combining the obstacles whose distance is less than a certain threshold and preprocessing the path planning, aiming at the fact that the moving subject in the simulation environment cannot pass through obstacles whose distance is smaller than itself. Therefore, the actual path planning time is effectively accelerated, and the real-time processing speed of the system is improved.

附图说明Description of drawings

图1是本发明的基于矢量法的路径规划预处理方法流程图；Fig. 1 is the flow chart of the path planning preprocessing method based on the vector method of the present invention;

图2是本发明方法中两个凸多边形之间距离计算的示意图；Fig. 2 is the schematic diagram of distance calculation between two convex polygons in the inventive method;

图3是本发明方法中点到图形的距离计算示意图，其中（a）为点到多边形的距离计算，（b）为点到直线段的距离计算；Fig. 3 is a schematic diagram of calculating the distance from a point to a graph in the method of the present invention, wherein (a) is calculating the distance from a point to a polygon, and (b) is calculating the distance from a point to a straight line segment;

图4是本发明方法中融合点的计算示意图，其中（a）为计算过程，（b）为计算结果；Fig. 4 is a schematic diagram of the calculation of fusion points in the method of the present invention, wherein (a) is the calculation process, and (b) is the calculation result;

图5是具体实施方式中所述射线与多边形的相交判断方法示意图；Fig. 5 is a schematic diagram of the method for judging the intersection of a ray and a polygon in the specific embodiment;

图6是本发明方法在融合处理过程中不同阶段的示意图；Fig. 6 is a schematic diagram of different stages in the fusion process of the method of the present invention;

图7是分别采用栅格法和本发明方法进行路径规划的结果比较；Fig. 7 adopts the result comparison of grid method and the method of the present invention to carry out path planning respectively;

图8是分别采用栅格法和本发明方法进行路径规划的时间结果比较。Fig. 8 is a comparison of the time results of path planning using the grid method and the method of the present invention respectively.

具体实施方式Detailed ways

下面结合附图及实施例对本发明的技术方案进行详细说明：Below in conjunction with accompanying drawing and embodiment the technical solution of the present invention is described in detail:

本实施例采用如图6（a）所示的二维虚拟仿真环境，经模型化处理后共有26个用凸多边形表示的障碍物，根据该仿真环境中移动主体的尺寸将阈值

Figure 2010105527412100002DEST_PATH_IMAGE019
设定为5。然后按照以下方法对这26个凸多边形进行处理（处理流程如附图1所示）：This embodiment adopts the two-dimensional virtual simulation environment shown in Figure 6(a). After modeling, there are 26 obstacles represented by convex polygons. According to the size of the moving subject in the simulation environment, the threshold
Figure 2010105527412100002DEST_PATH_IMAGE019
Set to 5. Then process these 26 convex polygons according to the following method (the processing flow is shown in Figure 1):

步骤B1、设置变量

Figure 2010105527412100002DEST_PATH_IMAGE021
的初始值为步骤A得到的凸多边形的数量，本实施例中的初始值即为26；Step B1, set variables
Figure 2010105527412100002DEST_PATH_IMAGE021
The initial value of is the number of convex polygons obtained in step A, in this embodiment The initial value of is 26;

步骤B2、设置变量

Figure 2010105527412100002DEST_PATH_IMAGE023
、
Figure 508589DEST_PATH_IMAGE015
的值为：
Figure 2010105527412100002DEST_PATH_IMAGE025
，
Figure 2010105527412100002DEST_PATH_IMAGE027
；Step B2, set variables
Figure 2010105527412100002DEST_PATH_IMAGE023
,
Figure 508589DEST_PATH_IMAGE015
The value is:
Figure 2010105527412100002DEST_PATH_IMAGE025
,
Figure 2010105527412100002DEST_PATH_IMAGE027
;

步骤B3、计算第

Figure 503877DEST_PATH_IMAGE015
个凸多边形与第
Figure 654366DEST_PATH_IMAGE028
个凸多边形的距离并判断该距离是否大于一个预先设定的阈值，如是，则转步骤B5；如否，则转步骤B4；Step B3, calculate the first
Figure 503877DEST_PATH_IMAGE015
convex polygon and the
Figure 654366DEST_PATH_IMAGE028
convex polygon and judge whether the distance is greater than a preset threshold, if so, then go to step B5; if not, then go to step B4;

步骤B4、将第

Figure 235521DEST_PATH_IMAGE015
个凸多边形与第
Figure 2010105527412100002DEST_PATH_IMAGE029
个凸多边形融合为一个新的凸多边形并删除原第
Figure 443123DEST_PATH_IMAGE015
个与第
Figure 109728DEST_PATH_IMAGE009
个凸多边形，将
Figure 126226DEST_PATH_IMAGE021
的值修改为
Figure 2010105527412100002DEST_PATH_IMAGE031
后转步骤B2；Step B4, the first
Figure 235521DEST_PATH_IMAGE015
convex polygon and the
Figure 2010105527412100002DEST_PATH_IMAGE029
Convex polygons are merged into a new convex polygon and the original one is deleted
Figure 443123DEST_PATH_IMAGE015
and the first
Figure 109728DEST_PATH_IMAGE009
a convex polygon, the
Figure 126226DEST_PATH_IMAGE021
The value of is changed to
Figure 2010105527412100002DEST_PATH_IMAGE031
Turn to step B2;

步骤B5、判断是否

Figure DEST_PATH_IMAGE033
，如是，则转步骤B6；如否，则将
Figure 437252DEST_PATH_IMAGE013
的值修改为
Figure 208899DEST_PATH_IMAGE009
后转步骤B3；Step B5, determine whether
Figure DEST_PATH_IMAGE033
, if yes, go to step B6; if no, then
Figure 437252DEST_PATH_IMAGE013
The value of is changed to
Figure 208899DEST_PATH_IMAGE009
Turn to step B3;

步骤B6、判断是否

Figure 34904DEST_PATH_IMAGE011
，如是，则结束；如否，则将
Figure 869741DEST_PATH_IMAGE013
的值修改为
Figure 159908DEST_PATH_IMAGE015
并将
Figure 40139DEST_PATH_IMAGE015
的值修改为
Figure 415757DEST_PATH_IMAGE017
并后转步骤B3。Step B6, determine whether
Figure 34904DEST_PATH_IMAGE011
, if yes, end; if no, then
Figure 869741DEST_PATH_IMAGE013
The value of is changed to
Figure 159908DEST_PATH_IMAGE015
and will
Figure 40139DEST_PATH_IMAGE015
The value of is changed to
Figure 415757DEST_PATH_IMAGE017
And turn to step B3.

本发明中，任意两个多边形的距离采用最小间距法进行计算并根据预先设定的阈值判断是否进行融合，In the present invention, the distance between any two polygons is calculated using the minimum distance method and judges whether to perform fusion according to a preset threshold.

采用最小间距判断法计算两个多边形之间的距离，首先如附图2所示，建立以O1为原心，O1O2方向为横坐标轴方向的相对坐标系O'x'y'，在该坐标系下

Figure DEST_PATH_IMAGE035
＝(
Figure 711740DEST_PATH_IMAGE037
)(
Figure 121993DEST_PATH_IMAGE039
)，
Figure 235443DEST_PATH_IMAGE041
＝(
Figure 98356DEST_PATH_IMAGE043
)(
Figure 257418DEST_PATH_IMAGE045
)，O1=(0,0)，O2=(l12,0)，l12=
Figure 256598DEST_PATH_IMAGE047
。Use the minimum distance judgment method to calculate the distance between two polygons. First, as shown in Figure 2, establish a relative coordinate systemO 'x 'y ' withO1 as the original center andO1O2 as the direction of the abscissa axis , in this coordinate system
Figure DEST_PATH_IMAGE035
=(
Figure 711740DEST_PATH_IMAGE037
)(
Figure 121993DEST_PATH_IMAGE039
),
Figure 235443DEST_PATH_IMAGE041
=(
Figure 98356DEST_PATH_IMAGE043
)(
Figure 257418DEST_PATH_IMAGE045
),O1 =(0,0),O2 =(l12 ,0),l12 =
Figure 256598DEST_PATH_IMAGE047
.

先计算O1的所有顶点距离O2的最小值：First calculate the minimum value of all vertices ofO1 fromO2 :

Figure 478632DEST_PATH_IMAGE049
 1：比较
Figure 2010105527412100002DEST_PATH_IMAGE050
的横坐标，得到顶点，且
Figure 2010105527412100002DEST_PATH_IMAGE054
；
Figure 478632DEST_PATH_IMAGE049
1: Compare
Figure 2010105527412100002DEST_PATH_IMAGE050
The abscissa of the vertex ,and
Figure 2010105527412100002DEST_PATH_IMAGE054
;

Figure 704208DEST_PATH_IMAGE049
 2：令，计算顶点
Figure 2010105527412100002DEST_PATH_IMAGE058
、
Figure 2010105527412100002DEST_PATH_IMAGE060
、
Figure 2010105527412100002DEST_PATH_IMAGE062
与多边形O2的距离，分别为
Figure 2010105527412100002DEST_PATH_IMAGE064
、
Figure 2010105527412100002DEST_PATH_IMAGE066
、
Figure 2010105527412100002DEST_PATH_IMAGE068
；
Figure 704208DEST_PATH_IMAGE049
2: order , computing the vertices
Figure 2010105527412100002DEST_PATH_IMAGE058
,
Figure 2010105527412100002DEST_PATH_IMAGE060
,
Figure 2010105527412100002DEST_PATH_IMAGE062
The distancesto polygonO2 are respectively
Figure 2010105527412100002DEST_PATH_IMAGE064
,
Figure 2010105527412100002DEST_PATH_IMAGE066
,
Figure 2010105527412100002DEST_PATH_IMAGE068
;

Figure 298918DEST_PATH_IMAGE049
 3：若
Figure 2010105527412100002DEST_PATH_IMAGE070
Figure 2010105527412100002DEST_PATH_IMAGE072
Figure 355867DEST_PATH_IMAGE073
，则，
Figure 317799DEST_PATH_IMAGE077
=
Figure 821593DEST_PATH_IMAGE064
，转
Figure 60944DEST_PATH_IMAGE049
 4。若
Figure 359202DEST_PATH_IMAGE070
Figure 684004DEST_PATH_IMAGE072
Figure 53805DEST_PATH_IMAGE066
，则=
Figure 554505DEST_PATH_IMAGE066
，转
Figure 163341DEST_PATH_IMAGE049
 8。若
Figure 265727DEST_PATH_IMAGE070
Figure 214091DEST_PATH_IMAGE072
Figure 119731DEST_PATH_IMAGE081
，则，
Figure 2010105527412100002DEST_PATH_IMAGE084
=，转
Figure 678199DEST_PATH_IMAGE049
 6；
Figure 298918DEST_PATH_IMAGE049
3: if
Figure 2010105527412100002DEST_PATH_IMAGE070
Figure 2010105527412100002DEST_PATH_IMAGE072
Figure 355867DEST_PATH_IMAGE073
,but ,
Figure 317799DEST_PATH_IMAGE077
=
Figure 821593DEST_PATH_IMAGE064
,change
Figure 60944DEST_PATH_IMAGE049
4. like
Figure 359202DEST_PATH_IMAGE070
Figure 684004DEST_PATH_IMAGE072
Figure 53805DEST_PATH_IMAGE066
,but =
Figure 554505DEST_PATH_IMAGE066
,change
Figure 163341DEST_PATH_IMAGE049
8. like
Figure 265727DEST_PATH_IMAGE070
Figure 214091DEST_PATH_IMAGE072
Figure 119731DEST_PATH_IMAGE081
,but ,
Figure 2010105527412100002DEST_PATH_IMAGE084
= ,change
Figure 678199DEST_PATH_IMAGE049
6;

Figure 481070DEST_PATH_IMAGE049
 4：计算顶点
Figure 554681DEST_PATH_IMAGE058
与多边形O2的距离
Figure 75792DEST_PATH_IMAGE064
；
Figure 481070DEST_PATH_IMAGE049
4: Calculate vertices
Figure 554681DEST_PATH_IMAGE058
Distance frompolygonO2
Figure 75792DEST_PATH_IMAGE064
;

Figure 263191DEST_PATH_IMAGE049
 5：若
Figure 2010105527412100002DEST_PATH_IMAGE086
Figure 999197DEST_PATH_IMAGE089
，则
Figure 246638DEST_PATH_IMAGE075
，=，转
Figure 186748DEST_PATH_IMAGE049
 4。若
Figure 26528DEST_PATH_IMAGE064
Figure 382554DEST_PATH_IMAGE077
，则转
Figure 612679DEST_PATH_IMAGE049
 8；
Figure 263191DEST_PATH_IMAGE049
5: if
Figure 2010105527412100002DEST_PATH_IMAGE086
Figure 999197DEST_PATH_IMAGE089
,but
Figure 246638DEST_PATH_IMAGE075
, = ,change
Figure 186748DEST_PATH_IMAGE049
4. like
Figure 26528DEST_PATH_IMAGE064
Figure 382554DEST_PATH_IMAGE077
, then turn
Figure 612679DEST_PATH_IMAGE049
8;

 6：计算顶点与多边形O2的距离

Figure 690990DEST_PATH_IMAGE081
； 6: Calculate the vertices Distance frompolygonO2
Figure 690990DEST_PATH_IMAGE081
;

Figure 671060DEST_PATH_IMAGE049
 7：若
Figure 2010105527412100002DEST_PATH_IMAGE094
Figure 941635DEST_PATH_IMAGE088
，则，
Figure 658553DEST_PATH_IMAGE090
=，转
Figure 136119DEST_PATH_IMAGE049
 6。若
Figure 347393DEST_PATH_IMAGE081
Figure 101723DEST_PATH_IMAGE092
Figure 776417DEST_PATH_IMAGE077
，则转
Figure 237486DEST_PATH_IMAGE049
 8；
Figure 671060DEST_PATH_IMAGE049
7: if
Figure 2010105527412100002DEST_PATH_IMAGE094
Figure 941635DEST_PATH_IMAGE088
,but ,
Figure 658553DEST_PATH_IMAGE090
= ,change
Figure 136119DEST_PATH_IMAGE049
6. like
Figure 347393DEST_PATH_IMAGE081
Figure 101723DEST_PATH_IMAGE092
Figure 776417DEST_PATH_IMAGE077
, then turn
Figure 237486DEST_PATH_IMAGE049
8;

Figure 605013DEST_PATH_IMAGE049
 8：输出O1的所有顶点距离O2的最小值
Figure 518743DEST_PATH_IMAGE077
。
Figure 605013DEST_PATH_IMAGE049
8: Output the minimum value of all vertices ofO1 fromO2
Figure 518743DEST_PATH_IMAGE077
.

再计算O2的所有顶点距离O1的最小值：Then calculate the minimum value of all vertices ofO2 fromO1 :

Figure 997128DEST_PATH_IMAGE049
 1：比较
Figure DEST_PATH_IMAGE095
的横坐标，得到顶点
Figure DEST_PATH_IMAGE097
，且
Figure DEST_PATH_IMAGE099
；
Figure 997128DEST_PATH_IMAGE049
1: Compare
Figure DEST_PATH_IMAGE095
The abscissa of the vertex
Figure DEST_PATH_IMAGE097
,and
Figure DEST_PATH_IMAGE099
;

Figure 450719DEST_PATH_IMAGE049
 2：令
Figure DEST_PATH_IMAGE101
，计算顶点
Figure DEST_PATH_IMAGE103
、、
Figure DEST_PATH_IMAGE107
与多边形O1的距离，分别为
Figure 474301DEST_PATH_IMAGE064
、
Figure 140906DEST_PATH_IMAGE066
、
Figure 157403DEST_PATH_IMAGE081
；
Figure 450719DEST_PATH_IMAGE049
2: order
Figure DEST_PATH_IMAGE101
, computing the vertices
Figure DEST_PATH_IMAGE103
, ,
Figure DEST_PATH_IMAGE107
The distances to polygonO1 are
Figure 474301DEST_PATH_IMAGE064
,
Figure 140906DEST_PATH_IMAGE066
,
Figure 157403DEST_PATH_IMAGE081
;

Figure 595993DEST_PATH_IMAGE049
 3：若
Figure 102061DEST_PATH_IMAGE070
Figure 255962DEST_PATH_IMAGE072
Figure 76150DEST_PATH_IMAGE073
，则
Figure 366317DEST_PATH_IMAGE075
，
Figure DEST_PATH_IMAGE109
=
Figure 184232DEST_PATH_IMAGE064
，转
Figure 559850DEST_PATH_IMAGE049
 4。若
Figure 918150DEST_PATH_IMAGE070
Figure 325473DEST_PATH_IMAGE072
Figure 111026DEST_PATH_IMAGE066
，则
Figure 973940DEST_PATH_IMAGE110
=
Figure 135931DEST_PATH_IMAGE066
，转
Figure 400690DEST_PATH_IMAGE049
 8。若
Figure 972934DEST_PATH_IMAGE072
Figure 673037DEST_PATH_IMAGE081
，则
Figure 783513DEST_PATH_IMAGE083
，
Figure DEST_PATH_IMAGE111
=
Figure 176449DEST_PATH_IMAGE085
，转
Figure 13955DEST_PATH_IMAGE049
 6；
Figure 595993DEST_PATH_IMAGE049
3: if
Figure 102061DEST_PATH_IMAGE070
Figure 255962DEST_PATH_IMAGE072
Figure 76150DEST_PATH_IMAGE073
,but
Figure 366317DEST_PATH_IMAGE075
,
Figure DEST_PATH_IMAGE109
=
Figure 184232DEST_PATH_IMAGE064
,change
Figure 559850DEST_PATH_IMAGE049
4. like
Figure 918150DEST_PATH_IMAGE070
Figure 325473DEST_PATH_IMAGE072
Figure 111026DEST_PATH_IMAGE066
,but
Figure 973940DEST_PATH_IMAGE110
=
Figure 135931DEST_PATH_IMAGE066
,change
Figure 400690DEST_PATH_IMAGE049
8. like
Figure 972934DEST_PATH_IMAGE072
Figure 673037DEST_PATH_IMAGE081
,but
Figure 783513DEST_PATH_IMAGE083
,
Figure DEST_PATH_IMAGE111
=
Figure 176449DEST_PATH_IMAGE085
,change
Figure 13955DEST_PATH_IMAGE049
6;

 4：计算顶点

Figure DEST_PATH_IMAGE113
与多边形O1的距离
Figure 429204DEST_PATH_IMAGE064
； 4: Calculate vertices
Figure DEST_PATH_IMAGE113
Distance from polygonO1
Figure 429204DEST_PATH_IMAGE064
;

Figure 993040DEST_PATH_IMAGE049
 5：若
Figure 317842DEST_PATH_IMAGE086
Figure 356818DEST_PATH_IMAGE088
Figure 450676DEST_PATH_IMAGE111
，则
Figure 185414DEST_PATH_IMAGE075
，
Figure 731933DEST_PATH_IMAGE111
=
Figure 905425DEST_PATH_IMAGE064
，转
Figure 791473DEST_PATH_IMAGE049
 4。若
Figure 697112DEST_PATH_IMAGE064
Figure 117564DEST_PATH_IMAGE109
，则转
Figure 186015DEST_PATH_IMAGE049
 8；
Figure 993040DEST_PATH_IMAGE049
5: if
Figure 317842DEST_PATH_IMAGE086
Figure 356818DEST_PATH_IMAGE088
Figure 450676DEST_PATH_IMAGE111
,but
Figure 185414DEST_PATH_IMAGE075
,
Figure 731933DEST_PATH_IMAGE111
=
Figure 905425DEST_PATH_IMAGE064
,change
Figure 791473DEST_PATH_IMAGE049
4. like
Figure 697112DEST_PATH_IMAGE064
Figure 117564DEST_PATH_IMAGE109
, then turn
Figure 186015DEST_PATH_IMAGE049
8;

 6：计算顶点

Figure DEST_PATH_IMAGE115
与多边形O1的距离
Figure 783666DEST_PATH_IMAGE081
； 6: Calculate the vertices
Figure DEST_PATH_IMAGE115
Distance from polygonO1
Figure 783666DEST_PATH_IMAGE081
;

Figure 971065DEST_PATH_IMAGE049
 7：若
Figure 894022DEST_PATH_IMAGE094
Figure 141463DEST_PATH_IMAGE088
Figure 149871DEST_PATH_IMAGE111
，则
Figure 138031DEST_PATH_IMAGE083
，
Figure 915494DEST_PATH_IMAGE111
=
Figure 333837DEST_PATH_IMAGE081
，转
Figure 563961DEST_PATH_IMAGE049
 6。若
Figure 358742DEST_PATH_IMAGE081
Figure 990711DEST_PATH_IMAGE092
Figure 579956DEST_PATH_IMAGE109
，则转 8；
Figure 971065DEST_PATH_IMAGE049
7: if
Figure 894022DEST_PATH_IMAGE094
Figure 141463DEST_PATH_IMAGE088
Figure 149871DEST_PATH_IMAGE111
,but
Figure 138031DEST_PATH_IMAGE083
,
Figure 915494DEST_PATH_IMAGE111
=
Figure 333837DEST_PATH_IMAGE081
,change
Figure 563961DEST_PATH_IMAGE049
6. like
Figure 358742DEST_PATH_IMAGE081
Figure 990711DEST_PATH_IMAGE092
Figure 579956DEST_PATH_IMAGE109
, then turn 8;

 8：输出O2的所有顶点距离O1的最小值

Figure 396972DEST_PATH_IMAGE109
。 8: Output the minimum value of all vertices ofO2 fromO1
Figure 396972DEST_PATH_IMAGE109
.

多边形O1和O2之间的距离=

Figure DEST_PATH_IMAGE119
，当小于或等于预先设定的阈值时就将O1和O2合成一个多边形。Distance between polygonsO1 andO2 =
Figure DEST_PATH_IMAGE119
,when When it is less than or equal to the preset threshold,O1 andO2 are combined into one polygon.

以上计算多边形之间距离的过程中需要求解点到多边形的距离，本具体实施方式中采用以下方法：如图3(a)，O1：

Figure 2010105527412100002DEST_PATH_IMAGE122
＝是平面Oxy内一个多边形，Q为该平面内任一点。以Q点为原点，以O1Q连线为横坐标轴，建立相对坐标系O'x'y'；在该坐标系下
Figure DEST_PATH_IMAGE125
＝(
Figure 2010105527412100002DEST_PATH_IMAGE126
)(
Figure 121586DEST_PATH_IMAGE039
)，Q=(0,0)，O1=(l12,0)，l12=
Figure 2010105527412100002DEST_PATH_IMAGE128
，Q到O1的最近距离L可计算如下：In the above process of calculating the distance between polygons, it is necessary to solve the distance from the point to the polygon. In this specific embodiment, the following method is adopted: as shown in Figure 3 (a),O1 :
Figure 2010105527412100002DEST_PATH_IMAGE122
= is a polygon in the planeOxy ,and Q is any point in the plane. Takethe Q point as the origin, and take the lineO1Q as the abscissa axis to establish a relative coordinate systemO 'x 'y '; under this coordinate system
Figure DEST_PATH_IMAGE125
=(
Figure 2010105527412100002DEST_PATH_IMAGE126
)(
Figure 121586DEST_PATH_IMAGE039
),Q =(0,0),O1 =(l12 ,0),l12 =
Figure 2010105527412100002DEST_PATH_IMAGE128
, the shortest distanceL fromQ toO1 can be calculated as follows:

Figure 728148DEST_PATH_IMAGE049
 1：比较
Figure 924774DEST_PATH_IMAGE125
的横坐标，得到顶点
Figure DEST_PATH_IMAGE129
，且
Figure DEST_PATH_IMAGE131
；
Figure 728148DEST_PATH_IMAGE049
1: Compare
Figure 924774DEST_PATH_IMAGE125
The abscissa of the vertex
Figure DEST_PATH_IMAGE129
,and
Figure DEST_PATH_IMAGE131
;

Figure 226574DEST_PATH_IMAGE049
 2：令
Figure DEST_PATH_IMAGE133
，计算点Q与线段
Figure DEST_PATH_IMAGE135
的距离
Figure 107461DEST_PATH_IMAGE064
，点Q与线段
Figure DEST_PATH_IMAGE137
的距离
Figure 506212DEST_PATH_IMAGE066
；
Figure 226574DEST_PATH_IMAGE049
2: order
Figure DEST_PATH_IMAGE133
, calculate pointQ and line segment
Figure DEST_PATH_IMAGE135
distance
Figure 107461DEST_PATH_IMAGE064
, pointQ and line segment
Figure DEST_PATH_IMAGE137
distance
Figure 506212DEST_PATH_IMAGE066
;

Figure 608160DEST_PATH_IMAGE049
 3：若
Figure 849786DEST_PATH_IMAGE086
Figure 643747DEST_PATH_IMAGE085
，则
Figure 182175DEST_PATH_IMAGE075
，
Figure DEST_PATH_IMAGE139
=
Figure 517954DEST_PATH_IMAGE073
，转
Figure 800031DEST_PATH_IMAGE049
 4；若
Figure 235691DEST_PATH_IMAGE064
Figure DEST_PATH_IMAGE141
Figure 617125DEST_PATH_IMAGE142
，则，
Figure DEST_PATH_IMAGE143
=
Figure DEST_PATH_IMAGE145
，转 6；
Figure 608160DEST_PATH_IMAGE049
3: if
Figure 849786DEST_PATH_IMAGE086
Figure 643747DEST_PATH_IMAGE085
,but
Figure 182175DEST_PATH_IMAGE075
,
Figure DEST_PATH_IMAGE139
=
Figure 517954DEST_PATH_IMAGE073
,change
Figure 800031DEST_PATH_IMAGE049
4; if
Figure 235691DEST_PATH_IMAGE064
Figure DEST_PATH_IMAGE141
Figure 617125DEST_PATH_IMAGE142
,but ,
Figure DEST_PATH_IMAGE143
=
Figure DEST_PATH_IMAGE145
,change 6;

Figure 747959DEST_PATH_IMAGE049
 4：计算点Q与线段
Figure 362611DEST_PATH_IMAGE135
的距离
Figure 738229DEST_PATH_IMAGE064
；
Figure 747959DEST_PATH_IMAGE049
4: Calculate pointQ and line segment
Figure 362611DEST_PATH_IMAGE135
distance
Figure 738229DEST_PATH_IMAGE064
;

Figure 362108DEST_PATH_IMAGE049
 5：若
Figure 620231DEST_PATH_IMAGE088
Figure 483145DEST_PATH_IMAGE117
，则
Figure 642206DEST_PATH_IMAGE075
，
Figure 906965DEST_PATH_IMAGE139
=
Figure 66682DEST_PATH_IMAGE073
，转
Figure 88996DEST_PATH_IMAGE049
 5。若
Figure 992361DEST_PATH_IMAGE064
Figure 114557DEST_PATH_IMAGE092
Figure 507492DEST_PATH_IMAGE120
，则转
Figure 344998DEST_PATH_IMAGE049
 8；
Figure 362108DEST_PATH_IMAGE049
5: if
Figure 620231DEST_PATH_IMAGE088
Figure 483145DEST_PATH_IMAGE117
,but
Figure 642206DEST_PATH_IMAGE075
,
Figure 906965DEST_PATH_IMAGE139
=
Figure 66682DEST_PATH_IMAGE073
,change
Figure 88996DEST_PATH_IMAGE049
5. like
Figure 992361DEST_PATH_IMAGE064
Figure 114557DEST_PATH_IMAGE092
Figure 507492DEST_PATH_IMAGE120
, then turn
Figure 344998DEST_PATH_IMAGE049
8;

 6：计算点Q与线段

Figure DEST_PATH_IMAGE147
的距离
Figure 697930DEST_PATH_IMAGE142
； 6: Calculate pointQ and line segment
Figure DEST_PATH_IMAGE147
distance
Figure 697930DEST_PATH_IMAGE142
;

Figure 324083DEST_PATH_IMAGE049
 7：若
Figure 318060DEST_PATH_IMAGE085
Figure 625544DEST_PATH_IMAGE088
Figure 719402DEST_PATH_IMAGE117
，则，
Figure 264575DEST_PATH_IMAGE139
=
Figure 110171DEST_PATH_IMAGE142
，转 5。若
Figure 873356DEST_PATH_IMAGE092
Figure 522643DEST_PATH_IMAGE120
，则转
Figure 653410DEST_PATH_IMAGE049
 8；
Figure 324083DEST_PATH_IMAGE049
7: if
Figure 318060DEST_PATH_IMAGE085
Figure 625544DEST_PATH_IMAGE088
Figure 719402DEST_PATH_IMAGE117
,but ,
Figure 264575DEST_PATH_IMAGE139
=
Figure 110171DEST_PATH_IMAGE142
,change 5. like
Figure 873356DEST_PATH_IMAGE092
Figure 522643DEST_PATH_IMAGE120
, then turn
Figure 653410DEST_PATH_IMAGE049
8;

Figure 732880DEST_PATH_IMAGE049
 8：输出点Q与多边形O1的距离
Figure 988412DEST_PATH_IMAGE120
。
Figure 732880DEST_PATH_IMAGE049
8: Output the distance between pointQ and polygonO1
Figure 988412DEST_PATH_IMAGE120
.

以上计算多边形之间距离的过程中需要求解点到直线段的最近距离，本具体实施方式中采用以下方法：如图3(b)，P1P2为一位于平面Oxy内的直线段，Q为该平面内任一点。以该线段的任一端点为原点(图中选择的是P1点)，以线段所在直线为横坐标轴，建立相对坐标系O'x'y'，显然，P1点和O’点重合。设Q点在O'x'y'下的坐标值为(x1，y1)，P1点在O'x'y'下的坐标值为(x2，0)，则Q到P1P2的最近距离L可计算如下：In the above process of calculating the distance between polygons, it is necessary to solve the shortest distance from the point to the straight line segment. In this specific embodiment, the following method is adopted: as shown in Figure 3 (b),P1P2 is a straight line segment located in the planeOxy ,Q for any point in this plane. Take any endpoint of the line segment as the origin (pointP1 is selected in the figure), and take the straight line where the line segment is located as the abscissa axis to establish a relative coordinate systemO 'x 'y '. Obviously, pointP1 and pointO ' coincide . Assumethat the coordinate value of pointQ underO'x'y' is (x1 ,y1 ), and the coordinate value of pointP1 underO'x'y ' is (x2, 0) , thenQ toP1 The shortest distanceL ofP2 can becalculated as follows:

(1) 当

Figure DEST_PATH_IMAGE149
 < 0时，
Figure DEST_PATH_IMAGE151
；(1) when
Figure DEST_PATH_IMAGE149
< 0,
Figure DEST_PATH_IMAGE151
;

(2) 当

Figure 379074DEST_PATH_IMAGE149
>
Figure DEST_PATH_IMAGE153
时，
Figure DEST_PATH_IMAGE155
；(2) when
Figure 379074DEST_PATH_IMAGE149
>
Figure DEST_PATH_IMAGE153
hour,
Figure DEST_PATH_IMAGE155
;

(3) 当时，

Figure DEST_PATH_IMAGE159
。(3) when hour,
Figure DEST_PATH_IMAGE159
.

计算O1的所有顶点距离O2的最小值以及点与多边形O2的距离时，都是从最有可能产生最小距离的顶点开始，然后往两边扩展，直到遇到距离大于该点的情况，此时的最小距离就是所要求的值。When calculating the minimum value of all vertices ofO1 fromO2 and the distance between the point and the polygonO2 , it starts from the vertex most likely to produce the minimum distance, and then expands to both sides until the distance is greater than the point. The minimum distance at this time is the required value.

将两个凸多边形融合处理为一个新的凸多边形，具体按照以下方法：Merge two convex polygons into a new convex polygon, specifically as follows:

 1：如图2所示建立的坐标系中，寻找两个多边形中纵坐标绝对值最大的4个顶点，将这4个顶点作为一级融合点，见图4(a)中的K1、K2、 K3和K4； 1: In the coordinate system established as shown in Figure 2, find the 4 vertices with the largest absolute value of the ordinate in the two polygons, and use these 4 vertices as the first-level fusion points, seeK1 , in Figure 4(a)K2,K3andK4;

Figure 234958DEST_PATH_IMAGE049
 2：运用直线与多边形相交算法，对直线K1K2和多边形O1进行计算，判断二者是否相交(K1点除外)，若相交，求出二级融合点来代替K1点；
Figure 234958DEST_PATH_IMAGE049
2: Use the straight line and polygon intersection algorithm to calculate the straight lineK1K2 and the polygonO1 , and judge whether the two intersect (exceptK1 point), if they intersect, find the secondary fusion point to replaceK1 point;

Figure 977786DEST_PATH_IMAGE049
 3：对直线K1K2和多边形O2重复 2操作；
Figure 977786DEST_PATH_IMAGE049
3: Repeat for lineK1K2 andpolygonO2 2 operation;

Figure 746339DEST_PATH_IMAGE049
 4：对直线K1K2、多边形O1和多边形O2重复
Figure 164682DEST_PATH_IMAGE049
 2和
Figure 660385DEST_PATH_IMAGE049
 3，直到K1K2与O1和O2不再相交为止；
Figure 746339DEST_PATH_IMAGE049
4: Repeat for lineK1K2 , polygonO1 andpolygonO2
Figure 164682DEST_PATH_IMAGE049
2 and
Figure 660385DEST_PATH_IMAGE049
3, untilK1K2 no longer intersects withO1 andO2 ;

 5：对直线K3K4、多边形O1和多边形O2重复

Figure 16030DEST_PATH_IMAGE049
 2、
Figure 605274DEST_PATH_IMAGE049
 3和
Figure 322694DEST_PATH_IMAGE049
 4； 5: Repeat for lineK3K4 , polygonO1 andpolygonO2
Figure 16030DEST_PATH_IMAGE049
2,
Figure 605274DEST_PATH_IMAGE049
3 and
Figure 322694DEST_PATH_IMAGE049
4;

 SHAPE  \* MERGEFORMAT  6：按图形的顺时针方向，设定多边形的融合起点和融合终点，保留两点之间的顶点，合成为一个新多边形，并且删除原有多边形。在图4(a)中，多边形O1的融合起点为K4，融合终点是K1，则按照顺时针方向，保留从K4到K1的O1的顶点；多边形O2的融合起点为K，融合终点是K3，同样按照顺时针方向，保留从K到K3的O2的顶点。按照顺时针方向将保留的O1和O2的顶点连接起来，得到了新的多边形O，如图4 (b)所示。SHAPE \* MERGEFORMAT 6: According to the clockwise direction of the graph, set the fusion start point and fusion end point of the polygon, keep the vertices between the two points, synthesize a new polygon, and delete the original polygon. In Fig. 4(a), the fusion starting point of polygonO1 isK4 , and the fusion end point isK1 , then keep the vertices ofO1 fromK4 toK1 in a clockwise direction; the fusion starting point of polygonO2 isK , the end point of the fusion isK3 , also keep the vertex ofO2 fromK toK3 in the clockwise direction. Connect the retained vertices ofO1 andO2 in a clockwise direction to obtain a new polygonO , as shown in Figure 4 (b).

在上述求解融合点的计算步骤中，需要进行直线、射线、线段与多边形相交的判断，相应的判断方法如下：In the above calculation steps for solving fusion points, it is necessary to judge the intersection of straight lines, rays, line segments and polygons, and the corresponding judgment methods are as follows:

(1) 直线与多边形相交判断算法：在相对坐标系中，如果多边形的各顶点A、B、C、D、E、F的纵坐标值都是同号，即都是正值或都是负值，则直线与该多边形不相交；如果存在异号情况，则相交。(1) Algorithm for judging the intersection of a straight line and a polygon: In the relative coordinate system, if the ordinate values of the vertices A, B, C, D, E, and F of the polygon are all of the same sign, that is, they are all positive or negative value, the line does not intersect the polygon; if there is a case of different signs, it intersects.

(2) 射线与多边形相交判断算法：如图5所示，P1P2为一条位于平面Oxy内的射线，P1为端点，建立如图中所示的相对坐标系O'x'y'，Z1、Z2为该平面内一多边形的两个位于横坐标轴两侧的点，Z3为Z1Z2与横轴的交点，Z3的横坐标值为x3。并且，P1点不在该多边形内，则该多边形与射线P1P2的位置关系可判断如下：(2) Judgment algorithm for the intersection of rays and polygons: as shown in Figure 5,P1P2 is a ray located in the planeOxy ,P1 is the endpoint, and establish the relative coordinate systemO 'x 'y ' as shown in the figure ,Z1 ,Z2 are two points of a polygon in the plane located on both sides of the abscissa axis,Z3 is the intersection point ofZ1Z2 and the abscissa axis, and the abscissa value ofZ3 isx3 . And, pointP1 is not within the polygon, then the positional relationship between the polygon and the rayP1P2 can be judged as follows:

 = 1 \* GB3 ① 当

Figure DEST_PATH_IMAGE161
时，两者不相交；= 1 \*GB3 ① When
Figure DEST_PATH_IMAGE161
, the two do not intersect;

 = 2 \* GB3 ② 当

Figure DEST_PATH_IMAGE163
时，两者相交。= 2 \*GB3 ② when
Figure DEST_PATH_IMAGE163
, the two intersect.

(3) 线段与多边形相交判断算法：分别以线段的两个端点为起点，按照线段的方向建立两条射线，然后对这两条射线与多边形进行相交判断，与这两条射线都相交的多边形与该线段相交。(3) Algorithm for judging the intersection of a line segment and a polygon: take the two endpoints of the line segment as the starting point respectively, establish two rays according to the direction of the line segment, and then judge the intersection of these two rays with the polygon, and the polygon that intersects the two rays intersects the line segment.

附图6显示了这个融合实例的结果，整个融合过程一共进行了12步，这里仅显示了其中4个步骤的结果。融合后，原来的障碍物用浅颜色线条的多边形来表示，说明该障碍物已经不存在了，其外围的深颜色多边形表示融合后的障碍物。融合结束后，障碍物之间的距离都大于5，障碍物的数量变成了12个。Figure 6 shows the results of this fusion example. The entire fusion process has a total of 12 steps, of which only the results of 4 steps are shown here. After fusion, the original obstacle is represented by a polygon with light-colored lines, indicating that the obstacle no longer exists, and the dark-colored polygon around it represents the fused obstacle. After the fusion is over, the distance between obstacles is greater than 5, and the number of obstacles becomes 12.

将融合结束后的结果作为仿真系统中路径规划的初始状态，此时即可采用现有的各种基于矢量法的方法进行路径规划。The result after fusion is used as the initial state of path planning in the simulation system, and various existing vector-based methods can be used for path planning at this time.

为了验证本发明的预处理方法的效果，采用以下方法进行进行验证：经过本发明进行预处理之后的仿真环境采用遗传算法进行路径规划，并和常用的A*算法进行比较。针对图7所示的仿真环境进行路径规划比较。图7显示了本发明和A*算法进行路径规划的结果比较，其中

Figure 217761DEST_PATH_IMAGE164
的值代表不同尺寸的移动主体。可以看出本发明所得的规划路径与A*算法所得的路径大致是相同的。In order to verify the effect of the preprocessing method of the present invention, the following method is used for verification: the simulation environment after the preprocessing of the present invention uses a genetic algorithm for path planning, and compares it with the commonly used A* algorithm. The path planning comparison is carried out for the simulation environment shown in Fig. 7 . Fig. 7 has shown the result comparison that the present invention and A* algorithm carry out path planning, wherein
Figure 217761DEST_PATH_IMAGE164
The values of represent different sizes of moving subjects. It can be seen that the planned path obtained by the present invention is roughly the same as the path obtained by the A* algorithm.

图8显示了本发明和A*算法在路径规划时间上的比较。其中，

Figure 977907DEST_PATH_IMAGE166
是规划空间生成的时间，对于A*算法就是规划空间的栅格化过程，对于本发明就是对障碍物进行融合预处理所花费的时间。
Figure 182623DEST_PATH_IMAGE168
是算法搜索路径的时间，
Figure 319207DEST_PATH_IMAGE170
是最终生成的路径长度。
Figure 988085DEST_PATH_IMAGE166
和
Figure DEST_PATH_IMAGE171
的单位是秒。根据图8所示的实验结果，可以得到以下结论：Fig. 8 shows the comparison between the present invention and the A* algorithm in path planning time. in,
Figure 977907DEST_PATH_IMAGE166
is the time for generating the planning space, for the A* algorithm it is the rasterization process of the planning space, and for the present invention it is the time spent for fusion preprocessing of obstacles.
Figure 182623DEST_PATH_IMAGE168
is the time for the algorithm to search the path,
Figure 319207DEST_PATH_IMAGE170
is the resulting path length.
Figure 988085DEST_PATH_IMAGE166
and
Figure DEST_PATH_IMAGE171
The unit is second. According to the experimental results shown in Figure 8, the following conclusions can be drawn:

(1) 当移动主体外形尺寸较小时，规划空间中的栅格数量较多，空间栅格化以及A*算法搜索过程花费时间都较长。而本发明算法此时没有需要融合的障碍物，也就不用运行GA算法，因此路径搜索过程非常快，特别是当＝2时的路径搜索时间甚至不到1毫秒，说明了该算法的规划速度较快；(1) When the size of the moving body is small, the number of grids in the planning space is large, and the space rasterization and A* algorithm search process take a long time. And the algorithm of the present invention does not need the obstacle of fusion at this moment, just needn't run GA algorithm, so path search process is very fast, especially when =2, the path search time is even less than 1 millisecond, which shows that the planning speed of this algorithm is relatively fast;

(2) 当移动主体外形尺寸逐渐变大时，规划空间中的栅格数量随之减少，空间栅格化以及A*算法搜索过程花费时间都相应得迅速减少。而本发明算法中由于出现了需要融合的障碍物，搜索时间增加，导致本发明算法的路径搜索过程所花费时间(

Figure DEST_PATH_IMAGE175
)也随之增加；(2) When the size of the moving body gradually increases, the number of grids in the planning space decreases, and the time spent on spatial rasterization and A* algorithm search decreases rapidly accordingly. However, in the algorithm of the present invention, due to the occurrence of obstacles that need to be fused, the search time increases, resulting in the time spent in the path search process of the algorithm of the present invention (
Figure DEST_PATH_IMAGE175
) also increases accordingly;

(3) 随着移动主体外形尺寸的增加，两种算法规划得到的路径长度都在增加，但是本发明算法得到的路径长度绝大多数都比A*算法的小。(3) With the increase of the external dimensions of the moving body, the path lengths obtained by the two algorithms are all increasing, but most of the path lengths obtained by the algorithm of the present invention are smaller than those obtained by the A* algorithm.

Claims (6)

Translated fromChinese
1.一种基于矢量法的路径规划预处理方法，用于矢量法表示的仿真系统路径规划，其特征在于，包括以下步骤：1. a path planning preprocessing method based on vector method, for the simulation system path planning of vector method representation, it is characterized in that, comprises the following steps:步骤A、将仿真环境中的每个障碍物均模型化为凸多边形；Step A, modeling each obstacle in the simulation environment as a convex polygon;步骤B、将步骤A中得到的凸多边形中距离小于预先设定的阈值的任意两个凸多边形融合处理为一个新的凸多边形，并依次迭代处理，直到最终得到的凸多边形中任意两个的距离均大于上述预先设定的阈值；其中，所述预先设定的阈值等于路径规划中最大移动主体的尺寸；Step B, merging any two convex polygons whose distance is smaller than a preset threshold in the convex polygon obtained in step A into a new convex polygon, and iteratively processing in turn until any two of the convex polygons finally obtained The distances are all greater than the aforementioned preset threshold; wherein, the preset threshold is equal to the size of the largest moving subject in path planning;步骤C、将步骤B得到的结果作为仿真系统中路径规划的初始状态。Step C, using the result obtained in step B as the initial state of path planning in the simulation system.2.如权利要求1所述基于矢量法的路径规划预处理方法，其特征在于，步骤A中所述将障碍物模型化为凸多边形是在欧式平面中实现。2. The path planning preprocessing method based on vector method as claimed in claim 1, characterized in that, modeling obstacles as convex polygons in step A is realized in the Euclidean plane.3.如权利要求1所述基于矢量法的路径规划预处理方法，其特征在于，步骤B中所述凸多边形之间的距离采用最小间距判断法计算。3. The path planning preprocessing method based on the vector method according to claim 1, wherein the distance between the convex polygons in step B is calculated by a minimum distance judgment method.4.如权利要求1所述基于矢量法的路径规划预处理方法，其特征在于，所述步骤B具体包括以下各步骤：4. the path planning preprocessing method based on vector method as claimed in claim 1, is characterized in that, described step B specifically comprises the following steps:步骤B1、设置变量                                                的初始值为步骤A得到的凸多边形的数量；Step B1, set variables The initial value of is the number of convex polygons obtained in step A;步骤B2、设置变量
Figure 758366DEST_PATH_IMAGE002
、
Figure 465027DEST_PATH_IMAGE004
的值为：
Figure 405301DEST_PATH_IMAGE006
，；Step B2, set variables
Figure 758366DEST_PATH_IMAGE002
,
Figure 465027DEST_PATH_IMAGE004
The value is:
Figure 405301DEST_PATH_IMAGE006
, ;步骤B3、计算第
Figure 968317DEST_PATH_IMAGE004
个凸多边形与第
Figure 147626DEST_PATH_IMAGE010
个凸多边形的距离并判断该距离是否大于一个预先设定的阈值，如是，则转步骤B5；如否，则转步骤B4；Step B3, calculate the first
Figure 968317DEST_PATH_IMAGE004
convex polygon and the
Figure 147626DEST_PATH_IMAGE010
convex polygon and judge whether the distance is greater than a preset threshold, if so, then go to step B5; if not, then go to step B4;步骤B4、将第
Figure 688329DEST_PATH_IMAGE004
个凸多边形与第
Figure 2010105527412100001DEST_PATH_IMAGE011
个凸多边形融合为一个新的凸多边形并删除原第个与第
Figure 480015DEST_PATH_IMAGE012
个凸多边形，将
Figure 878111DEST_PATH_IMAGE014
的值修改为
Figure 160188DEST_PATH_IMAGE016
后转步骤B2；Step B4, the first
Figure 688329DEST_PATH_IMAGE004
convex polygon and the
Figure 2010105527412100001DEST_PATH_IMAGE011
Convex polygons are merged into a new convex polygon and the original one is deleted and the first
Figure 480015DEST_PATH_IMAGE012
a convex polygon, the
Figure 878111DEST_PATH_IMAGE014
The value of is changed to
Figure 160188DEST_PATH_IMAGE016
Turn to step B2;步骤B5、判断是否
Figure 330269DEST_PATH_IMAGE018
，如是，则转步骤B6；如否，则将
Figure 39599DEST_PATH_IMAGE020
的值修改为
Figure 990238DEST_PATH_IMAGE012
后转步骤B3；Step B5, determine whether
Figure 330269DEST_PATH_IMAGE018
, if yes, go to step B6; if no, then
Figure 39599DEST_PATH_IMAGE020
The value of is changed to
Figure 990238DEST_PATH_IMAGE012
Turn to step B3;步骤B6、判断是否
Figure 2010105527412100001DEST_PATH_IMAGE022
，如是，则结束；如否，则将
Figure 748109DEST_PATH_IMAGE020
的值修改为
Figure 38276DEST_PATH_IMAGE023
并将
Figure 918508DEST_PATH_IMAGE023
的值修改为
Figure 2010105527412100001DEST_PATH_IMAGE025
并后转步骤B3。Step B6, determine whether
Figure 2010105527412100001DEST_PATH_IMAGE022
, if yes, end; if no, then
Figure 748109DEST_PATH_IMAGE020
The value of is changed to
Figure 38276DEST_PATH_IMAGE023
and will
Figure 918508DEST_PATH_IMAGE023
The value of is changed to
Figure 2010105527412100001DEST_PATH_IMAGE025
And turn to step B3.5.如权利要求1至4中任一项所述基于矢量法的路径规划预处理方法，其特征在于，5. the path planning preprocessing method based on vector method according to any one of claims 1 to 4, it is characterized in that,所述两个凸多边形融合为一个新的凸多边形具体按照以下方法:The two convex polygons are fused into a new convex polygon according to the following methods:以其中一个多边形的中心为原点，该多边形的两个顶点的连线为纵轴，两个多边形的中心连线为横轴，建立相对坐标系；在该相对坐标系中，在两个多边形中寻找进行纵坐标绝对值最大的4个顶点作为一级融合点；如果一级融合点的连线与多边形相交，则在一级融合点集合中寻找二级融合点，使之连线与多边形不相交，同时删除该二级融合点取代的一级融合点；将现有融合点连在一起合成一个凸多边形，完成两个多边形的融合；所述连线包括直线、射线、线段。Taking the center of one of the polygons as the origin, the line connecting the two vertices of the polygon as the vertical axis, and the line connecting the centers of the two polygons as the horizontal axis, establish a relative coordinate system; in this relative coordinate system, in the two polygons Find the 4 vertices with the largest absolute value of the ordinate as the first-level fusion point; if the connection line of the first-level fusion point intersects the polygon, then find the second-level fusion point in the first-level fusion point set so that the connection line and the polygon do not Intersect, and delete the first-level fusion point replaced by the second-level fusion point; connect the existing fusion points together to form a convex polygon, and complete the fusion of two polygons; the connection includes straight lines, rays, and line segments.6.如权利要求5所述基于矢量法的路径规划预处理方法，其特征在于，进行直线、射线、线段与凸多边形相交的判断时分别采用以下判断方法：6. as claimed in claim 5 based on the path planning preprocessing method of vector method, it is characterized in that, when carrying out straight line, ray, line segment and the judgment that convex polygon intersects, adopt following judging method respectively:直线与多边形相交判断方法：在相对坐标系中，如果多边形的各顶点的纵坐标值都是同号，则直线与该多边形不相交；如果存在异号情况，则相交；Judgment method for the intersection of a straight line and a polygon: In the relative coordinate system, if the ordinate values of each vertex of the polygon are of the same sign, the straight line does not intersect the polygon; if there is a case of different signs, then the intersection;射线与多边形相交判断方法：以该射线的顶点作为原点，以该射线作为横轴，建立相对坐标系，多边形的边与相对坐标系的交点的横坐标，如果小于0，则该多边形与射线不相交；如果大于0，该多边形与射线相交；Judgment method of intersection between ray and polygon: take the vertex of the ray as the origin and the ray as the horizontal axis to establish a relative coordinate system. intersection; if greater than 0, the polygon intersects the ray;线段与多边形相交判断方法：分别以线段的两个端点为起点，按照线段的方向建立两条射线，然后对这两条射线与多边形进行相交判断，与这两条射线都相交的多边形与该线段相交。The method of judging the intersection of a line segment and a polygon: take the two endpoints of the line segment as the starting point, establish two rays according to the direction of the line segment, and then judge the intersection of these two rays with the polygon, and the polygon that intersects with the two rays and the line segment intersect.
CN 2010105527412010-11-222010-11-22Path planning pretreatment method based on vector methodPendingCN101996516A (en)

Priority Applications (1)

Application NumberPriority DateFiling DateTitle
CN 201010552741CN101996516A (en)2010-11-222010-11-22Path planning pretreatment method based on vector method

Applications Claiming Priority (1)

Application NumberPriority DateFiling DateTitle
CN 201010552741CN101996516A (en)2010-11-222010-11-22Path planning pretreatment method based on vector method

Publications (1)

Publication NumberPublication Date
CN101996516Atrue CN101996516A (en)2011-03-30

Family

ID=43786611

Family Applications (1)

Application NumberTitlePriority DateFiling Date
CN 201010552741PendingCN101996516A (en)2010-11-222010-11-22Path planning pretreatment method based on vector method

Country Status (1)

CountryLink
CN (1)CN101996516A (en)

Cited By (9)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN102854880A (en)*2012-10-082013-01-02中国矿业大学Robot whole-situation path planning method facing uncertain environment of mixed terrain and region
CN104933228B (en)*2015-05-272018-03-02西安交通大学Unmanned vehicle real-time track planing method based on Speed Obstacles
CN109634284A (en)*2019-01-152019-04-16安徽工程大学 Path planning method for obstacle avoidance at robot executive end based on nested thirds algorithm
CN110986955A (en)*2019-12-192020-04-10拉扎斯网络科技（上海）有限公司Robot path planning method and device, electronic equipment and storage medium
CN111708369A (en)*2020-07-172020-09-25武汉科技大学 A path planning method for a substation inspection robot
CN114670820A (en)*2020-12-242022-06-28丰田自动车株式会社 Cargo transportation system, cargo transportation method, and storage medium
CN114754777A (en)*2022-04-202022-07-15普达迪泰（天津）智能装备科技有限公司 A full path coverage planning method for unmanned lawn mower based on geographic coordinate system
CN115016472A (en)*2022-06-022022-09-06上海思岚科技有限公司Robot global path planning method and device
CN116329774A (en)*2023-02-242023-06-27百超(深圳)激光科技有限公司Intelligent cutting control system and method for high-speed optical fiber laser cutting machine

Citations (1)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN1617170A (en)*2003-09-192005-05-18索尼株式会社Environment identification device and method, route design device and method and robot

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN1617170A (en)*2003-09-192005-05-18索尼株式会社Environment identification device and method, route design device and method and robot

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
《系统仿真学报》 20060831 孟宪权等 用于虚拟环境中实时避障的凸多边形融合算法 第81-83,87页 1-6 第18卷, 2*

Cited By (13)

* Cited by examiner, † Cited by third party
Publication numberPriority datePublication dateAssigneeTitle
CN102854880A (en)*2012-10-082013-01-02中国矿业大学Robot whole-situation path planning method facing uncertain environment of mixed terrain and region
CN102854880B (en)*2012-10-082014-12-31中国矿业大学Robot whole-situation path planning method facing uncertain environment of mixed terrain and region
CN104933228B (en)*2015-05-272018-03-02西安交通大学Unmanned vehicle real-time track planing method based on Speed Obstacles
CN109634284B (en)*2019-01-152021-07-23安徽工程大学 Path planning method for obstacle avoidance at robot executive end based on nested thirds algorithm
CN109634284A (en)*2019-01-152019-04-16安徽工程大学 Path planning method for obstacle avoidance at robot executive end based on nested thirds algorithm
CN110986955A (en)*2019-12-192020-04-10拉扎斯网络科技（上海）有限公司Robot path planning method and device, electronic equipment and storage medium
CN111708369A (en)*2020-07-172020-09-25武汉科技大学 A path planning method for a substation inspection robot
CN111708369B (en)*2020-07-172021-07-23武汉科技大学 A path planning method for a substation inspection robot
CN114670820A (en)*2020-12-242022-06-28丰田自动车株式会社 Cargo transportation system, cargo transportation method, and storage medium
CN114754777A (en)*2022-04-202022-07-15普达迪泰（天津）智能装备科技有限公司 A full path coverage planning method for unmanned lawn mower based on geographic coordinate system
CN115016472A (en)*2022-06-022022-09-06上海思岚科技有限公司Robot global path planning method and device
CN116329774A (en)*2023-02-242023-06-27百超(深圳)激光科技有限公司Intelligent cutting control system and method for high-speed optical fiber laser cutting machine
CN116329774B (en)*2023-02-242023-10-20百超(深圳)激光科技有限公司Intelligent cutting control system and method for high-speed optical fiber laser cutting machine

Similar Documents

PublicationPublication DateTitle
CN101996516A (en)Path planning pretreatment method based on vector method
CN109990796B (en)Intelligent vehicle path planning method based on bidirectional extended random tree
CN108520554B (en)Binocular three-dimensional dense mapping method based on ORB-SLAM2
WO2018176596A1 (en)Unmanned bicycle path planning method based on weight-improved particle swarm optimization algorithm
CN105843234B (en)A kind of two-dimentional Route planner that UUV detours to round barrier geometry
CN105333879B (en)Synchronous superposition method
CN107943053A (en)A kind of paths planning method of mobile robot
CN113485360B (en) AGV robot path planning method and system based on improved search algorithm
CN106441303A (en)Path programming method based on A* algorithm capable of searching continuous neighborhoods
CN106643733A (en)Moving body route planning method for relay navigation among multiple navigation stations
CN109974739B (en) Global Navigation System and Navigation Information Generation Method Based on High Precision Map
CN110487286B (en)Robot pose judgment method based on point feature projection and laser point cloud fusion
CN113239072B (en)Terminal equipment positioning method and related equipment thereof
CN117451057B (en) UAV three-dimensional path planning method, equipment and media based on improved A* algorithm
CN113932796B (en)High-precision map lane line generation method and device and electronic equipment
CN113050684A (en)Emergency threat-oriented unmanned aerial vehicle track planning algorithm
CN115981311A (en)Path planning method and system for complex pipeline maintenance robot
CN115390551A (en) A robot path planning method, device, electronic equipment and storage medium
CN114444267A (en)Flight planning flight segment horizontal flight path prediction method
CN114879678A (en)Distance weight-based global path smoothing method for mobile robot
CN115453549B (en)Extraction method of environment right angle point coordinate angle based on two-dimensional laser radar
CN103795417B (en)Trajectory data compression method capable of controlling maximum error
CN104407613B (en)Obstacle avoidance path smooth optimization method
CN105538309B (en)A kind of robot barrier object Dynamic Recognition algorithm of limited sensing capability
CN118466517A (en) A robot path planning method based on visibility graph

Legal Events

DateCodeTitleDescription
C06Publication
PB01Publication
C10Entry into substantive examination
SE01Entry into force of request for substantive examination
C02Deemed withdrawal of patent application after publication (patent law 2001)
WD01Invention patent application deemed withdrawn after publication

Open date:20110330
[8]ページ先頭
©2009-2025 Movatter.jp