METHOD FOR DETERMINING POLYGONS THAT OVERLAP WITH A CANDIDATE POLYGON OR POINT

• US 20180137675A1
• Filed: 11/16/2016
• Published: 05/17/2018
• Est. Priority Date: 11/16/2016
• Status: Active Grant

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: HERE Global B.V. (HERE Holding Corporation)
• Inventors: KWANT, Richard, MITTAL, Anish, LAWLOR, David
• Granted Patent: US 10,445,927 B2
• Time in Patent Office: Days
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 2210/21 Collision detection, intersection

Abstract

An approach is provided for determining a polygon of a geographic database that overlaps a candidate polygon or candidate point. The geographic database represents stored polygons as respective polygon points with zero area. The approach involves determining proximate polygon points from among the respective polygon points with zero area that are within a distance threshold of the candidate polygon or the candidate point. The approach also involves retrieving one or more proximate polygons from the geographic database that correspond to the one or more proximate polygon points. The approach further involves determining an intersection between the one or more proximate polygons and the candidate polygon or the candidate point. The approach then involves selecting the polygon that overlaps the candidate polygon or the candidate point based on the determined intersection.

Claims

1. A method for determining a plurality of polygons of a geographic database that overlaps a candidate polygon or a candidate point, wherein the geographic database represents stored polygons as respective polygon points with zero area, the method comprising:

determining, by a processor, proximate polygon points from among the respective polygon points with zero area of the geographic database that are within a distance threshold of the candidate polygon or the candidate point;

retrieving proximate polygons from the geographic database that correspond to the proximate polygon points;

determining an intersection between the proximate polygons and the candidate polygon or the candidate point;

selecting the plurality of polygons among the proximate polygons each of which overlaps the candidate polygon or the candidate point based on the determined intersection, wherein the candidate polygon and at least one of the plurality of polygons are three-dimensional polygons; and

initiating a presentation of recommendations corresponding to the plurality of polygons on a user interface.

2. The method of claim 1, wherein the respective polygon points are respective centroids of the stored polygons, wherein at least two of the plurality of polygons overlap with each other.

3. The method of claim 1, further comprising:

determining a geographic feature associated with the candidate polygon, the candidate point, the proximate polygons, the proximate polygon points, or a combination thereof; and

determining the distance threshold based on the geographic feature.

4. The method of claim 1, wherein the at least one of the plurality of polygons is a three-dimensional polygon representing a real-world building or park that overlaps or contains the candidate polygon.

5. The method of claim 1, wherein the candidate polygon is a new polygon, the method further comprising:

collating the candidate polygon into the geographic database based on the plurality of polygons, other previously stored or detected polygons in the geographic database, or a combination thereof, wherein the candidate polygon overlaps at least one other three-dimensional candidate polygon in the geographic database.

6. The method of claim 1, further comprising:

presenting the plurality of polygons as recommended points-of-interest in the user interface.

7. The method of claim 1, wherein the candidate polygon or the candidate point represents a user location trace, the method further comprising:

identifying points of interest associated with the user location trace based on the plurality of polygons.

8. The method of claim 1, wherein the determining of the intersection with respect to the candidate point comprises:

extending a horizontal line from the candidate point to infinity;

counting a number of times the horizontal line intersects with an edge of at least one of the proximate polygons;

determining that the intersection is of the candidate point and the at least one of the proximate polygons when the number of times is odd or if the candidate point lies on the edge.

9. The method of claim 1, wherein the determining of the intersection with respect to the candidate polygon comprises:

constructing a convex hull of a union of the candidate polygon and at least one of the proximate polygons;

determining a pocket lid of the convex hull;

determining the intersection as respective portions of the candidate polygon and the at least one of the proximate polygons that lie within a pocket delineated by the pocket lid.

10. The method of claim 1, wherein the plurality of polygons, the stored polygons, or a combination thereof include at lease one two-dimensional polygon.

17. The non-transitory computer-readable storage medium of claim 1, wherein the candidate polygon represents an area of location uncertainty surrounding of a location determined from a location sensor of a device.

11. A non-transitory computer-readable storage medium for determining a polygon of a geographic database that overlaps a candidate polygon or a candidate point, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform:

selecting a respective point of each polygon stored in the geographic database, wherein the respective point is a zero area of said each polygon;

creating a spatial index of said each polygon using the respective point; and

storing the spatial index in the geographic database,

wherein the spatial index is searched to determine one or more proximate points from among

the indexed respective points that are within a distance threshold of the candidate polygon or the candidate point; and

wherein one or more proximate polygons corresponding to the one or more proximate points are retrieved from the geographic database to determine the polygon that overlaps the candidate polygon or the candidate point.

12. The non-transitory computer-readable storage medium of claim 11, wherein the apparatus is further caused to perform:

creating the spatial index as a quad-tree representation.

13. The non-transitory computer-readable storage medium of claim 12, wherein the apparatus is further caused to perform:

determining a number of levels in the quad-tree representation based on the distance threshold.

14. The non-transitory computer-readable storage medium of claim 12, wherein the searched spatial index returns a bin of the quad-tree containing the one or more proximate points.

15. The non-transitory computer-readable storage medium of claim 11, wherein the one or more proximate polygons are a subset of less than all of a plurality of polygons stored in the geographic database.

16. The non-transitory computer-readable storage medium of claim 11, wherein the distance threshold is a radius from a center point of the candidate polygon or the candidate point.

18. An apparatus for determining a plurality of polygons of a geographic database that overlaps a candidate polygon or a candidate point, wherein the geographic database represents stored polygons as respective polygon points with zero area, the apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following,

determine proximate polygon points from among the respective polygon points with zero area of the geographic database that are within a distance threshold of the candidate polygon or the candidate point

retrieve proximate polygons from the geographic database that correspond to the proximate polygon points;

determine an intersection between the proximate polygons and the candidate polygon or the candidate point

select the plurality of polygons among the proximate polygons each of which overlaps the candidate polygon or the candidate point based on the determined intersection, wherein the candidate polygon and at least one of the plurality of polygons are three-dimensional polygons; and

initiate a presentation of recommendations corresponding to the plurality of polygons on a user interface.

19. The apparatus of claim 18, wherein the apparatus is a server that provides mapping-related services or navigation-related services to user devices over a communication network.

20. The apparatus of claim 18, wherein the stored polygons represent respective footprints of geographic features, and wherein the geographic features include buildings.