Method for constructing polygons used to represent geographic features

• US 20030132932A1
• Filed: 09/17/2001
• Published: 07/17/2003
• Est. Priority Date: 09/17/2001
• Status: Abandoned Application

• Current Assignee: Navteq B.V. (HERE Holding Corporation)
• Original Assignee: Navteq B.V. (HERE Holding Corporation)
• Inventors: Yang, Xiangheng
• Application Number:
  US09/953,656
• Publication Number:
  US 20030132932A1
• Time in Patent Office: Days
• US Class Current: 345/418
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

A method for constructing a polygon from data representations of a given plurality of links. A first point of a candidate polygon is determined by selecting a point located on one of the given plurality of links. Then, a first known link that forms part of the boundary of a candidate polygon is determined to be that link upon which the first point is located. The orientation of the first known link is determined. Then, each subsequent known link that forms part of the boundary of the candidate polygon is determined by selecting from the given plurality of links that link (1) that connects to an end of a known link in a chosen direction and (2) that forms a minimum rotation angle therewith in a chosen rotational direction. After determining that the candidate polygon is a complete polygon, any links from the given plurality of links that are not shared by the complete polygon with any other candidate polygon are removed from the given plurality of links. The process continues until all the links of the given plurality of links are removed. The process also determines all links that do not form part of any complete polygon.

Claims

1. A method for constructing polygons from data representations of a given plurality of links, comprising:

(a) determining a first point, wherein said first point is located on one of said given plurality of links;

(b) determining as a first known link that forms part of the boundary of a candidate polygon a link upon which the first point is located;

(c) determining an orientation of said first known link;

(d) determining each subsequent known link that forms part of the boundary of the candidate polygon by selecting from the given plurality of links that link that connects to a chosen ordered end of a known link and that forms a minimum rotation angle therewith in a chosen rotational direction; and

(e) after determining that the candidate polygon is a complete polygon, removing from the given plurality of links any links that are not shared by the complete polygon with any other candidate polygon.

2. The method of claim 1 wherein said first point is at an extreme in a chosen direction.

3. The method of claim 2 wherein the chosen direction is south.

4. The method of claim 1 wherein the candidate polygon is determined to be a complete polygon when the first known link is encountered during the step of determining each subsequent known link.

5. The method of claim 1 further comprising:

determining that a series of one or more links do not form a complete polygon when no link of said given plurality of links is determined to be connected to the chosen ordered end of a known link.

6. The method of claim 1 further comprising:

returning to a calling application data indicating the links of said given plurality of links that do not form part of at least one complete polygon.

7. The method of claim 1 further comprising:

returning to a calling application data indicating all the complete polygons formed of the given plurality of links.

8. The method of claim 7 wherein each complete polygon is represented by a list of links that form a boundary of the complete polygon and wherein the links in the list are in an order that conforms to the order in which the links connect to each other to form the boundary of the polygon in a clockwise direction.

9. The method of claim 1 wherein the polygons represent two-dimensional geographic features.

10. 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 polygons.

11. 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.

12. A program for constructing one or more polygons from data representations of a given plurality of links, wherein said program is stored on a computer-readable medium, said program comprising:

program code that determines a first point, wherein said first point is located on one of said given plurality of links;

program code that determines as a first known link that forms part of the boundary of a candidate polygon a link upon which the first point is located;

program code that determines an orientation of said first known link;

program code that determines each subsequent known link that forms part of the boundary of the candidate polygon by selecting from the given plurality of links that link that connects to a chosen ordered end of a known link and that forms a chosen rotation angle therewith in a chosen rotational direction; and

program code that removes from the given plurality of links any links that are not shared by the complete polygon with any other candidate polygon after determining that the candidate polygon is a complete polygon.

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

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

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

16. The invention of claim 12 wherein the program code is executed on a server connected to the Internet that provides navigation-related services to users.