Data structure for storing information relating to an environment of an autonomous vehicle and methods of use thereof
Methods and systems for determining information about an area that includes a polygon for controlling navigation of an autonomous vehicle are disclosed. The methods include defining a bounding box that encloses the area, and generating a KD-tree from the bounding box that partitions the polygon into a plurality of leaf nodes that each include at least some of a plurality of edges of the polygon. The methods also include assigning a reference point to each leaf node, creating a data representation of the area that comprises the KD-tree, and adding the data representation to map data comprising the area. A reference point is associated with a location within that leaf node, and information relating to whether the reference point lies outside or inside the at least one polygon.
1. A method for determining information about an area for controlling navigation of an autonomous vehicle, the method comprising, by a processor:
defining a bounding box that encloses the area, wherein the area comprises at least one polygon;
generating, from the bounding box, a KD-tree that partitions the at least one polygon into a plurality of leaf nodes, each of the plurality of leaf nodes comprising at least some of a plurality of edges of the at least one polygon;
assigning a reference point to each of the plurality of leaf nodes, wherein the reference point is associated with:
a location within that leaf node, and
information relating to whether the reference point lies outside or inside the at least one polygon;
creating a data representation of the area that comprises the KD-tree; and
adding the data representation to map data comprising the area;
identifying the location of a query point with respect to the area using the data representation, wherein identifying the location of the query point with respect to the area comprises determining that the query point lies inside the at least one polygon when:
the reference point lies inside the at least one polygon and a count is even, the count being indicative of a number of edges of the at least one polygon that a line segment that joins the query point and the reference point intersects; or
the reference point lies outside the at least one polygon and the count is odd; and
controlling navigation of the autonomous vehicle to traverse the area using the location.
2. The method of claim 1 , wherein identifying the location of the query point with respect to the geographical area comprises determining that the query point lies outside the at least one polygon when:
the reference point lies inside the at least one polygon and the count is odd, the count being indicative of a number of edges of the at least one polygon that a line segment that joins the query point and the reference point intersects; or
the reference point lies outside the at least one polygon and the count is even.
3. The method of claim 1 , wherein the KD-tree further comprises a plurality of partition nodes that divide the bounding box or a previously identified partition node into two regions that each include an equal number of geometrical constructs of the at least one polygon.
4. The method of claim 1 , wherein:
a leaf node of the plurality of leaf nodes comprises segments from two polygons included in the area; and
the method further comprises generating the KD-tree by generating, corresponding to the leaf node, a first sub-leaf node and a second sub-leaf node, wherein:
the first sub-leaf node comprises a first segment corresponding to one of the two polygons and a second segment corresponding to a remaining portion of the leaf node,
the second sub-leaf node comprises a third segment corresponding to the other one of the two polygons and a fourth segment corresponding to a remaining portion of the leaf node, and
the second sub-leaf node and the first leaf node share a reference point location within the leaf node but differ in information relating to whether that reference point lies outside or inside a polygon.
5. The method of claim 1 , wherein assigning the reference point to each of the plurality of leaf nodes comprises assigning the reference point as a point that lies at a geometrical center of each of the plurality of leaf nodes.
6. The method of claim 5 , further comprising updating a location of the reference point when the point that lies at the geometrical center of the leaf node lies within a threshold distance of an edge of the at least one polygon.
7. The method of claim 6 , wherein updating the location of the reference point comprises: using a Halton sequence for identifying the location; and
storing an index for regenerating the Halton sequence in a split value location of the leaf node.
8. The method of claim 1 , further comprises storing, in the KD-tree, a flag in association with each of the plurality of edges of the at least one polygon, the flag indicative of whether that edge should be ignored while determining the location of the query point with respect to the area.
9. A system for determining information about an area for controlling navigation of an autonomous vehicle, the system comprising:
a processor; and
a non-transitory computer-readable medium comprising one or more programming instructions that, when executed by the processor, will cause the processor to:
define a bounding box that encloses the area, wherein the area comprises at least one polygon;
generate, from the bounding box, a KD-tree that partitions the at least one polygon into a plurality of leaf nodes, each of the plurality of leaf nodes comprising at least some of a plurality of edges of the at least one polygon;
assign a reference point to each of the plurality of leaf nodes, wherein the reference point is associated with:
a location within that leaf node, and
information relating to whether the reference point lies outside or inside the at least one polygon;
create a data representation of the area that comprises the KD-tree;
add the data representation to map data associated with the area:
identify the location of a query point with respect to the area, wherein the programming instructions that when executed by the processor cause the processor to identify the location of the query point with respect to the area comprise programming instructions to cause the processor to determine that the query point lies inside the at least one polygon when:
the reference point lies inside the at least one polygon and a count is even, the count being indicative of a number of edges of the at least one polygon that a line segment that joins the query point and the reference point intersects; or
the reference point lies outside the at least one polygon and the count is odd; and
control navigation of the autonomous vehicle for traversing the area using the location of the query point.
10. The system of claim 9 , wherein the programming instructions that when executed by the processor cause the processor to identify the location of the query point with respect to the area comprise programming instructions to cause the processor to determine that the query point lies outside the at least one polygon when:
the reference point lies inside the at least one polygon and the count is odd, the count being indicative of a number of edges of the at least one polygon that a line segment that joins the query point and the reference point intersects; or
the reference point lies outside the at least one polygon and the count is even.
11. The system of claim 9 , wherein the KD-tree further comprises a plurality of partition nodes that divide the bounding box or a previously identified partition node into two regions that each include an equal number of geometrical constructs of the at least one polygon.
12. The system of claim 9 , wherein:
a leaf node of the plurality of leaf nodes comprises segments from two polygons included in the area; and
the system further comprises programming instructions that, when executed by the processor, will cause the processor to generate the KD-tree by generating, corresponding to the leaf node, a first sub-leaf node and a second sub-leaf node, wherein:
the first sub-leaf node comprises a first segment corresponding to one of the two polygons and a second segment corresponding to a remaining portion of the leaf node,
the second sub-leaf node comprises a third segment corresponding to the other one of the two polygons and a fourth segment corresponding to a remaining portion of the leaf node, and
the second sub-leaf node and the first leaf node share a reference point location within the leaf node but differ in information relating to whether that reference point lies outside or inside a polygon.
13. The system of claim 9 , wherein the programming instructions that when executed by the processor cause the processor to assign the reference point to each of the plurality of leaf nodes comprise programming instructions that cause the processor to assign the reference point as a point that lies at a geometrical center of each of the plurality of leaf nodes.
14. The system of claim 13 , programming instructions that, when executed by the processor, will cause the processor to update a location of the reference point when the point that lies at the geometrical center of the leaf node lies within a threshold distance of an edge of the at least one polygon.
15. The system of claim 14 , wherein the programming instructions that when executed by the processor cause the processor to update the location of the reference point comprise programming instructions that cause the processor to:
use a Halton sequence for identifying the location; and
store an index for regenerating the Halton sequence in a split value location of the leaf node.
16. A computer program product for determining information about an area for controlling navigation of an autonomous vehicle, the computer program product comprising programming instructions that are configured to cause a processor to:
define a bounding box that encloses the area, wherein the area comprises at least one polygon;
generate, from the bounding box, a KD-tree that partitions the at least one polygon into a plurality of leaf nodes, each of the plurality of leaf nodes comprising at least some of a plurality of edges of the at least one polygon;
assign a reference point to each of the plurality of leaf nodes, wherein the reference point is associated with:
a location within that leaf node, and
information relating to whether the reference point lies outside or inside the at least one polygon;
create a data representation of the area that comprises the KD-tree;
add the data representation to map data associated with the area:
identify the location of a query point with respect to the area using the data representation, wherein to identify the location of the query point with respect to the area, the programming instructions are further configured to cause the processor to:
determine that the query point lies inside the at least one polygon when:
the reference point lies inside the at least one polygon and a count is even, the count being indicative of a number of edges of the at least one polygon that a line segment that joins the query point and the reference point intersects; or
the reference point lies outside the at least one polygon and the count is odd; or
determine that the query point lies outside the at least one polygon when:
the reference point lies inside the at least one polygon and the count is odd, the count being indicative of a number of edges of the at least one polygon that a line segment that joins the query point and the reference point intersects; or
the reference point lies outside the at least one polygon and the count is even; and
control navigation of the autonomous vehicle for traversing the area using the location of query point.