×

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

  • US 6,917,877 B2
  • Filed: 08/14/2001
  • Issued: 07/12/2005
  • Est. Priority Date: 08/14/2001
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for determining a polygonal intersection of a first polygon and a second polygon represented by data contained in a geographic database, wherein the first polygon has a boundary comprised of a series of links ordered in a known rotational direction and the second polygon has a boundary comprised of a series of links ordered in the known rotational direction, the method comprising:

  • at an intersection of the boundary of the first polygon with the 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, wherein the portion of the boundary of the first polygon that is located inside the second polygon is comprised of one or more links; and

    where a leading end of the current known portion of the boundary of the polygonal intersection connects to two other links, determining a subsequent portion of the boundary of the polygonal intersection by selecting that portion of the boundary of either the first polygon or the second polygon that connects to the leading end of the current known portion of the boundary of the polygonal intersection and that forms a minimum rotation angle in the rotational direction with the current known portion of the boundary of the polygonal intersection if the direction of traversal of the current known portion of the boundary of the polygonal intersection is opposite the known rotational direction or that forms a minimum rotation angle in the opposite rotational direction with the current known portion of the boundary of the polygonal intersection if the direction of traversal of the current known portion of the boundary of the polygonal intersection is the same as the known rotational direction.

View all claims
  • 5 Assignments
Timeline View
Assignment View
    ×
    ×