Patent ID: 8990204
Filing Date: 2015-03-24
Classification: G06F

Abstract:
1. A computer-implemented method for determining in which of a multitude of at least partly contiguous spatial areas is located a given spatial point, the method comprising: (a) receiving an electronic query that includes spatial coordinates of the given spatial point; (b) reading or receiving from a computer-readable storage medium electronic indicia of a boundary dataset, said boundary dataset comprising, for each one of a multitude of piecewise-linear spatial boundary segments, a corresponding set of spatial coordinates of that spatial boundary segment, wherein (i) a closed, polygonal boundary of each spatial area comprises one or more of the boundary segments, (ii) each boundary segment forms a portion of the polygonal boundary of at most two adjacent spatial areas and separates those spatial areas, and (iii) the boundary dataset further comprises an indicator, for each spatial boundary segment, of the at most two corresponding adjacent spatial areas that are separated by that boundary segment; (c) using one or more computer processors programmed therefor and operatively coupled to the computer-readable storage medium, identifying boundary segments that intersect a line segment extending from the given spatial point to an arbitrary end point outside an aggregate area encompassed by the multitude of spatial areas; (d) using one or more computer processors programmed therefor, tabulating, for each boundary segment identified in part (c), the at most two adjacent spatial areas separated by that boundary segment; (e) identifying as the spatial area containing the given spatial point the spatial area tabulated in part (d) an odd number of times; and (f) storing electronic indicia or displaying visual indicia of the spatial area identified in part (e), wherein the set of spatial coordinates of each polygonal boundary or each boundary segment comprises spatial coordinates for a first vertex of that boundary or segment and offset coordinates for other vertices of that boundary or segment.