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 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.
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
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. - 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 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. - View Dependent Claims (19, 20)
-
Specification