CN101685016A - Two-dimensional navigation path planning method based on vector electronic chart - Google Patents
Two-dimensional navigation path planning method based on vector electronic chart Download PDFInfo
- Publication number
- CN101685016A CN101685016A CN200810222938A CN200810222938A CN101685016A CN 101685016 A CN101685016 A CN 101685016A CN 200810222938 A CN200810222938 A CN 200810222938A CN 200810222938 A CN200810222938 A CN 200810222938A CN 101685016 A CN101685016 A CN 101685016A
- Authority
- CN
- China
- Prior art keywords
- flight path
- point
- arrive
- zone
- electronic chart
- 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.)
- Granted
Links
Images
Landscapes
- Navigation (AREA)
Abstract
The invention provides a two-dimensional navigation path planning method based on a vector electronic chart, comprising the following steps: selecting a sea area on the vector electronic chart, determining an unavailable arrival area, a necessary arrival point and a navigation path cost parameter; setting a starting point and an ending point on the selected sea area, storing the coordinate valuesof the starting point, the ending point and the necessary arrival point in a node library according to an arrival sequence; taking out two points from the node library to make connection between the two points, judging whether the obtained connection passes the unavailable arrival area or not, if not, taking the connection to be a candidate navigation path between the two points, if so, finding out points which is intersected with the connection and is not capable of arriving outside area from the selected sea area, repeatedly executing the step after coordinate values of found points are stored in the node library according to the arrival sequence; connecting the candidate navigation path between the two points in the node library to obtain all candidate navigation paths; calculating navigation cost of all candidate navigation path according to the navigation cost parameter; and taking the candidate navigation path with the minimum cost as the final navigation path.
Description
Technical field
The present invention relates to the marine navigation field, particularly based on the two-dimentional path planning method of vector electronic chart.
Background technology
When riding the sea, trajectory planning is the thing that the navigator must do before navigation.Along with the popularization of computer utility scope, the navigator also can realize the planning of flight path now by computing machine on the vector electronic chart.Compare with sea chart made of paper, the vector electronic chart can provide detailed in a large number, reliable, accurate and digitized marine environment geodata, be easy to preservation, renewal and Computer Processing, therefore on accuracy, alternative, all improve a lot in the planning of doing flight path on the vector electronic chart.
In the prior art, have the method for carrying out trajectory planning according to the existing fixedly data of flight path, this method obviously is not suitable for and does not have the fixedly free marine site of flight path, and does not use a large amount of marine environment geodata that the vector electronic chart can provide.And in actual applications, carrying out trajectory planning in free marine site is a kind of comparatively general demand, if realize that by artificial method not only labor intensive but also spended time also are unfavorable for realizing the unmanned in real time of aircraft.Therefore, on the basis of vector electronic chart, provide a kind of path planning method that can design flight path voluntarily that broad application prospect is arranged in actual applications.
Summary of the invention
Adopt the defective of the inefficiency that manual method caused when the objective of the invention is to overcome prior art and in free marine site, doing trajectory planning, thereby a kind of method of doing trajectory planning on the vector electronic chart that has had is provided.
To achieve these goals, the invention provides a kind of two-dimentional path planning method, comprising based on the vector electronic chart:
Step 1), on the vector electronic chart selected marine site, obtain the oceanographic data and the aeronautical data in selected marine site, determine in the selected marine site can not arrive the zone, must the point of arrival and flight path cost parameter; Also to set starting point and terminal point, with described starting point, terminal point and determined must according to the arrival order coordinate figure being kept in the node storehouse by the point of arrival for the flight path that will plan;
Step 2), from described node storehouse, take out two points according to the order of sequence, between described two points, do line, judge whether resulting line can not arrive the zone through described, if do not pass through, then with the candidate flight path of described line, if process, then from selected marine site, find with described line intersects and can not arrive extra-regional point as described point-to-point transmission, then pressing of being found shone and reach order and deposit described node storehouse in, re-execute this step;
Step 3), candidate's flight path of point-to-point transmission in the described node storehouse is coupled together, obtain all the candidate's flight paths between described Origin And Destination;
All candidate's flight paths between step 4), Origin And Destination that step 3) is obtained carry out the flight path cost according to described flight path cost parameter and calculate, with candidate's flight path of cost minimum as the final flight path between starting point and terminal point.
In the technique scheme, in described step 2) in, the described extra-regional point that can not arrive that intersects with described line that finds from selected marine site comprises:
Can not arrive the both sides that the zone is positioned at described line and be divided into two zones described;
In described two zones, find respectively and described line distance point farthest;
The point that found can not be arrived the safe distance that the outer mobile navigator in zone stipulates according to the normal orientation of described line to described, resulting point not be if can not arrive in the regional extent described, then described point be described and described line crossing can not arrive extra-regional point.
In the technique scheme, from selected marine site, find with described line intersect can not arrive at extra-regional some the time also comprise:
When described can not arrive the zone and be exactly before once during 2 lines operations process can not arrive the zone time, seek and current described line distance point farthest with the homonymy of preceding once selected point described can not arrival in the zone;
The point that found can not be arrived the safe distance that the outer mobile navigator in zone stipulates according to the normal orientation of described line to described, resulting point not be if can not arrive in the regional extent described, then described point be described and described line crossing can not arrive extra-regional point.
In the technique scheme, in described step 2) in, described the arrival order pressed that is found deposited coordinate figure in the node storehouse and comprises, when found o'clock identical greater than the arrival order between and these somes the time, these points are carried out mark to form candidate's flight path in different paths.
In the technique scheme, in described step 4), described flight path cost is calculated by the parameter of the parameter of the flight path total length in the described flight path cost parameter, the parameter of the total nodal point number of flight path, minimum flight path segment length, the parameter of the maximum angle of turn of flight path and the weighted value of each parameter and is calculated.
In the technique scheme, the computing formula that described flight path cost is calculated comprises:
Vexpense＝λ
1L+λ
2N+λ
3l+λ
4θ
Wherein, λ
1+ λ
2+ λ
3+ λ
4=1,0≤λ
i≤ 1, i=1,2,3,4, λ
iWeighted value for each parameter;
L is the parameter of expression flight path total length, comprising:
L wherein
iBe the length of every section flight path, L
MaxMaximum flight path total length for navigator's definition;
N is the parameter of the total nodal point number of expression flight path, comprising:
N wherein
lBe total node number of flight path, N
MaxMaximum flight path node number for navigator's definition;
L is the parameter of the minimum flight path segment length of expression, comprising:
L wherein
iBe the minimum flight path segment length of flight path, l
MinMinimum flight path segment length for navigator's definition;
θ is the parameter of the maximum angle of turn of expression flight path, comprising:
α wherein
iAnd α
I+1For forming two flight path vector paragraphs at maximum turning angle, φ is the maximum turning angle of definition.
In the technique scheme, the described zone that can not arrive comprises the zone that is used to represent land and forbidden zone in the described vector electronic chart, also comprises the sea area that the navigator delimit voluntarily.
In the technique scheme, the sea area that described navigator delimit voluntarily comprises by the navigator according to needs of self and the defined zone of data with existing in the described vector electronic chart, perhaps by the zone of navigator according to the latitude and longitude coordinates definition.
In the technique scheme, in described step 2) in, describedly judge that resulting line is whether through described can not arrive the zone time, represent describedly can not arrive the zone with polygon, represent described line with line segment, ask described line whether can not arrive the zone through described by line segment and polygonal crossing calculating.
In the technique scheme, will be used in the described selected marine site to represent that the described polygon that can not arrive the zone represents with binary tree.
The invention has the advantages that:
1, method of the present invention can realize the planning to flight path on the free marine site based on the data that existing vector electronic chart is provided, and has avoided the defective of the inefficiency that manual method caused.
2, method of the present invention can provide a plurality of flight paths, and these flight paths is carried out cost calculate, thereby finds out optimum flight path, helps the selection of navigator to flight path.
3, in the method for the invention, can not arrive the zone and store, accelerate the efficient of entire method with binary tree.
Description of drawings
Below, describe embodiments of the invention in conjunction with the accompanying drawings in detail, wherein:
Fig. 1 is the overview flow chart of path planning method of the present invention;
Fig. 2 is for asking for the particular flow sheet of point-to-point transmission flight path in the path planning method of the present invention;
Fig. 3 is in one embodiment to how realizing the exemplary plot of path planning method of the present invention.
Embodiment
The present invention is described further below in conjunction with the drawings and specific embodiments.
The work that the present invention will finish is at the flight path of needs design that has on the vector electronic chart of oceanographic data and aeronautical data according to the navigator, in the present embodiment, with the vector electronic chart that adopts the S57 standard is example, with reference to figure 1 and Fig. 2, the design process of new flight path is described.
The navigator is the selected marine site relevant with the flight path that will design on the vector electronic chart at first, obtains the oceanographic data and the aeronautical data in selected marine site.Described oceanographic data comprises information such as the depth of water, ocean current, submerged reef in marine site, and described aeronautical data comprises information such as navigation channel division, Warning Mark.According to oceanographic data on the vector electronic chart and navigator's demand, determine to arrive the zone, must the point of arrival and the flight path cost parameter of various factors.For example, the land that defines in S57 (Land area) and forbidden zone (Restricted area) can be defined as automatically and can not arrive the zone, in addition, the navigator can also be about to a certain marine site certainly and be defined as and can not arrive the zone, in definition procedure, can be according to navigator's self needs, according to the data with existing in the electronic chart, as the depth of water, the navigation channel, anchor district etc., definition can not arrive the zone; Also can any definition can not arrive the zone according to latitude and longitude coordinates in electronic chart.Above-mentioned each can not arrive the zone and can represent with polygon on how much.Must the point of arrival be the navigator according to the navigation needs and definite, for example, the supply of materials such as fuel, fresh water is carried out in a certain halfway possibly place in the navigation process, this place will be set at must the point of arrival.And flight path cost parameter comprises length, node number, steering angle of flight path etc., and they can specify its proportion shared when flight path is made a strategic decision by the navigator.Above-mentioned flight path cost parameter majority is the factor appointments such as needs, naval vessel situation and fuel oil according to navigator self, and the navigator is according to its weight of attention degree decision to each parameter, and weight is 0 when not considering, payes attention to more, and weight is more near 1.
The navigator is behind the vector electronic chart that obtains relevant marine site, for the flight path that will design is set starting point and terminal point.When setting starting point and terminal point, should guarantee that starting point and terminal point not can not the arriving in the zone of aforementioned setting, if in this zone, obviously need reset.To starting point and terminal point whether the judgement in can not arriving the zone in fact be exactly the whether judgement in representative can not arrive regional polygon of a point.Have a plurality ofly owing to can not arrive the zone, therefore, need whether in polygon, judge one by one the point of representing beginning or end.Only a bit not in any polygon, think that just beginning or end sets successfully.Generally can directly click realization when the starting point that input will be set on the vector electronic chart and the related data of terminal point,, also can set starting point and terminal point with the GPS locator data in order to guarantee accuracy by respective point at the vector electronic chart.After the starting point and terminal point affirmation that set, starting point and terminal point can be left in the node storehouse, if in aforesaid step, the navigator has also set must the point of arrival, then must also should leave in the node storehouse by the point of arrival, each in the node storehouse pressed to shine and reached order and arrange in order, promptly starting point before, terminal point is last, must the point of arrival according to the arrival order between described starting point and terminal point.
After the starting point and terminal point of setting flight path, the information in conjunction with vector electronic chart and navigator self setting begins concrete flight path design process, understands for convenience, an embodiment is combined with accompanying drawing do specific description below.
In one embodiment, do following supposition: the navigator has set the starting point S and the terminal point E of flight path, in the marine site at starting point S and terminal point E place, have three and can not arrive the zone, represent with R1, R2, R3 that respectively not existing must the point of arrival between Origin And Destination.Below in conjunction with Fig. 3, the flight path that how to design between starting point S and the terminal point E is described.
According to the shortest principle of straight line between 2 o'clock, be starting point S and terminal point E design flight path, what at first consider is exactly as possible candidate's flight path with the line between starting point S and the terminal point E.In Fig. 3 A, the line segment that starting point S and terminal point E are directly linked to each other is exactly possible candidate's flight path I.Possible candidate's flight path only just can become candidate's flight path through after the judgement of feasibility.Described feasibility judgement is meant that mainly this flight path is not through arriving the zone.The possible candidate's flight path that does not have feasibility can be rejected, and need select again.Mention in the description in front, can not arrive the zone and on how much, can represent, therefore, whether can be converted into the problem whether a line segment intersects with polygon through the judgement that can not arrive the zone for possible candidate's flight path with polygon.Owing to can not arrive more than one of zone possibility, therefore, judging that possible candidate's flight path is whether through can not arrive the zone time, the line segment of candidate's flight path that should representative is possible and all representatives can not arrive the polygon in zone and do crossing judgement, have only described line segment and all polygons all non-intersect, think that just possible candidate course line does not have through not arriving the zone.For line segment and the crossing situation of polygon, to know that also line segment is concrete and which polygon is crossing, which promptly possible candidate's flight path passed through can not arrive the zone, with convenient follow-up searching new possible candidate's flight path.In intersecting computation process, to calculate resource requirement in order saving, to raise the efficiency, in a preferred implementation, then stop to calculate the remaining limit of this polygon when finding that line segment and certain polygon intersect, begin to calculate next polygon and whether intersect.In Fig. 3 A, through calculating, candidate's flight path I can be successively through not arriving region R 1, R2, and therefore, possible candidate's flight path I can not be as candidate's flight path, and the flight path that need search other is as candidate's flight path.
The possible candidate's flight path that does not have feasibility has passed through and can not arrive the zone, therefore when seeking new possible candidate's flight path, should avoid last possible candidate's flight path process can not arrive the zone.Still think that starting point S and terminal point E design course line is an example, aforesaid possible candidate's flight path I has successively passed through and can not arrive region R 1, R2, and therefore new flight path should be avoided R1, R2.When avoiding R1, R2, avoid earlier avoiding R2 behind the R1, and avoid avoiding the resulting candidate of R1 course line behind the R2 earlier and can there are differences, be illustrated in conjunction with Fig. 3 A and Fig. 3 B respectively below.
In Fig. 3 A, at first to avoid to arrive region R 1.R1 is divided into two parts by possible candidate's flight path I, the definition directed line segment
The left side be minus zone, the right side is found one respectively apart from flight path I node farthest for just distinguishing in positive and negative district, represents two nodes being found with triangle in Fig. 3 A.Normal orientation from these two summits along flight path I moves fixing safe distance and obtains new flight path node 1 and 2 outside the zone then, and safe distance described herein can be specified by the navigator.Resulting new flight path node should judge whether it can not arrive in the regional extent, if can not arrive in the regional extent, then delete the flight path node that newly obtains, otherwise the flight path node that will newly obtain joins in the node storehouse.In the present embodiment, the flight path node 1 and 2 that newly obtains obviously can not arrive in the zone, and therefore, flight path node 1 and 2 all can join in the node storehouse.Mention in the explanation in front, starting point, terminal point and when can not the point of arrival depositing in the node storehouse should be stored in proper order according to arrival.And when herein flight path node 1,2 being stored, the arrival of two flight path nodes is identical in proper order, therefore, when storing into flight path node 1 and 2 in the node storehouse, should carry out mark to embody above-mentioned feature to these two flight path nodes.When follow-up path computing, can form different paths according to these two flight path nodes.
Calculate path through node in the node storehouse.To be example to path through node 1, can obtain a new possible candidate course line II by starting point S, flight path node 1, terminal point E, in new candidate course line II, comprise the line of starting point S and flight path node 1
, the line of flight path node 1 and terminal point E
Line
Be the flight path of safe and feasible, no longer cut apart, but line
Intersect with region R 3, therefore need avoid R3 once more.Repeat aforesaid process, can produce node 3 and 4, node 3 and node 4 are safe with the line of terminal point E, therefore, and resulting possible candidate's flight path
With
Become candidate's flight path.Similarly, can obtain candidate's flight path by flight path node 2
With
More than be the situation of at first avoiding to arrive region R 1, in Fig. 3 B, provided and at first avoided to arrive region R 2, avoid the situation of R1 then.Similar with the description of front, at first R2 is told positive negative region by possible candidate's flight path I, then by on R2, looking for distance point farthest further to find two nodes 7,8, then with starting point S, node 7, terminal point E, perhaps starting point S, node 8, terminal point E are linked in sequence, and obtain possible candidate's flight path, judge by the feasibility to possible candidate's flight path, whether decision needs further to cut apart, till the candidate's flight path that obtains safe and feasible.In Fig. 3 B, finally can obtain candidate's flight path
(, so being 10 to have added bracket) because 10 and 1,0 can't distinguish in above-mentioned flight path sign and
By aforesaid operations, can obtain 7 candidate's flight paths between starting point S and the terminal point E, but for the navigator, as long as a selection final flight path of conduct wherein.Resulting final flight path should be a flight path the most fast and easily.Select problem in order to solve above-mentioned candidate's flight path, need calculate the navigation cost of flight path.In one embodiment of the invention, provided following flight path cost computing formula:
Vexpense＝λ
1L+λ
2N+λ
3l+λ
4θ
Wherein, λ
1+ λ
2+ λ
3+ λ
4=1,0≤λ
i≤ 1, i=1,2,3,4, λ
iWeighted value for each parameter.
L is the parameter of expression flight path total length, and it is defined as follows:
L wherein
iBe the length of every section flight path, L
MaxMaximum flight path total length for navigator's definition.
N is the parameter of the total nodal point number of expression flight path, and it is defined as follows:
N wherein
lBe total node number of flight path, N
MaxMaximum flight path node number for navigator's definition.
L is the parameter of the minimum flight path segment length of expression, and it is defined as follows:
L wherein
iBe the minimum flight path segment length of flight path, l
MinMinimum flight path segment length for navigator's definition.
θ is the parameter of the maximum angle of turn of expression flight path, and it is defined as follows:
α wherein
iAnd α
I+1For forming two flight path vector paragraphs at maximum turning angle, φ is the maximum turning angle of definition.
λ in above-mentioned each parameter
i, L
Max, N
Max, l
Min, φ can specify according to the factors such as needs, naval vessel situation and fuel oil of self by the navigator, the value that flight path cost computing formula calculates is more little, illustrates that flight path satisfies condition more.
After 7 candidate's flight paths in the present embodiment calculate through above-mentioned formula, just can select the flight path of cost minimum as final flight path according to result of calculation.
It more than is the explanation of the idiographic flow when method of the present invention is realized in one embodiment, when practical application, except the cited situation of the foregoing description, also may have following situation: the area shape very big or should the zone that can not arrive the zone presents a concave polygon, for this kind situation, shown in Fig. 3 (C), when calculating flight path, adopt preceding method to produce node 1 and 3, find when calculating flight path II then that it is still crossing with region R 1, no longer calculate the positive and negative two lateral extent flight paths of flight path point farthest this moment.Consider that node 1 is positioned at the minus side that flight path I is cut apart, the also inevitable minus side in flight path II cut zone of therefore new node so only need look for apart from flight path new node farthest at the flight path minus side, finds node 2 at last, generates candidate's flight path
Make the picture that returns that to avoid flight path like this, can guarantee that flight path can enter the recessed zone of concave polygon simultaneously.
Can see that from the foregoing description a large amount of calculation costs related when method of the present invention realizes on computers are all relevant with polygon.For example, when selecting starting point and terminal point, judge selected starting point and terminal point whether the calculation cost in can not arriving the zone be O (n
1Logn
1+ n
2Logn
2+ ...+n
mLogn
m), wherein m be for can not arrive regional polygonal number, n
i(i=1,2 ..., m) be i polygonal limit number.Whether the worst crossing calculation cost is O (n can not to arrive regional polygon in calculating line segment and representative
1+ n
2+ ...+n
m), n wherein
i(i=1,2 ..., m) be i polygonal limit number.
Consider above-mentioned characteristic, the present invention can also form binary tree with the polygonal region subregion with the method for two-dimensional space subregion binary tree In yet another embodiment, and this process is finished before trajectory planning in advance.By the calculating that whether this method can be simplified a little in polygon and whether line segment intersects with polygon.After adopting the binary tree method, judge that whether starting point and terminal point can be reduced to O (logn at the calculation cost that can not arrive in regional
1+ logn
2+ ...+logn
m), wherein m be for can not arrive regional polygonal number, n
i(i=1,2 ..., m) be i polygonal limit number; Whether the worst crossing calculation cost is reduced to O (P (logn and line segment and representative can not arrive regional polygon
1+ logn
2+ ...+logn
m)).Even add the calculation cost O (n that the structure binary tree will spend
1Logn
1+ n
2Logn
2+ ...+n
mLogn
m), compare with the method that does not adopt binary tree, also can reduce and calculate needed expense.The method of two-dimensional space subregion binary tree is ripe prior art, no longer repeat specification herein.
It should be noted last that above embodiment is only unrestricted in order to technical scheme of the present invention to be described.Although the present invention is had been described in detail with reference to embodiment, those of ordinary skill in the art is to be understood that, technical scheme of the present invention is made amendment or is equal to replacement, do not break away from the spirit and scope of technical solution of the present invention, it all should be encompassed in the middle of the claim scope of the present invention.
Claims (10)
1, a kind of two-dimentional path planning method based on the vector electronic chart comprises:
Step 1), on the vector electronic chart selected marine site, obtain the oceanographic data and the aeronautical data in selected marine site, determine in the selected marine site can not arrive the zone, must the point of arrival and flight path cost parameter; Also to set starting point and terminal point, with described starting point, terminal point and determined must according to the arrival order coordinate figure being kept in the node storehouse by the point of arrival for the flight path that will plan;
Step 2), from described node storehouse, take out two points according to the order of sequence, between described two points, do line, judge whether resulting line can not arrive the zone through described, if do not pass through, then with the candidate flight path of described line, if process, then from selected marine site, find with described line intersects and can not arrive extra-regional point as described point-to-point transmission, deposit the arrival of being found of pressing in the node storehouse in proper order then, re-execute this step;
Step 3), candidate's flight path of point-to-point transmission in the described node storehouse is coupled together, obtain all the candidate's flight paths between described Origin And Destination;
All candidate's flight paths between step 4), Origin And Destination that step 3) is obtained carry out the flight path cost according to described flight path cost parameter and calculate, with candidate's flight path of cost minimum as the final flight path between starting point and terminal point.
2, the two-dimentional path planning method based on the vector electronic chart according to claim 1 is characterized in that, in described step 2) in, the described extra-regional point that can not arrive that intersects with described line that finds from selected marine site comprises:
Can not arrive the both sides that the zone is positioned at described line and be divided into two zones described;
In described two zones, find respectively and described line distance point farthest;
The point that found can not be arrived the safe distance that the outer mobile navigator in zone stipulates according to the normal orientation of described line to described, resulting point not be if can not arrive in the regional extent described, then described point be described and described line crossing can not arrive extra-regional point.
3, the two-dimentional path planning method based on the vector electronic chart according to claim 2 is characterized in that, from selected marine site, find with described line intersect can not arrive at extra-regional some the time also comprise:
When described can not arrive the zone and be exactly before once during 2 lines operations process can not arrive the zone time, seek and current described line distance point farthest with the homonymy of preceding once selected point described can not arrival in the zone;
The point that found can not be arrived the safe distance that the outer mobile navigator in zone stipulates according to the normal orientation of described line to described, resulting point not be if can not arrive in the regional extent described, then described point be described and described line crossing can not arrive extra-regional point.
4, the two-dimentional path planning method based on the vector electronic chart according to claim 1, it is characterized in that, in described step 2) in, described the arrival order pressed that is found is deposited coordinate figure in the node storehouse and comprises, when found o'clock identical greater than the arrival order between one and these some the time, these points are carried out mark to form candidate's flight path in different paths.
5, the two-dimentional path planning method based on the vector electronic chart according to claim 1, it is characterized in that, in described step 4), described flight path cost is calculated by the parameter of the parameter of the flight path total length in the described flight path cost parameter, the parameter of the total nodal point number of flight path, minimum flight path segment length, the parameter of the maximum angle of turn of flight path and the weighted value of each parameter and is calculated.
6, the two-dimentional path planning method based on the vector electronic chart according to claim 5 is characterized in that, the computing formula that described flight path cost is calculated comprises:
Vexpense＝λ
1L+λ
2N+λ
3l+λ
4θ
Wherein, λ
1+ λ
2+ λ
3+ λ
4=1,0≤λ
i≤ 1, i=1,2,3,4, λ
iWeighted value for each parameter;
L is the parameter of expression flight path total length, comprising:
L wherein
iBe the length of every section flight path, L
MaxMaximum flight path total length for navigator's definition;
N is the parameter of the total nodal point number of expression flight path, comprising:
N wherein
1Be total node number of flight path, N
MaxMaximum flight path node number for navigator's definition;
L is the parameter of the minimum flight path segment length of expression, comprising:
L wherein
iBe the minimum flight path segment length of flight path, l
MinMinimum flight path segment length for navigator's definition;
θ is the parameter of the maximum angle of turn of expression flight path, comprising:
α wherein
iAnd α
I+1For forming two flight path vector paragraphs at maximum turning angle, φ is the maximum turning angle of definition.
7, the two-dimentional path planning method based on the vector electronic chart according to claim 1, it is characterized in that, the described zone that can not arrive comprises the zone that is used to represent land and forbidden zone in the described vector electronic chart, also comprises the sea area that the navigator delimit voluntarily.
8, the two-dimentional path planning method based on the vector electronic chart according to claim 7, it is characterized in that, the sea area that described navigator delimit voluntarily comprises by the navigator according to needs of self and the defined zone of data with existing in the described vector electronic chart, perhaps by the zone of navigator according to the latitude and longitude coordinates definition.
9, the two-dimentional path planning method based on the vector electronic chart according to claim 1, it is characterized in that, in described step 2) in, describedly judge that resulting line is whether through described can not arrive the zone time, represent describedly can not arrive the zone with polygon, represent described line with line segment, ask described line whether can not arrive the zone through described by line segment and polygonal crossing calculating.
10, the two-dimentional path planning method based on the vector electronic chart according to claim 9 is characterized in that, will be used in the described selected marine site to represent that the described polygon that can not arrive the zone represents with binary tree.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 200810222938 CN101685016B (en) | 2008-09-23 | 2008-09-23 | Two-dimensional navigation path planning method based on vector electronic chart |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN 200810222938 CN101685016B (en) | 2008-09-23 | 2008-09-23 | Two-dimensional navigation path planning method based on vector electronic chart |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101685016A true CN101685016A (en) | 2010-03-31 |
| CN101685016B CN101685016B (en) | 2013-04-24 |
Family
ID=42048290
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN 200810222938 Expired - Fee Related CN101685016B (en) | 2008-09-23 | 2008-09-23 | Two-dimensional navigation path planning method based on vector electronic chart |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101685016B (en) |
Cited By (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101846524A (en) * | 2010-04-30 | 2010-09-29 | 浙江大学 | Planning method for determining first-aid repair paths |
| CN102496311A (en) * | 2011-12-22 | 2012-06-13 | 北京东进记录科技有限公司 | Warning method and device for minimum safe altitude of aerial target |
| CN103645870A (en) * | 2013-11-19 | 2014-03-19 | 上海广电通信技术有限公司 | Overlapping display system for electronic chart and radar echo |
| CN104020770A (en) * | 2014-06-13 | 2014-09-03 | 哈尔滨工程大学 | UUV space trajectory planning method based on polynomial |
| CN104067092A (en) * | 2012-01-25 | 2014-09-24 | 日本先锋公司 | Image processing apparatus, image processing/managing apparatus, terminal, image processing method, and data structure |
| CN104239635A (en) * | 2014-09-16 | 2014-12-24 | 武汉中原电子集团有限公司 | Method for automatically drawing navigable area central line on inland river electronic chart |
| CN105279069A (en) * | 2015-11-06 | 2016-01-27 | 中国电子科技集团公司第二十八研究所 | Index matrix-based target quick alarm judgment method |
| CN105629989A (en) * | 2015-12-28 | 2016-06-01 | 电子科技大学 | Obstacle region division method based on minimum enclosing circle and maximum inscribed circle |
| CN106582023A (en) * | 2016-12-01 | 2017-04-26 | 北京像素软件科技股份有限公司 | Game path-searching method and apparatus |
| CN107479558A (en) * | 2017-09-22 | 2017-12-15 | 中国人民解放军63983部队 | Vehicle field paths planning method based on vehicle movement model |
| CN107727098A (en) * | 2017-09-26 | 2018-02-23 | 上海大学 | A kind of unmanned water surface ship paths planning method for multiple target locations of patrolling successively |
| CN108764401A (en) * | 2018-05-28 | 2018-11-06 | 孔令根 | It is a kind of to be easy to debate the two-dimensional marker scheme to addressing |
| WO2022220741A1 (en) * | 2021-04-12 | 2022-10-20 | Quantum Inventions Pte Ltd | A method and system for route computation |
-
2008
- 2008-09-23 CN CN 200810222938 patent/CN101685016B/en not_active Expired - Fee Related
Cited By (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101846524B (en) * | 2010-04-30 | 2011-12-21 | 浙江大学 | Planning method for determining first-aid repair paths |
| CN101846524A (en) * | 2010-04-30 | 2010-09-29 | 浙江大学 | Planning method for determining first-aid repair paths |
| CN102496311A (en) * | 2011-12-22 | 2012-06-13 | 北京东进记录科技有限公司 | Warning method and device for minimum safe altitude of aerial target |
| CN102496311B (en) * | 2011-12-22 | 2014-01-15 | 北京东进记录科技有限公司 | Warning method and device for minimum safe altitude of aerial target |
| CN104067092A (en) * | 2012-01-25 | 2014-09-24 | 日本先锋公司 | Image processing apparatus, image processing/managing apparatus, terminal, image processing method, and data structure |
| CN103645870A (en) * | 2013-11-19 | 2014-03-19 | 上海广电通信技术有限公司 | Overlapping display system for electronic chart and radar echo |
| CN104020770B (en) * | 2014-06-13 | 2015-07-22 | 哈尔滨工程大学 | UUV space trajectory planning method based on polynomial |
| CN104020770A (en) * | 2014-06-13 | 2014-09-03 | 哈尔滨工程大学 | UUV space trajectory planning method based on polynomial |
| CN104239635A (en) * | 2014-09-16 | 2014-12-24 | 武汉中原电子集团有限公司 | Method for automatically drawing navigable area central line on inland river electronic chart |
| CN105279069A (en) * | 2015-11-06 | 2016-01-27 | 中国电子科技集团公司第二十八研究所 | Index matrix-based target quick alarm judgment method |
| CN105279069B (en) * | 2015-11-06 | 2017-11-10 | 中国电子科技集团公司第二十八研究所 | A kind of target based on index matrix quickly alerts determination methods |
| CN105629989A (en) * | 2015-12-28 | 2016-06-01 | 电子科技大学 | Obstacle region division method based on minimum enclosing circle and maximum inscribed circle |
| CN105629989B (en) * | 2015-12-28 | 2018-04-17 | 电子科技大学 | Based on the barrier zone division methods to take all of outside minimum with maximum inscribed circle |
| CN106582023A (en) * | 2016-12-01 | 2017-04-26 | 北京像素软件科技股份有限公司 | Game path-searching method and apparatus |
| CN106582023B (en) * | 2016-12-01 | 2020-06-02 | 北京像素软件科技股份有限公司 | Game way finding method and device |
| CN107479558A (en) * | 2017-09-22 | 2017-12-15 | 中国人民解放军63983部队 | Vehicle field paths planning method based on vehicle movement model |
| CN107727098A (en) * | 2017-09-26 | 2018-02-23 | 上海大学 | A kind of unmanned water surface ship paths planning method for multiple target locations of patrolling successively |
| CN108764401A (en) * | 2018-05-28 | 2018-11-06 | 孔令根 | It is a kind of to be easy to debate the two-dimensional marker scheme to addressing |
| WO2022220741A1 (en) * | 2021-04-12 | 2022-10-20 | Quantum Inventions Pte Ltd | A method and system for route computation |
Also Published As
| Publication number | Publication date |
|---|---|
| CN101685016B (en) | 2013-04-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101685016B (en) | Two-dimensional navigation path planning method based on vector electronic chart | |
| Wang et al. | A Three-Dimensional Dijkstra's algorithm for multi-objective ship voyage optimization | |
| CN108680163B (en) | Unmanned ship path searching system and method based on topological map | |
| CN106371445B (en) | A kind of unmanned vehicle planning control method based on topological map | |
| CN110608738B (en) | Unmanned ship global meteorological air route dynamic planning method and system | |
| CN107422736B (en) | Unmanned ship autonomous return control method | |
| WO2020083686A1 (en) | An apparatus for determining an optimal route of a maritime ship | |
| CN103968841B (en) | Improved fireflyalgorithm based AUV (autonomous underwater vehicle) three-dimensional track planning method | |
| Zhao et al. | Route planning for autonomous vessels based on improved artificial fish swarm algorithm | |
| Zhang et al. | Application of improved multi-objective ant colony optimization algorithm in ship weather routing | |
| CN111222701B (en) | Marine environment map layer-based automatic planning and evaluation method for ship route | |
| KR101554498B1 (en) | System for planning optimized vessel seaway using network modeling | |
| Chen et al. | Research on Ship Meteorological Route Based on A‐Star Algorithm | |
| JP2008145312A (en) | Optimum route search method | |
| CN104949679A (en) | Navigation information determination method and navigation information determination device | |
| CN112880678A (en) | Unmanned ship navigation planning method in complex water area environment | |
| CN108225333A (en) | A kind of optimal path generation method for flight course planning | |
| Zhang et al. | AUV path planning based on differential evolution with environment prediction | |
| CN111176281A (en) | Multi-surface unmanned ship coverage type collaborative search method and system based on quadrant method | |
| CN110969289B (en) | Continuous dynamic optimization method and system for unmanned ship meteorological route | |
| Wang et al. | Route planning and tracking for ships based on the ECDIS platform | |
| Lee et al. | Generation of Ship’s passage plan using data-driven shortest path algorithms | |
| CN116430875A (en) | Unmanned ship and unmanned ship collaborative patrol path planning algorithm for marine pasture unmanned plane | |
| Neumann | Method of path selection in the graph-case study | |
| Dalang et al. | Stochastic optimization of sailing trajectories in an upwind regatta |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20130424 Termination date: 20160923 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |