Method for determining the intersection of polygons used to represent geographic features

• US 20030037059A1
• Filed: 08/14/2001
• Published: 02/20/2003
• Est. Priority Date: 08/14/2001
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Yang, Xiangheng
• Granted Patent: US 6,917,877 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A method for determining a polygonal intersection of a first polygon and a second polygon. An intersection of the boundary of the first polygon with the boundary of the second polygon is located by finding a point from which at least three portions of boundaries extend. From this point, a first portion of the boundary of the polygonal intersection is determined by identifying a portion of the boundary of the first polygon that is located inside the second polygon. Each subsequent portion of the boundary of the polygonal intersection is determined by selecting that portion of the boundary of either the first polygon or the second polygon that (1) connects to a leading end of a current portion of the boundary of the polygonal intersection and (2) forms the least angle with the current portion of the boundary of the polygonal intersection.

Claims

1. A method for determining a polygonal intersection of a first polygon and a second polygon comprising:

at an intersection of a boundary of the first polygon with a boundary of the second polygon, determining a first known portion of a boundary of the polygonal intersection as comprised of a portion of the boundary of the first polygon that is located inside the second polygon; and

determining each subsequent portion of the boundary of the polygonal intersection that connects to a current known portion of the boundary of the polygonal intersection by selecting that portion of the boundary either the first polygon or the second polygon that connects to a leading end of the current known portion of the boundary of the polygonal intersection and that forms a minimum rotation angle therewith.

2. The method of claim 1 wherein the first polygon, the second polygon and the polygonal intersection are represented by data indicating a list of edges.

3. The method of claim 2 wherein the edges represent the boundaries of the polygons.

4. The method of claim 2 wherein the edges in the list of edges are consistently ordered in either a clockwise or counterclockwise direction.

5. The method of claim 2 wherein a hole located in the first polygon is represented by data indicating a list of edges.

6. The method of claim 5 wherein the edges in the list of edges that represent a hole are ordered in an opposite direction to the direction used to order the edges in the list of edges used to represent the first polygon.

7. The method of claim 2 wherein the edges in the list of edges are consistently ordered in a clockwise direction.

8. The method of claim 1 wherein the first polygon and the second polygon represent two-dimensional geographic features.

9. The method of claim 1 wherein the steps of determining are performed by a software program that uses a geographic database containing data representations of the first polygon and the second polygon.

10. The method of claim 1 wherein the portion of the boundary of the first polygon that is located inside the second polygon is determined by comparing an angle formed by the portion of the boundary of the first polygon with portions of the boundary of the second polygon formed by the intersection.

11. The method of claim 1 wherein the intersection of the boundary of the first polygon with the boundary of the second polygon is found by searching a rectangular area formed by an intersection of a first minimum bounding rectangle encompassing the first polygon and a second minimum bounding rectangle encompassing the second polygon.

12. The method of claim 1 further comprising:

determining an additional polygonal intersection of the first polygon and the second polygon by performing the determining steps for any additional intersection of the boundary of the first polygon with the boundary of the second polygon which is not already part of the polygonal intersection of a first polygon and a second polygon already determined.

13. The method of claim 1 wherein the steps of determining are performed on a server connected to the Internet and that provides navigation-related services to users.

14. A program for determining a polygonal intersection of a first polygon and a second polygon, wherein said program is stored on a computer-readable medium, said program comprising:

program code that determines a first known portion of a boundary of the polygonal intersection as being comprised of a portion of a boundary of the first polygon that is located inside the second polygon at an intersection of the boundary of the first polygon with a boundary of the second polygon; and

program code that determines each subsequent portion of the boundary of the polygonal intersection that connects to a current known portion of the boundary of the polygonal intersection by selecting that portion of the boundary either the first polygon or the second polygon that connects to a leading end of the current known portion of the boundary of the polygonal intersection and that forms a minimum rotation angle therewith.

15. The invention of claim 14 wherein said program is run on a server connected to the Internet that provides navigation-related services to users.

16. The invention of claim 14 wherein said polygons represent two dimensional geographic features.

17. The invention of claim 14 wherein said polygons are represented by data contained in a database that represents geographic features.

18. A method for determining a polygonal intersection of a first polygon and a second polygon represented by data contained in a geographic database,

wherein a boundary of the first polygon is represented by a first list of links connected at endpoints thereof and the second polygon is represented by a second list of links connected at endpoints thereof,

wherein an endpoint of a link is represented by either a node or a shape point;

wherein each location at which the boundary of the first polygon intersects with the boundary of the second polygon is represented by a node;

wherein the links contained in the first list of links are in an order corresponding to a consistent direction of traversal of the corresponding links representing the boundary of the first polygon;

wherein the links contained in the second list of links are in the order corresponding to the consistent direction of traversal of the corresponding links representing the boundary of the second polygon;

the method comprising the steps of;

determining a first minimum bounding rectangle that encompasses the first polygon;

determining a second minimum bounding rectangle that encompasses the second polygon;

determining that the first minimum bounding rectangle and the second minimum bounding rectangle intersect;

identifying all the links located entirely in a first polygonal area formed by an intersection of the first minimum bounding rectangle and the second minimum bounding rectangle that have at least one node at an endpoint thereof;

associating in a node-link map each node connected to each of the identified links with each of the links connected thereto;

identifying a node from the node-link map that has at least three links connected thereto;

from the order of two of said at least three links that belong to one of the polygons, determining which one of said at least three links that belong to the other of polygons is located inside the one of said polygons;

using the link that is located inside the one of said polygons as a starting link for the polygonal intersection of the first polygon and the second polygon; and

determining each other link of the polygonal intersection by selecting from the links that connect to a currently known link at the end thereof according to the consistent direction of travel that link that forms a minimum rotation angle with the currently known link.

19. The method of claim 18 wherein the steps of determining, associating, identifying and using are performed by a software program that uses the geographic database.

20. The method of claim 18 wherein the steps of determining, associating, identifying and using are performed on a server connected to the Internet and that provides navigation-related services to users.