Patent ID: 7426455

Claim:
A method for locating a geographical region using a digital computer, where the located region is the result of a Boolean operation among a first geographical region and a second geographical region, where the regions are represented as vector tuples, the method comprising: establishing indexing cells about the regions; classifying each indexing cell by the type of interaction between the regions, where the type of interaction includes (boundary, boundary), a (boundary, boundary) indexing cell containing a portion of the boundary of each region; for each (boundary, boundary) indexing cell: defining a pseudo-point at each entrance of each region boundary to the cell and each exit from the cell of each region boundary; categorizing the (boundary, boundary) indexing cell based on a relationship of its pseudo-points; identifying at least one starting point along the boundary of one of the regions based on: the categorization, a Boolean operation to be performed, and the interior convention of the vector tuples representation; accumulating result tuples, including tuples including pseudo points and intersections between region boundaries, encountered in tracing a cycle: from a first at least one starting point, along the first starting point region boundary; in the direction of the first starting point region boundary; and returning to the first starting point, wherein: upon encountering each intersection the cycle proceeds along the other region boundary, in the direction of the other region boundary, upon encountering a cell edge the cycle proceeds along the cell edge in the direction consistent with the interior convention of the vector tuple representation, and until the cycle is completed at the first starting point; upon completing a cycle where at least one of a starting point remains untraversed or an intersection between region boundaries remains untraversed, accumulating result tuples, including tuples including pseudo points and intersections between region boundaries, encountered in tracing a cycle: from a subsequent starting point at the first untraversed starting point or untraversed intersection between region boundaries along the subsequent starting point region boundary, in the direction of the subsequent starting point region boundary, and returning to the subsequent starting point, wherein: upon encountering each intersection the cycle proceeds along the other region boundary, in the direction of the other region boundary, upon encountering a cell edge the cycle proceeds along the cell edge in the direction consistent with the interior convention of the vector tuple representation, and until the cycle is completed at the subsequent starting point; discarding duplicate tuples and tuples comprising only cell edges, until all starting points and intersections of the region boundaries have been traversed, and displaying the located region as defined at least in part by the accumulated result tuples.