Method, system and memory for constructing transverse topological relationship of lanes in high-definition map

Abstract

A method and system for constructing a transverse topological relationship and a memory are provided. In the method, lane group data in a high-definition map is acquired; for each lane group, a shared boundary line group of two adjacent lanes is sequentially extracted, and the number of parallel boundary line elements is determined; if the number is 1, a transverse topological relationship between the two adjacent lanes is not generated, otherwise the number and types of boundary line units on the parallel boundary line elements are determined; and if the number of the boundary line units is 1, the transverse topological relationship between the two adjacent lanes is generated, otherwise segmentation processing is performed on the lane group along a lane direction, and the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, is sequentially generated.

Claims

1. A method for constructing a transverse topological relationship of lanes in a high-definition map, comprising steps of: acquiring data of lane groups from the high-definition map; for each lane group, sequentially extracting a shared boundary line group of two adjacent lanes and determining the number of parallel boundary line elements in the shared boundary line group; if the number of the parallel boundary line elements is 1, not generating a transverse topological relationship between the two adjacent lanes; if the number of the parallel boundary line elements is not 1, determining the number and types of boundary line units on the parallel boundary line elements; if the number of the boundary line units is 1, generating the transverse topological relationship between the two adjacent lanes according to a type of a shared boundary line; and if the number of the boundary line units is not 1, performing segmentation processing on the lane group along a lane direction according to a point, where switching between a solid line and a dotted line occurs, of the shared boundary line, and sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to a position of the point where switching between the solid line and dotted line occurs and the types of the boundary line units.

2. The method of claim 1, wherein performing segmentation processing on the lane group along the lane direction according to the point where switching between the solid line and dotted line occurs of the shared boundary line comprises: if a previous boundary line unit of the point where switching between the solid line and dotted line occurs of the shared boundary line is B.sub.1, acquiring a distance dis between an ending point A of the boundary line unit B.sub.1 and a starting point S of a shared boundary line L from the lane group data, the distance dis being an accumulated sum of shape point line segments between the point S and the point A; acquiring shape coordinate points of the shared boundary line L, and assuming a set of the vectorized coordinate points of the shared boundary line is {P.sub.1, P.sub.2, P.sub.3 . . . P.sub.n}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1{P.sub.1, P.sub.2}, L.sub.2{P.sub.2, P.sub.3}, L.sub.3{P.sub.3, P.sub.4} . . . line segment L.sub.n−1{P.sub.n−1, P.sub.n} and calculating lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments; calculating a specific line segment, where the ending point A is located, in a line segment set L.sub.1, L.sub.2, L.sub.3, . . . L.sub.n−1 according to the distance dis and the lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments, A being denoted as located on a line segment L.sub.a and a starting point of L.sub.a being denoted as B; calculating a distance between the ending point A and B and calculating a position of the point A on the line segment L.sub.a according to the distance to acquire a coordinate of the point A; forming, by the point A and the point B, a line segment L.sub.AB, drawing a perpendicular line V.sub.A, that passes through the point A, of the line segment L.sub.AB and performing cutting processing on the lane group by use of the perpendicular line V.sub.A; and repeating the steps to cut the lane group into multiple segments along the lane direction according to shared boundary line units.

3. The method of claim 2, after performing cutting processing on the lane group along the lane direction, further comprising: calculating an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.L on the left of the shared boundary line L, and an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.R on the right of the shared boundary line L.

4. The method of claim 3, wherein calculating the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left of the shared boundary line L and the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right of L comprises: acquiring shape coordinate points of the lane centerline C.sub.R on the right of the shared boundary line L, and assuming a set of the vectorized coordinate points of the lane centerline C.sub.R is {P.sub.1′, P.sub.2′, P.sub.3′ . . . P.sub.n′}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1′{P.sub.1′, P.sub.2′}, L.sub.2′{P.sub.2′, P.sub.3′}, L.sub.3′{P.sub.3′, P.sub.4} . . . line segment L.sub.n−1′{P.sub.n−1′, P.sub.n′}; determining whether the perpendicular line V.sub.A is intersected with a line segment set {L.sub.1′, L.sub.2′, L.sub.3′ . . . L.sub.n−1′} or not, and calculating an intersection point, if there is more than one intersection point, extracting the intersection point closest to the point A, the intersection point being denoted as as a point C; and assuming the lane centerline on the left of the shared boundary line L is C.sub.L, repeating the steps to calculate an intersection point D between the perpendicular line V.sub.A and C.sub.L.

5. The method of claim 4, wherein sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to the position of the point where switching between the solid line and dotted line occurs and the types of the boundary line unit comprises: for a point A where switching between a solid line and a dotted line occurs, determining a position of the point where the switching occurs at first; if the point A is the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, a starting point of the lane centerline C.sub.R on the right being denoted as S.sub.R and a starting point of the lane centerline C.sub.L on the left being denoted as S.sub.L, generating topological relationships between the point S.sub.R and the point D and between the point S.sub.L and the point C according to the type of the boundary line unit B.sub.1; if the point A is not the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, generating a topological relationship between an intersection point C.sup.−1 of a perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.R on the right and the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and a topological relationship between an intersection point D.sup.−1 of the perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.L on the left and the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right according to the type of the boundary line unit B.sub.1, V.sub.A.sup.−1 being a perpendicular line passing through a point, where switching between a solid line and a dotted line occurs and which is previous to the point A, and V.sub.A being a perpendicular line passing through the point A; and if the point A is the last point where switching between a solid line and a dotted line occurs on the shared boundary line, a boundary line unit next to the point A being denoted as B.sub.2, a terminal point of the lane centerline C.sub.R on the right being denoted as E.sub.R and the starting point of the lane centerline C.sub.L on the left being denoted as E.sub.L, generating a topological relationship between the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right and the point E.sub.L and a topological relationship between the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and the point E.sub.R according to a type of the boundary line unit B.sub.2.

6. The method of claim 1, wherein generating the transverse topological relationship between the two adjacent lanes in each segment of the lane group comprises: (1) if the boundary line unit B.sub.1 is blank, namely there is no lane line or B.sub.1 is a dotted line, generating a transverse topological relationship that lane changing is allowed in the two lanes in a cutting region; (2) if the boundary line unit B.sub.1 is dotted on the left and solid on the right, generating a transverse topological relationship of changing from the left lane to the right lane in the cutting region; (3) if the boundary line unit B.sub.1 is solid on the left and dotted on the right, generating a transverse topological relationship of changing from the right lane to the left lane in the cutting region; and (4) under circumstance except for the three circumstances, not generating the transverse topological relationship between the two lanes in the cutting region.

7. A system for constructing a transverse topological relationship of lanes in a high-definition map, comprising: a memory for storing instructions; a processor configured to execute the instructions to perform steps of: acquiring data of lane groups from the high-definition map; for each lane group, sequentially extracting a shared boundary line group of two adjacent lanes and determining the number of parallel boundary line elements in the shared boundary line group; if the number of the parallel boundary line elements is 1, not generating a transverse topological relationship between the two adjacent lanes; if the number of the parallel boundary line elements is not 1, determining the number and types of boundary line units on the parallel boundary line elements; if the number of the boundary line units is 1, generating the transverse topological relationship between the two adjacent lanes according to a type of a shared boundary line; and if the number of the boundary line units is not 1, performing segmentation processing on the lane group along a lane direction according to a point, where switching between a solid line and a dotted line occurs, of the shared boundary line, and sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to a position of the point where switching between the solid line and dotted line occurs and the types of the boundary line units.

8. The system of claim 7, wherein performing segmentation processing on the lane group along the lane direction according to the point where switching between the solid line and dotted line occurs of the shared boundary line comprises: if a previous boundary line unit of the point where switching between the solid line and dotted line occurs of the shared boundary line is B.sub.1, acquiring a distance dis between an ending point A of the boundary line unit B.sub.1 and a starting point S of a shared boundary line L from the lane group data, the distance dis being an accumulated sum of shape point line segments between the point S and the point A; acquiring shape coordinate points of the shared boundary line L, and assuming a set of the vectorized coordinate points of the shared boundary line is {P.sub.1, P.sub.2, P.sub.3 . . . P.sub.n}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1{P.sub.1, P.sub.2}, L.sub.2{P.sub.2, P.sub.3}, L.sub.3{P.sub.3, P.sub.4} . . . line segment L.sub.n−1{P.sub.n−1, P.sub.n} and calculating lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments; calculating a specific line segment, where the ending point A is located, in a line segment set L.sub.1, L.sub.2, L.sub.3, . . . L.sub.n−1 according to the distance dis and the lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments, A being denoted as located on a line segment L.sub.a and a starting point of L.sub.a being denoted as B; calculating a distance between the ending point A and B and calculating a position of the point A on the line segment L.sub.a according to the distance to acquire a coordinate of the point A; forming, by the point A and the point B, a line segment L.sub.AB, drawing a perpendicular line V.sub.A, that passes through the point A, of the line segment L.sub.AB and performing cutting processing on the lane group by use of the perpendicular line V.sub.A; and repeating the steps to cut the lane group into multiple segments along the lane direction according to shared boundary line units.

9. The system of claim 8, after performing cutting processing on the lane group along the lane direction, further comprising: calculating an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.L on the left of the shared boundary line L, and an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.R on the right of the shared boundary line L.

10. The system of claim 9, wherein calculating the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left of the shared boundary line L and the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right of L comprises: acquiring shape coordinate points of the lane centerline C.sub.R on the right of the shared boundary line L, and assuming a set of the vectorized coordinate points of the lane centerline C.sub.R is {P.sub.1′, P.sub.2′, P.sub.3′ . . . P.sub.n′}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1′{P.sub.1′, P.sub.2′}, L.sub.2′{P.sub.2′, P.sub.3′}, L.sub.3′{P.sub.3′, P.sub.4′} . . . line segment L.sub.n−1′{P.sub.n−1′, P.sub.n′}; determining whether the perpendicular line V.sub.A is intersected with a line segment set {L.sub.1′, L.sub.2′, L.sub.3′ . . . L.sub.n−1′} or not, and calculating an intersection point, if there is more than one intersection point, extracting the intersection point closest to the point A, the intersection point being denoted as as a point C; and assuming the lane centerline on the left of the shared boundary line L is C.sub.L, repeating the steps to calculate an intersection point D between the perpendicular line V.sub.A and C.sub.L.

11. The system of claim 10, wherein sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to the position of the point where switching between the solid line and dotted line occurs and the types of the boundary line unit comprises: for a point A where switching between a solid line and a dotted line occurs, determining a position of the point where the switching occurs at first; if the point A is the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, a starting point of the lane centerline C.sub.R on the right being denoted as S.sub.R and a starting point of the lane centerline C.sub.L on the left being denoted as S.sub.L, generating topological relationships between the point S.sub.R and the point D and between the point S.sub.L and the point C according to the type of the boundary line unit B.sub.1; if the point A is not the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, generating a topological relationship between an intersection point C.sup.−1 of a perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.R on the right and the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and a topological relationship between an intersection point D.sup.−1 of the perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.L on the left and the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right according to the type of the boundary line unit B.sub.1, V.sub.A.sup.−1 being a perpendicular line passing through a point, where switching between a solid line and a dotted line occurs and which is previous to the point A, and V.sub.A being a perpendicular line passing through the point A; and if the point A is the last point where switching between a solid line and a dotted line occurs on the shared boundary line, a boundary line unit next to the point A being denoted as B.sub.2, a terminal point of the lane centerline C.sub.R on the right being denoted as E.sub.R and the starting point of the lane centerline C.sub.L on the left being denoted as E.sub.L, generating a topological relationship between the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right and the point E.sub.L and a topological relationship between the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and the point E.sub.R according to a type of the boundary line unit B.sub.2.

12. The system of claim 7, wherein generating the transverse topological relationship between the two adjacent lanes in each segment of the lane group comprises: (1) if the boundary line unit B.sub.1 is blank, namely there is no lane line or B.sub.1 is a dotted line, generating a transverse topological relationship that lane changing is allowed in the two lanes in a cutting region; (2) if the boundary line unit B.sub.1 is dotted on the left and solid on the right, generating a transverse topological relationship of changing from the left lane to the right lane in the cutting region; (3) if the boundary line unit B.sub.1 is solid on the left and dotted on the right, generating a transverse topological relationship of changing from the right lane to the left lane in the cutting region; and (4) under circumstance except for the three circumstances, not generating the transverse topological relationship between the two lanes in the cutting region.

13. A non-transitory memory having stored thereon a computer program configured to implement the method for constructing a transverse topological relationship of lanes in a high-definition map, the method comprising: acquiring data of lane groups from the high-definition map; for each lane group, sequentially extracting a shared boundary line group of two adjacent lanes and determining the number of parallel boundary line elements in the shared boundary line group; if the number of the parallel boundary line elements is 1, not generating a transverse topological relationship between the two adjacent lanes; if the number of the parallel boundary line elements is not 1, determining the number and types of boundary line units on the parallel boundary line elements; if the number of the boundary line units is 1, generating the transverse topological relationship between the two adjacent lanes according to a type of a shared boundary line; and if the number of the boundary line units is not 1, performing segmentation processing on the lane group along a lane direction according to a point, where switching between a solid line and a dotted line occurs, of the shared boundary line, and sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to a position of the point where switching between the solid line and dotted line occurs and the types of the boundary line units.

14. The memory of claim 13, wherein performing segmentation processing on the lane group along the lane direction according to the point where switching between the solid line and dotted line occurs of the shared boundary line comprises: if a previous boundary line unit of the point where switching between the solid line and dotted line occurs of the shared boundary line is B.sub.1, acquiring a distance dis between an ending point A of the boundary line unit B.sub.1 and a starting point S of a shared boundary line L from the lane group data, the distance dis being an accumulated sum of shape point line segments between the point S and the point A; acquiring shape coordinate points of the shared boundary line L, and assuming a set of the vectorized coordinate points of the shared boundary line is {P.sub.1, P.sub.2, P.sub.3 . . . P.sub.n}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1{P.sub.1, P.sub.2}, L.sub.2{P.sub.2, P.sub.3}, L.sub.3{P.sub.3, P.sub.4} . . . line segment L.sub.n−1{P.sub.n−1, P.sub.n} and calculating lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments; calculating a specific line segment, where the ending point A is located, in a line segment set L.sub.1, L.sub.2, L.sub.3, . . . L.sub.n−1 according to the distance dis and the lengths len.sub.1, len.sub.2, len.sub.3, len.sub.n−1 of the line segments, A being denoted as located on a line segment L.sub.a and a starting point of L.sub.a being denoted as B; calculating a distance between the ending point A and B and calculating a position of the point A on the line segment L.sub.a according to the distance to acquire a coordinate of the point A; forming, by the point A and the point B, a line segment L.sub.AB, drawing a perpendicular line V.sub.A, that passes through the point A, of the line segment L.sub.AB and performing cutting processing on the lane group by use of the perpendicular line V.sub.A; and repeating the steps to cut the lane group into multiple segments along the lane direction according to shared boundary line units.

15. The memory of claim 14, after performing cutting processing on the lane group along the lane direction, further comprising: calculating an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.L on the left of the shared boundary line L, and an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.R on the right of the shared boundary line L.

16. The memory of claim 15, wherein calculating the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left of the shared boundary line L and the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right of L comprises: acquiring shape coordinate points of the lane centerline C.sub.R on the right of the shared boundary line L, and assuming a set of the vectorized coordinate points of the lane centerline C.sub.R is {P.sub.1′, P.sub.2′, P.sub.3′ . . . P.sub.n′}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.2′{P.sub.1′, P.sub.2′}, L.sub.2′{P.sub.2′, P.sub.3′}, L.sub.3′{P.sub.3′, P.sub.4′} . . . line segment L.sub.n−1′{P.sub.n−1′, P.sub.n′}; determining whether the perpendicular line V.sub.A is intersected with a line segment set {L.sub.1′, L.sub.2′, L.sub.3′ . . . L.sub.n−1′} or not, and calculating an intersection point, if there is more than one intersection point, extracting the intersection point closest to the point A, the intersection point being denoted as as a point C; and assuming the lane centerline on the left of the shared boundary line L is C.sub.L, repeating the steps to calculate an intersection point D between the perpendicular line V.sub.A and C.sub.L.

17. The memory of claim 16, wherein sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to the position of the point where switching between the solid line and dotted line occurs and the types of the boundary line unit comprises: for a point A where switching between a solid line and a dotted line occurs, determining a position of the point where the switching occurs at first; if the point A is the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, a starting point of the lane centerline C.sub.R on the right being denoted as S.sub.R and a starting point of the lane centerline C.sub.L on the left being denoted as S.sub.L, generating topological relationships between the point S.sub.R and the point D and between the point S.sub.L and the point C according to the type of the boundary line unit B.sub.1; if the point A is not the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, generating a topological relationship between an intersection point C.sup.−1 of a perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.R on the right and the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and a topological relationship between an intersection point D.sup.−1 of the perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.L on the left and the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right according to the type of the boundary line unit B.sub.1, V.sub.A.sup.−1 being a perpendicular line passing through a point, where switching between a solid line and a dotted line occurs and which is previous to the point A, and V.sub.A being a perpendicular line passing through the point A; and if the point A is the last point where switching between a solid line and a dotted line occurs on the shared boundary line, a boundary line unit next to the point A being denoted as B.sub.2, a terminal point of the lane centerline C.sub.R on the right being denoted as E.sub.R and the starting point of the lane centerline C.sub.L on the left being denoted as E.sub.L, generating a topological relationship between the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right and the point E.sub.L and a topological relationship between the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and the point E.sub.R according to a type of the boundary line unit B.sub.2.

18. The memory of claim 13, wherein generating the transverse topological relationship between the two adjacent lanes in each segment of the lane group comprises: (1) if the boundary line unit B.sub.1 is blank, namely there is no lane line or B.sub.1 is a dotted line, generating a transverse topological relationship that lane changing is allowed in the two lanes in a cutting region; (2) if the boundary line unit B.sub.1 is dotted on the left and solid on the right, generating a transverse topological relationship of changing from the left lane to the right lane in the cutting region; (3) if the boundary line unit B.sub.1 is solid on the left and dotted on the right, generating a transverse topological relationship of changing from the right lane to the left lane in the cutting region; and (4) under circumstance except for the three circumstances, not generating the transverse topological relationship between the two lanes in the cutting region.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a processing flowchart according to an embodiment of the disclosure.

(2) FIG. 2 is an illustration diagram of high-definition roads, lane groups, lane shapes, lane nodes and a lane boundary line according to an embodiment of the disclosure.

(3) FIG. 3 is an illustration diagram of lane boundary line groups and lane boundary line units according to an embodiment of the disclosure.

(4) FIG. 4 is an illustration diagram of switching between a solid line and a dotted line of a lane boundary line unit according to an embodiment of the disclosure.

(5) FIG. 5 is an illustration diagram of a distance between an ending point of a boundary line unit and a starting point of a lane boundary line according to an embodiment of the disclosure.

(6) FIG. 6 is an illustration diagram of a set of vectorized coordinate points of a shared lane boundary line according to an embodiment of the disclosure.

(7) FIG. 7 is an illustration diagram of a set of vectorized coordinate points of a lane centerline according to an embodiment of the disclosure.

(8) FIG. 8 is an illustration diagram of an intersection point of a perpendicular line and a lane centerline at a position where switching between a solid line and a dotted line occurs of a lane boundary line according to an embodiment of the disclosure.

(9) FIG. 9 is an illustration diagram of related intersection points of perpendicular lines and lanes on two sides at a position where switching between a solid line and a dotted line occurs of a shared lane boundary line according to an embodiment of the disclosure.

(10) FIG. 10 is an illustration diagram of a transverse topological relationship at the first position where switching between a solid line and a dotted line occurs on a lane boundary line according to an embodiment of the disclosure.

(11) FIG. 11 is an illustration diagram of a transverse topological relationship at the second position where switching between a solid line and a dotted line occurs on a lane boundary line according to an embodiment of the disclosure.

(12) FIG. 12 is an illustration diagram of a transverse topological relationship at the last position where switching between a solid line and a dotted line occurs on a lane boundary line according to an embodiment of the disclosure.

(13) FIG. 13 is a structure diagram of a system according to an embodiment of the disclosure.

DETAILED DESCRIPTION

(14) The principle and characteristics of the disclosure will be described below in combination with the drawings. The listed examples are only adopted to explain the disclosure and not intended to limit the scope of the disclosure.

(15) FIG. 1 is a flowchart of a method for constructing a transverse topological relationship of lanes in a high-definition map according to an embodiment of the disclosure. The following steps are included.

(16) In 1, lane group data in a high-definition map is read, and after the data is read, it is necessary to ensure correctness of numbers of lanes in each lane group and ensure consistency between an arrangement sequence of the lanes and the real world.

(17) In 2, a read high-definition lane group set is filtered to acquire lane group data, including lane boundary line shape point information, of more than one lane. In a few lane groups illustrated in FIG. 2, the lane group 3 includes only one lane, and the lane group may be filtered.

(18) In 3, a transverse topological relationship between adjacent lanes in the same lane group is generated.

(19) In (3.1), a shared boundary line group of the two adjacent lanes is acquired.

(20) In (3.2), if the number of parallel boundary line elements in the shared boundary line group is not 1, the transverse topological relationship between the two lanes is not generated, otherwise Step (3.3) is executed.

(21) In (3.3), if the number of units of the parallel boundary line element is 1, cutting is not required and the lane changing topological relationship between the two lanes is generated according to a type of a boundary line; and if the number of the units is more than 1, Step (3.4) is executed.

(22) In (3.4), two adjacent boundary line units on a lane boundary line are extracted, whether they form switching between a solid line and a dotted line is determined, and if YES, cutting is performed by use of a cutting algorithm to obtain a perpendicular line, recorded as V.sub.A, at a position where switching between a solid line and a dotted line occurs.

(23) As illustrated in FIG. 3, a boundary line unit 0 is a single solid line, a boundary line unit 1 is a single dotted line and a boundary line unit 2 is dotted on the left and solid on the right. In such case, the boundary line unit 0 and the boundary line unit 1 form switching between a solid line and a dotted line, the boundary line unit 1 and the boundary line unit 2 also form switching between a solid line and a dotted line, and they are all required to be cut.

(24) The cutting algorithm includes the following steps.

(25) In {circle around (1)}, if a previous boundary line unit of the position where switching between a solid line and a dotted line occurs of the lane boundary line is B.sub.1 and a next boundary line unit is B.sub.2, a distance dis between an ending point A of the boundary line unit B.sub.1 and a starting point S of a shared boundary line L is acquired from the lane group data (dis is an accumulated distance sum of shape point line segments between the point S and the point A), as illustrated in FIG. 5.

(26) In {circle around (2)}, shape coordinate points of the shared boundary line L are acquired, and assuming a set of the vectorized coordinate points of the shared boundary line is {P.sub.1, P.sub.2, P.sub.3 . . . P.sub.n}, every two adjacent coordinate points form a line segment to obtain line segments L.sub.1{P.sub.1, P.sub.2}, L.sub.2{P.sub.2, P.sub.3}, L.sub.3{P.sub.3, P.sub.4} . . . line segment L.sub.n−1{P.sub.n−1, P.sub.n} and lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments are calculated, as illustrated in FIG. 6.

(27) In {circle around (3)}, the specific line segment, where the ending point A is located, in a line segment set L.sub.1, L.sub.2, L.sub.3, . . . L.sub.n−1 is calculated according to the distance dis and len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1, A being denoted as located on a line segment L.sub.a and a starting point of L.sub.a being denoted as B.

(28) In {circle around (4)}, a distance between the ending point A and B is calculated, and a position of the point A on the line segment L.sub.a is calculated according to the distance to acquire a coordinate of the point A.

(29) In {circle around (5)}, the point A and the point B form a line segment L.sub.AB, and a perpendicular line V.sub.A, that passes through the point A, of the line segment L.sub.AB is drawn.

(30) In (3.5), shape coordinate points of a lane centerline C.sub.R on the right of the shared boundary line L are acquired, and assuming a set of the vectorized coordinate points of the lane centerline C.sub.R is {P.sub.1′, P.sub.2′, P.sub.3′ . . . P.sub.n′}, every two adjacent coordinate points form a line segment to obtain line segments L.sub.1′{P.sub.1′, P.sub.2′}, L.sub.2′{P.sub.2′, P.sub.3′}, L.sub.3′{P.sub.3′, P.sub.4′} . . . line segment L.sub.n−1′{P.sub.n−1′, P.sub.n′}, as illustrated in FIG. 7.

(31) In (3.6), whether the perpendicular line V.sub.A is intersected with a line segment set {L.sub.1′, L.sub.2′, L.sub.3′ . . . L.sub.n−1′} or not is calculated, and an intersection point is calculated, if there is more than one intersection point, the intersection point closest to the point A is extracted and is denoted as a point C, as illustrated in FIG. 8.

(32) In (3.7), it is assumed that the lane centerline on the left of the shared boundary line L is C.sub.L, a right-side lane centerline of C.sub.R is B.sub.R and a left-side lane boundary line of C.sub.L is B.sub.L, Steps (3.4) and (3.5) are repeated to calculate intersection points D, E and F between the perpendicular line V.sub.A and C.sub.L, B.sub.R and B.sub.L, as illustrated in FIG. 9.

(33) In (3.8), the transverse topological relationship is generated.

(34) In {circle around (1)}, if B.sub.1 and B.sub.2 are adjacent boundary line units on two sides of the first position where switching between a solid line and a dotted line occurs on the shared lane boundary line, a starting point of the lane centerline C.sub.R on the right is recorded as S.sub.R and a starting point of the lane centerline C.sub.L on the left is recorded as S.sub.L, topological relationships between the point S.sub.R and the point D and between the point S.sub.L and the point C are generated according to a type of the boundary line unit B.sub.1, as illustrated in FIG. 10. In FIG. 10, the type of the boundary line unit B.sub.1 is a single solid line and a vehicle is not allowed to change the lane, so that the topological relationship between the point S.sub.R and the point D and the topological relationship between the point S.sub.L and the point C are not required to be generated.

(35) In {circle around (2)}, if B.sub.1 and B.sub.2 are adjacent boundary line units on the two sides of the first position where switching between a solid line and a dotted line occurs on the shared lane boundary line, an intersection point of the perpendicular line and the lane centerline C.sub.R at a previous position where switching between a solid line and a dotted line occurs is recorded as G.sub.R and an intersection point with the lane centerline C.sub.L is recorded as G.sub.L, topological relationships between a point G.sub.R and the point D and between a point G.sub.L and the point C are generated according to the type of the boundary line unit B.sub.1, as illustrated in FIG. 11. In FIG. 11, the type of the boundary line unit B.sub.1 is a single dotted line and a vehicle is allowed to change the lane, so that the topological relationship between the point G.sub.R and the point D and the topological relationship between the point G.sub.L and the point C are generated, and the vehicle may change the lane from the point G.sub.R of the right lane to the point D of the left lane and may change the lane from the point G.sub.L of the left lane to the point C of the right lane.

(36) In {circle around (3)}, if B.sub.1 and B.sub.2 are where the last switching between a solid line and a dotted line occurs on the shared lane boundary line, an ending point of the lane centerline C.sub.R is recorded as E.sub.R and an ending point of the lane centerline C.sub.L is recorded as E.sub.L, it is necessary to generate topological relationships between the point C and the point E.sub.L and between the point D and the point E.sub.R according to a type of the boundary line unit B.sub.2 as illustrated in FIG. 12. In FIG. 12, the type of the boundary line unit B.sub.2 is dotted on the left and solid on the right and a vehicle may change from the left lane to the right lane but may not change from the right lane to the left lane, so that only the topological relationship between the point D and the point E.sub.R is generated.

(37) In (3.9), Step (3.2)-Step (3.8) are repeated to generate transverse topological relationships at all positions where switching between a solid line and a dotted line occurs on the shared lane boundary line.

(38) In ((3.10), Step (3.2)-(3.9) are repeated to generate transverse topological relationships between every two adjacent lanes in the same lane group.

(39) According to the disclosure, a transverse topological relationship between two adjacent lanes at a position where switching between a solid line and a dotted line occurs of a lane boundary line is calculated simply by use of an accumulated sum of lengths of line segments, a relationships between the line segments and a relationship between a line segment and a straight line, thereby simplifying complex lane-level path planning into simple plane-level data calculation problem.

(40) Referring to FIG. 13, FIG. 13 is a system 1300 according to an embodiment of the disclosure. The UE 1300 includes a processing unit 1301 and a storage unit 1302.

(41) The processing unit 1301 is configured to execute executable programs stored in the storage unit 1302 to perform steps of:

(42) acquiring data of lane groups from the high-definition map;

(43) for each lane group, sequentially extracting a shared boundary line group of two adjacent lanes and determining the number of parallel boundary line elements in the shared boundary line group;

(44) if the number of the parallel boundary line elements is 1, not generating a transverse topological relationship between the two adjacent lanes;

(45) if the number of the parallel boundary line elements is not 1, determining the number and types of boundary line units on the parallel boundary line elements;

(46) if the number of the boundary line units is 1, generating the transverse topological relationship between the two adjacent lanes according to a type of a shared boundary line; and

(47) if the number of the boundary line units is not 1, performing segmentation processing on the lane group along a lane direction according to a point, where switching between a solid line and a dotted line occurs, of the shared boundary line, and sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to a position of the point where switching between the solid line and dotted line occurs and the types of the boundary line units.

(48) The step of performing segmentation processing on the lane group along the lane direction according to the point where switching between the solid line and dotted line occurs of the shared boundary line comprises:

(49) if a previous boundary line unit of the point where switching between the solid line and dotted line occurs of the shared boundary line is B.sub.1, acquiring a distance dis between an ending point A of the boundary line unit B.sub.1 and a starting point S of a shared boundary line L from the lane group data, the distance dis being an accumulated sum of shape point line segments between the point S and the point A;

(50) acquiring shape coordinate points of the shared boundary line L, and assuming a set of the vectorized coordinate points of the shared boundary line is {P.sub.1, P.sub.2, P.sub.3 . . . P.sub.n}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1{P.sub.1, P.sub.2}, L.sub.2 {P.sub.2, P.sub.3}, L.sub.3 {P.sub.3, P.sub.4} . . . line segment L.sub.n−1{P.sub.n−1, P.sub.n} and calculating lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments;

(51) calculating a specific line segment, where the ending point A is located, in a line segment set L.sub.1, L.sub.2, L.sub.3, . . . L.sub.n−1 according to the distance dis and the lengths len.sub.1, len.sub.2, len.sub.3, . . . len.sub.n−1 of the line segments, A being denoted as located on a line segment L.sub.a and a starting point of L.sub.a being denoted as B;

(52) calculating a distance between the ending point A and B and calculating a position of the point A on the line segment L.sub.a according to the distance to acquire a coordinate of the point A;

(53) forming, by the point A and the point B, a line segment L.sub.AB, drawing a perpendicular line V.sub.A, that passes through the point A, of the line segment L.sub.AB and performing cutting processing on the lane group by use of the perpendicular line V.sub.A; and

(54) repeating the steps to cut the lane group into multiple segments along the lane direction according to shared boundary line units.

(55) After the step of performing cutting processing on the lane group along the lane direction, further comprising: calculating an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.L on the left of the shared boundary line L, and an intersection point of the perpendicular line V.sub.A and a lane centerline C.sub.R on the right of the shared boundary line L.

(56) The step of calculating the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left of the shared boundary line L and the intersection point of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right of L comprises:

(57) acquiring shape coordinate points of the lane centerline C.sub.R on the right of the shared boundary line L, and assuming a set of the vectorized coordinate points of the lane centerline C.sub.R is {P.sub.1′, P.sub.2′, P.sub.3′ . . . P.sub.n′}, forming, by every two adjacent coordinate points, a line segment to obtain line segments L.sub.1′{P.sub.1′, P.sub.2′}, L.sub.2′{P.sub.2′, P.sub.3′}, L.sub.3′{P.sub.3′, P.sub.4′} . . . line segment L.sub.n−1′{P.sub.n−1′, P.sub.n′};

(58) determining whether the perpendicular line V.sub.A is intersected with a line segment set {L.sub.1′, L.sub.2′, L.sub.3′ . . . L.sub.n−1′} or not, and calculating an intersection point, if there is more than one intersection point, extracting the intersection point closest to the point A, the intersection point being denoted as as a point C; and

(59) assuming the lane centerline on the left of the shared boundary line L is C.sub.L, repeating the steps to calculate an intersection point D between the perpendicular line V.sub.A and C.sub.L.

(60) The step of sequentially generating the transverse topological relationship between two adjacent lanes in each of segments, which are obtained by the segmentation processing on the lane group, according to the position of the point where switching between the solid line and dotted line occurs and the types of the boundary line unit comprises:

(61) for a point A where switching between a solid line and a dotted line occurs, determining a position of the point where the switching occurs at first;

(62) if the point A is the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, a starting point of the lane centerline C.sub.R on the right being denoted as S.sub.R and a starting point of the lane centerline C.sub.L on the left being denoted as S.sub.L, generating topological relationships between the point S.sub.R and the point D and between the point S.sub.L and the point C according to the type of the boundary line unit B.sub.1;

(63) if the point A is not the first point of points where switching between a solid line and a dotted line occurs on the shared boundary line, generating a topological relationship between an intersection point C.sup.−1 of a perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.R on the right and the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and a topological relationship between an intersection point D.sup.−1 of the perpendicular line V.sub.A.sup.−1 and the lane centerline C.sub.L on the left and the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right according to the type of the boundary line unit B.sub.1, V.sub.A.sup.−1 being a perpendicular line passing through a point, where switching between a solid line and a dotted line occurs and which is previous to the point A, and V.sub.A being a perpendicular line passing through the point A; and

(64) if the point A is the last point where switching between a solid line and a dotted line occurs on the shared boundary line, a boundary line unit next to the point A being denoted as B.sub.2, a terminal point of the lane centerline C.sub.R on the right being denoted as E.sub.R and the starting point of the lane centerline C.sub.L on the left being denoted as E.sub.L, generating a topological relationship between the intersection point C of the perpendicular line V.sub.A and the lane centerline C.sub.R on the right and the point E.sub.L and a topological relationship between the intersection point D of the perpendicular line V.sub.A and the lane centerline C.sub.L on the left and the point E.sub.R according to a type of the boundary line unit B.sub.2.

(65) The step of generating the transverse topological relationship between the two adjacent lanes in each segment of the lane group comprises:

(66) (1) if the boundary line unit B.sub.1 is blank, namely there is no lane line or B.sub.1 is a dotted line, generating a transverse topological relationship that lane changing is allowed in the two lanes in a cutting region;

(67) (2) if the boundary line unit B.sub.1 is dotted on the left and solid on the right, generating a transverse topological relationship of changing from the left lane to the right lane in the cutting region;

(68) (3) if the boundary line unit B.sub.1 is solid on the left and dotted on the right, generating a transverse topological relationship of changing from the right lane to the left lane in the cutting region; and

(69) (4) under circumstance except for the three circumstances, not generating the transverse topological relationship between the two lanes in the cutting region.

(70) The disclosure has the following beneficial effects. According to the disclosure, a transverse topological relationship between two adjacent lanes at a position where switching between a solid line and a dotted line occurs of a lane boundary line is calculated simply by use of an accumulated sum of lengths of line segments, a relationships between the line segments and a relationship between a line segment and a straight line, thereby simplifying complex lane-level path planning into simple plane-level data calculation problem.

(71) In an exemplary embodiment, the processing unit 1301 may be a processor or a controller (which may be, for example, a Central Processing Unit (CPU), a universal processor, a Digital Signal Processor (DSP), an Application-Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or another programmable logical device, transistor logical device, hardware component or any combination thereof. It may implement or execute various exemplary logical blocks, modules and circuits described in combination with the contents disclosed in the disclosure. The processor may also be a combination realizing a calculation function (for example, including a combination of one or more microprocessors and a combination of a DSP and a microprocessor. The storage unit 1302 may be a memory.

(72) An embodiment of the disclosure also provides a computer-readable storage medium, which stores a computer program configured for electronic data exchange, the computer program enabling a computer to execute part or all of the operations executed in the abovementioned methods.

(73) An embodiment of the disclosure also provides a computer program product. The computer program product includes a non-transitory computer-readable storage medium storing a computer program. The computer program may be operated to enable a computer to execute part or all of the operations executed in the abovementioned methods. The computer program product may be a software installation package.

(74) The operations of the method or algorithm described in the embodiments of the disclosure may be implemented in a hardware manner, or may be implemented in a manner of executing, by a processor, software. A software instruction may consist of a corresponding software module, and the software module may be stored in a RAM, a flash memory, a Read Only Memory (ROM), an Erasable Programmable ROM (EPROM), an Electrically EPROM (EEPROM), a register, a hard disk, a mobile hard disk, a Compact Disc-ROM (CD-ROM) or a storage medium in any other form well known in the field. An exemplary storage medium is coupled to the processor, thereby enabling the processor to read information from the storage medium and write information into the storage medium. Of course, the storage medium may also be a component of the processor. The processor and the storage medium may be located in an ASIC. In addition, the ASIC may be located in an access network device, a target network device or a core network device. Of course, the processor and the storage medium may also exist in the access network device, the target network device or the core network device as discrete components.

(75) Those skilled in the art may realize that, in one or more abovementioned examples, all or part of the functions described in the embodiments of the disclosure may be realized through software, hardware or any combination thereof. During implementation with the software, the embodiments may be implemented completely or partially in form of computer program product. The computer program product includes one or more computer instructions. When the computer program instruction is loaded and executed on a computer, the flows or functions according to the embodiments of the disclosure are completely or partially generated. The computer may be a universal computer, a dedicated computer, a computer network or another programmable device. The computer instruction may be stored in a computer-readable storage medium or transmitted from one computer-readable storage medium to another computer-readable storage medium. For example, the computer instruction may be transmitted from a website, computer, server or data center to another website, computer, server or data center in a wired (for example, coaxial cable, optical fiber and Digital Subscriber Line (DSL)) or wireless (for example, infrared, wireless and microwave) manner. The computer-readable storage medium may be any available medium accessible for the computer or a data storage device, such as a server and a data center, including one or more integrated available media. The available medium may be a magnetic medium (for example, a floppy disk, a hard disk and a magnetic tape), an optical medium (for example, a Digital Video Disc (DVD)), a semiconductor medium (for example, a Solid State Disk (SSD)) or the like.

(76) The above is only the preferred embodiment of the disclosure and not intended to limit the disclosure. Any modifications, equivalent replacements, improvements and the like made within the spirit and principle of the disclosure shall fall within the scope of protection of the disclosure.