# US 12,498,250 B2 · Localization using tessellated grids

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,498,250 B2
- Document ID: US12498250B2
- Status: Granted
- Kind: B2
- Application number: 17/134,224
- Filed: 2020-12-25
- Published: 2022-06-30
- Granted: 2025-12-16
- Earliest claimed: 2020-12-25
- Assignees: Mapsted Corp.
- Applicants: Mapsted Corp.
- Inventors: Sean Huberman; Joshua Karon; Ahmed Mahmood
- Web page: https://patentgrep.com/patent/US12498250B2

## CPC

- G01C 21/383: {Indoor data}
- G01C 21/206: {specially adapted for indoor navigation}
- G06F 16/2246: {Trees, e.g. B+trees}
- H04W 4/029: Location-based management or tracking services
- H04W 4/33: for indoor environments, e.g. buildings
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

Examples for localization using tessellated grids are described. In an example, a plurality of physical entities can be identified in an indoor space and each physical entity can be georeferenced to a coordinate system. The indoor space can be divided into a grid of polygonal tiles abutting adjacent polygonal tiles, and arranged in a hierarchical structure with the tiles in one level of the hierarchical structure being substantially representable by polygonal tiles in other levels of the hierarchical structure. The grid is then spatially indexed by associating each physical entity with a polygonal tile from amongst the polygonal tiles in each hierarchical level, thereby correlating a georeference of the physical entity with the polygonal tile. Based on the spatial indexing, a grid map for the indoor space can be generated for localizing mobile devices in the indoor space.

## Claims

### Claim 1

A method comprising:
identifying a plurality of physical entities in an indoor space, wherein a physical entity represents a structural feature of the indoor space and is not a network source and a signal source;
georeferencing each of the physical entities to a coordinate system;
dividing the indoor space into a grid of a plurality of polygonal tiles abutting adjacent polygonal tiles, the grid comprising a hierarchical structure of the plurality of polygonal tiles, wherein a polygonal tile at a level in the hierarchical structure is representable by polygonal tiles at other levels in the hierarchical structure;
indexing, spatially, the grid with the physical entities in the indoor space, the indexing comprising associating each physical entity with a polygonal tile from amongst the plurality of polygonal tiles in each hierarchical level in the hierarchical structure to correlate a georeference of the physical entity with the polygonal tile in each hierarchical level;
implementing an identifier allocation scheme to associate an identifier with each of the plurality of polygonal tiles, the identifier having the georeference embedded therein, the identifier allocation scheme is based on parameters associated with the polygonal tile, the parameters including at least one of an orientation of the polygonal tile, a size of the polygonal tile, and polygonal tiles neighboring the polygonal tile; and
generating a grid map for the indoor space based on the indexing for localization of mobile devices in the indoor space, wherein spatial data of a mobile device is compared with a set of georeferences for the indoor space to identify a polygonal tile in which the mobile device is instantaneously located, the spatial data including sensor data obtained by the mobile device.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of polygonal tiles have a symmetrical hexagon shape.

### Claim 3 (depends on 1)

The method of claim 1, wherein the plurality of polygonal tiles have one of a same asymmetrical polygon shape and different symmetrical polygon shapes.

### Claim 4 (depends on 1)

The method of claim 1, wherein a first set of polygonal tiles in one hierarchical level in the hierarchical structure are symmetrical and of a first shape and a second set of polygonal tiles in another hierarchical level in the hierarchical structure are symmetrical and of a second shape, wherein a plurality of second set of polygonal tiles cover a single polygonal tile from the first set.

### Claim 5 (depends on 1)

The method of claim 1, wherein the indexing comprises spatially indexing child polygonal tiles from amongst the plurality of polygonal tiles hierarchically linked to a parent polygonal tile from amongst the plurality of polygonal tiles at a higher level in the hierarchical structure.

### Claim 6 (depends on 1)

The method as claimed in claim 1, wherein the physical entity representing the structural feature of the indoor space includes at least of walls, passages, hallways, elevator shafts, escalators, open spaces, doorways, kiosks, stores, alleys, holes, a café, and a salon.

### Claim 7 (depends on 1)

The method as claimed in claim 1, wherein based on association between the plurality of polygonal tiles on the grid map, analytics data is associated with the plurality of the polygonal tile to provide information pertaining to a selected polygonal tile.

### Claim 8

A server computing device comprising:
a processor; and
a memory storing a set of instructions, the set of instructions executable in the processor to:
identify a plurality of physical entities in an indoor space, wherein a physical entity represents a structural feature of the indoor space and is not a network source and a signal source;
georeferencing each of the physical entities to a coordinate system;
divide the indoor space into a grid of a plurality of polygonal tiles abutting adjacent polygonal tiles, the grid comprising a hierarchical structure of the plurality of polygonal tiles, wherein a polygonal tile at a level in the hierarchical structure is representable by polygonal tiles at other levels in the hierarchical structure;
index, spatially, the grid with respect to the physical entities in the indoor space, the indexing comprising associating each physical entity with a polygonal tile from amongst the plurality of polygonal tiles in each hierarchical level in the hierarchical structure to correlate a georeference of the physical entity with the polygonal tile in each hierarchical level;
implement an identifier allocation scheme to associate an identifier with each of the plurality of polygonal tiles, the identifier having the georeference embedded therein, the identifier allocation scheme is based on parameters associated with the polygonal tile, the parameters including at least one of an orientation of the polygonal tile, a size of the polygonal tile, and polygonal tiles neighboring the polygonal tile; and
localize mobile devices in the indoor space based on the indexing, wherein a grid map is generated to represent the indoor space based on the indexing, wherein spatial data of a mobile device is compared with a set of georeferences for the indoor space to identify a polygonal tile in which the mobile device is instantaneously located, the spatial data including sensor data obtained by the mobile device.

### Claim 9 (depends on 8)

The server computing device of claim 8, wherein the plurality of polygonal tiles have symmetrical hexagon shape.

### Claim 10 (depends on 8)

The server computing device of claim 8, wherein the plurality of polygonal tiles have one of same asymmetrical polygon shape and different symmetrical polygon shapes.

### Claim 11 (depends on 8)

The server computing device of claim 8, wherein a first set of polygonal tiles in one hierarchical level in the hierarchical structure are symmetrical and of a first shape and a second set of polygonal tiles in another hierarchical level in the hierarchical structure are symmetrical and of a second shape, wherein a plurality of second set of polygonal tiles cover a single polygonal tile from the first set.

### Claim 12 (depends on 8)

The server computing device of claim 8 further comprising instructions executable in the processor to index, spatially, with respect to the indoor space, child polygonal tiles from amongst the plurality of polygonal tiles hierarchically linked to a parent polygonal tile from amongst the plurality of polygonal tiles at a higher level in the hierarchical structure.

### Claim 13 (depends on 8)

The server computing device of claim 8, wherein the physical entity representing the structural feature of the indoor space includes at least of walls, passages, hallways, elevator shafts, escalators, open spaces, doorways, kiosks, stores, alleys, holes, a café, and a salon.

### Claim 14 (depends on 8)

The server computing device of claim 8, wherein based on association between the plurality of polygonal tiles on the grid map, analytics data is associated with the plurality of the polygonal tile to provide information pertaining to a selected polygonal tile.