Enhanced spatial index for point in polygon operations
AssigneePitney Bowes Inc.
InventorsAnand Kannan, Andy Kane
Life of this patent
Estimating the term…
Abstract
An improved method is provided for determining whether a sample point is within a defined geographic area. Indexes for the geographic area of interest are generated in advance. Such indexes complement the traditional spatial indexing techniques such as quad tree and r-tree. The geographic area, as defined by an outer boundary, is subdivided into some regular geometric shape, preferably a rectangle, encoded into a suitable form, and indexed. Then, a simplified comparison of the sample point to the indexed regular shapes is made.
Claims16
A computer implemented method for determining whether a sample point is within a geographic area by generating indices for subdivided areas within the geographic area, and the geographic area having a defined boundary, the method comprising;
- defining a rectangular boundary box that encloses the geographic area:
- dividing the boundary box into a plurality of equal first level rectangular boxes at a first dividing level;
- determining for each of the first level boxes whether the first level box is (a) entirely outside the geographic area;
- (b) entirely inside the geographic area or (c) intersecting with the defined boundary;
- for each of the first level boxes performing the following indexing steps:
- if the first level box is (a) entirely outside the geographic area, then that box is discarded and it is not part of the indices;
- if the first level box is (b) entirely inside the geographic area, then that box is added to the indices and is assigned an index number that is stored with the corresponding range of coordinates for that box;
- if the first level box is (c) intersecting with the defined boundary then dividing that box into a plurality of equal second level rectangular boxes at the second dividing level;
- repeating the determining and indexing steps for each of the second level boxes as described above for the first level boxes.
A computer implemented method for determining whether a sample point is within a geographic area by generating indices for subdivided areas within the geographic area, and the geographic area having a defined boundary, the method comprising:
- defining a geometric boundary shape that encloses the geographic area;
- dividing the boundary shape into a plurality of equal first level shapes at a first dividing level;
- determining for each of the first level shapes whether the first level shape is (a) entirely outside the geographic area;
- (b) entirely inside the geographic area;
- or (c) intersecting with the defined boundary:
- for each of the first level shapes performing the following indexing steps:
- if the first level shape is (a) entirely outside the geographic area, then that shape is discarded and it is not part of the indices;
- if the first level shape is (b) entirely inside the geographic area, then that shape is added to the indices and is assigned an index number that is stored with the corresponding range of coordinates for that shape;
- if the first level shape is (c) intersecting with the defined boundary then dividing that shape into a plurality of equal second level shapes at the second dividing level;
- repeating the determining and indexing steps for each of the second level shapes as described above for the first level shapes.
Dependencies are inferred from the claim text.