Method for determining the intersection of polygons used to represent geographic features
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
37 Citations
20 Claims
-
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 Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A program on a computer readable medium for determining a polygonal intersection of a first polygon and a second polygon, 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 program comprising:
-
program code that determines 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 at an intersection of the boundary of the first polygon with the boundary of the second polygon; and
program code that determines a subsequent portion of the boundary of the polygonal intersection where a leading end of the current known portion of the boundary of the polygonal intersection connects to two other links 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 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 Dependent Claims (15, 16, 17)
-
-
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 each link located entirely in a first polygonal area formed by an intersection of the first minimum bounding rectangle and the second minimum bounding rectangle that has at least one node at an endpoint of said link;
associating in a node-link map each node connected to each identified link with each link to which the node is connected;
identifying a node from the node-link map that has at least three links connected to it;
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 as 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 a link that connects to a currently known link in a selected direction of traversal and where a leading end of a currently known portion of the polygonal intersection in the selected direction of traversal connects to two other links, selecting that link that forms a minimum rotation angle in a selected rotational direction with the currently known link, wherein the selected rotational direction is opposite to the selected direction of traversal. - View Dependent Claims (19, 20)
-
Specification