Back to results
US 6,208,352 B1Granted
Method for the computerized solution of the intersection of polygons
AssigneeGeneral Dynamics Government Systems Corporation
InventorBruce Hardy Blackwell
Life of this patent
Estimating the term…
Abstract
Methods and systems for the computerized solution of the intersection of polygons where the product polygon and subtracting polygon are represented by vertices in a product polygon linked list and a subtracting polygon linked list, respectively. In one aspect, the vertices in the product polygon linked list and the vertices in the subtracting polygon linked list have a different orientation.
Claims16
A method for subtracting a first subtracting polygon from a product polygon, comprising:
- determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list;
- inserting a first intersection node at the intersection in the product polygon linked list;
- inserting a second intersection node at the intersection in the first subtracting polygon linked list;
- creating a new linked list by performing the subsets of:
- determining a first vertex in the product polygon linked list,
- adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex,
- if an intersection node is encountered, adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node, and
- repeating the above subsets until returned to the determined first vertex;
- and
- replacing the product polygon linked list with the new linked list.
7 more elements
An apparatus for subtracting a first subtracting polygon from a product polygon, comprising:
- a memory for storing a program for
- determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list,
- inserting a first intersection node at the intersection in the product polygon linked list;
- inserting a second intersection node at the intersection in the first subtracting polygon linked list;
- creating a new linked list by performing the subsets of:
- determining a first vertex in the product polygon linked list,
- adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex,
- if an intersection node is encountered, adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node,
- repeating the above subsets until returned to the determined first vertex, and
- replacing the product polygon linked list with the new linked list;
- and
- a processor for running the program.
9 more elements
An apparatus for subtracting a first subtracting polygon from a product polygon, comprising:
- means for determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list,
- means for inserting a first intersection node at the intersection in the first subtracting polygon linked list;
- means for inserting a second intersection node at the intersection in the product polygon linked list;
- means for creating a new linked list including:
- means for determining a first vertex in the product polygon linked list,
- means for adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex, and
- means for adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node;
- and
- means for replacing the product polygon linked list with the new linked list.
6 more elements
A computer-readable medium whose contents cause a computer system to subtract a first subtracting polygon from a product polygon, by performing the steps of:
- determining an intersection of the first subtracting polygon and the product polygon, wherein the first subtracting polygon is represented by a plurality of vertices in a first subtracting polygon linked list and the product polygon is represented by a plurality of vertices in a product polygon linked list;
- inserting a first intersection node at the intersection in the product polygon linked list;
- inserting a second intersection node at the intersection in the first subtracting polygon linked list;
- creating a new linked list by performing the subsets of:
- determining a first vertex in the product polygon linked list,
- adding vertices from the product polygon linked list to the new linked list until the first intersection node is encountered by following the product polygon linked list from the determined first vertex,
- if an intersection node is encountered, adding vertices from the first subtracting product polygon linked list to the new linked list until a third intersection node is encountered by following the first subtracting polygon linked list from the second intersection node, and
- repeating the above subsets until returned to the determined first vertex;
- replacing the product polygon linked list with the new linked list.
6 more elements
Dependencies are inferred from the claim text.