Patent ID: 11970185
Assignee: FORD GLOBAL TECHNOLOGIES, LLC
Field: Measurement (Instruments)
Classification: CPC B  G | IPC B  G

Claim 0:
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.