Method and system for map construction
A method of retrieving a map includes receiving a grid data of the map comprising lane segments, wherein the grid data includes an array of grids each associated with a list including none or at least one of the lane segments intersecting the respective grid; receiving coordinates of a location; identifying a first grid including the location based on the grid data; identifying a target grid that has an associated list including at least one of the lane segments as first lane segment; and outputting the first lane segment.
1. A method of map construction, comprising:
constructing an outline circumscribing a plurality of lanes on a road based on a plurality of segments that extend along the plurality of lanes or the road; and
identifying an individual outline of each of the plurality of lanes based on the plurality of segments and the outline circumscribing the plurality of lanes,
wherein the plurality of segments is obtained by partitioning polylines describing a shape of the road into segments that are constructed on a start point, an end point, or a turning point of the polylines.
2. The method of claim 1 , wherein each of the plurality of segments is marked using arrows as a bidirectional segment.
3. The method of claim 2 , further comprising:
selecting, from the plurality of segments, a segment having a first end and a second end opposite to the first end;
identifying, from the plurality of segments, a plurality of candidate segments having one end connected to the second end of the segment; and
selecting a candidate segment from the plurality of candidate segments based on a comparison of an angle between the segment and each of the plurality of candidate segments, wherein the candidate segment includes a third end and a fourth end opposite to the third end, wherein the third end of the candidate segment is connected to the second end of the segment.
4. The method of claim 3 ,
wherein a first angle in between the candidate segment and the segment is determined in one direction from the segment to the candidate segment, and
wherein in response to the one direction being a counterclockwise direction, the candidate segment is selected in response to the first angle being greater than a first set of one or more angles determined respectively from the segment to one or more remaining candidate segments in the counterclockwise direction from the segment, and
wherein in response to the one direction being a clockwise direction, the candidate segment is selected in response to the first angle being less than a second set of one or more angles determined respectively from the segment to the one or more remaining candidate segments in the clockwise direction from the segment.
5. The method of claim 3 , further comprising:
removing, from the segment, a first arrow pointing from the first end to the second end of the segment in response to the selecting the candidate segment, wherein the segment includes a second arrow pointing from the second end to the first end of the segment.
6. The method of claim 2 , further comprising:
selecting, from the plurality of segments, a segment having a first end and a second end opposite to the first end;
identifying, from the plurality of segments, a plurality of candidate segments having one end connected to the second end of the segment;
selecting a second candidate segment from the plurality of candidate segments based on another comparison of an angle between the segment and each of the plurality of candidate segments, wherein the second candidate segment includes a fifth end and a sixth end opposite to the fifth end, wherein the fifth end of the second candidate segment is connected to the second end of the segment.
7. The method of claim 6 ,
wherein a second angle in between the second candidate segment and the segment is determined in a counterclockwise direction from the segment to the second candidate segment, and
wherein the second candidate segment is selected in response to the second angle being less than a first set of one or more angles determined respectively from the segment to one or more remaining candidate segments in the counterclockwise direction from the segment.
8. The method of claim 7 , further comprising:
removing, from the second candidate segment, a third arrow pointing from the fifth end to the sixth end of the second candidate segment in response to the selecting the second candidate segment,
wherein the second candidate segment includes a fourth arrow pointing from the sixth end to the fifth end of the second candidate segment,
wherein a lane segment is determined by circumscribing the segment, the second candidate segment, and two additional segments,
wherein each of the two additional segments have one end respectively connected to the segment and the second candidate segment, and
wherein the two additional segments have, opposite to the one end, another end that is connected to each other.
9. A system, comprising:
a processor; and
a memory including processor-executable instructions that, when executed by the processor, cause the system to perform operations comprising:
construct an outline circumscribing a plurality of lanes on a road based on a plurality of segments that extend along the plurality of lanes or the road; and
identify an individual outline of each of the plurality of lanes based on the plurality of segments and the outline circumscribing the plurality of lanes,
wherein the plurality of segments is obtained by partitioning polylines describing a shape of the road into segments that are constructed on a start point, an end point, or a turning point of the polylines.
10. The system of claim 9 , wherein the outline forms a closed space that circumscribe the plurality of lanes.
11. The system of claim 9 , wherein the processor is further configured to:
cause a vehicle to operate along a set of waypoints on a lane from the plurality of lanes, wherein the set of waypoints are calculated in a middle of the lane.
12. The system of claim 9 , wherein the processor is further configured to:
construct, for each of the plurality of lanes, lane geometry data based on the plurality of segments; and
generate, based on the lane geometry data, a lane content that includes a graphical representation of the plurality of lanes and waypoints of the plurality of lanes.
13. The system of claim 9 , wherein any segment from the plurality of segments does not cross any other segment from the plurality of segments.
14. A non-transitory computer readable storage medium comprising executable instructions that, when executed by at least one processor, cause the at least one processor to perform a method, comprising:
constructing an outline circumscribing a plurality of lanes on a road based on a plurality of segments that extend along the plurality of lanes or the road; and
identifying an individual outline of each of the plurality of lanes based on the plurality of segments and the outline circumscribing the plurality of lanes,
wherein the plurality of segments is obtained by partitioning polylines describing a shape of the road into segments that are constructed on a start point, an end point, or a turning point of the polylines.
15. The non-transitory computer readable storage medium of claim 14 , wherein the method further comprises:
removing, from the plurality of segments, at least one segment having one end that is not connected to another segment.
16. The non-transitory computer readable storage medium of claim 14 , wherein the method further comprises:
merging, from the plurality of segments, at least two segments in response to determining that the at least two segments merge at only one end with each other.
17. The non-transitory computer readable storage medium of claim 14 , wherein each of the plurality of lanes comprises a plurality of lane segments, wherein each lane segment is circumscribed by a set of segments from the plurality of segments.
18. The non-transitory computer readable storage medium of claim 17 , wherein a first lane segment and a second lane segment from the plurality of lane segments are determined to be in a same lane in response to determining that a first boundary segment of the first lane segment overlaps with a second boundary segment of the second lane segment, wherein the first boundary segment and the second boundary segment extends perpendicular to a direction of the plurality of lanes.
19. The non-transitory computer readable storage medium of claim 17 , wherein a third lane segment and a fourth lane segment from the plurality of lane segments are determined to be in different lanes in response to determining that a first boundary segment of the third lane segment overlaps with a second boundary segment of the fourth lane segment, wherein the first boundary segment and the second boundary segment extends parallel to a direction of the plurality of lanes.
20. The non-transitory computer readable storage medium of claim 17 , wherein the method further comprises:
converting the plurality of lane segments in each lane into a lane graph by connecting relationships between nodes of lane segments within a lane in an order.