Patent ID: 7277886

Claim:
A method of retrieving one or more points that are contained within a predetermined area, said method comprising: (i) retrieving data identifying a region, the region encompassing one or more points and being associated with linking data which, for each region, identifies the point or points encompassed by that region; (ii) performing a process in respect of the region, the process comprising: comparing extents of the region with extents of the predetermined area in order to establish whether the region overlaps with the predetermined area; if there is overlap, retrieving data identifying sub-regions of the region and identifying any such sub-regions whose extents are wholly within the predetermined area; (iii) for each sub-region, repeating the process until all sub-regions thereof falling wholly within the predetermined area are identified, and (iv) accessing linking data corresponding to the identified sub-regions to retrieve points encompassed by the sub-regions wherein: the area represented by the total set of points is first divided into top level quads; each quad is examined for the presence of points; quads which do not contain points are not considered further; the boundaries of quads which do contain one or more points are shrunk wrapped around the set of contained points; if the quad only contains a single point, then the shrink wrapping reduces to zero, the point is associated with that quad and processing ends for that particular quad; where more than one point is present in a quad, the shrunk wrap area is divided into first level sub quads and the shrink wrap procedure is repeated on each of the first level sub-quads; and subsequent lower level sub-quads are produced until each point is associated with a single quad.