Shared electric bikes have been steadily growing in popularity in these years, with many new developments and trends emerging in the market. However, it also brought many problems, one of them being the regulation of riding.
As the demand increases, many dockless bicycles system grow coverage very quickly. However, dockless systems still need to be load balanced and they have faced criticism because of vandalism and unregulated use of public spaces, such as sidewalks, front of the door and car parks.
1. Geofence
A geofence may be a good choice to solve and improve the above issues. A geofence is a kind of virtual boundary or perimeter on the map representing a real-world area. Paired with GPS or RFID equipment on the bike, the geofence could be used to define a specific area or zone that may mean different geofence commands, such as parking areas, no parking areas, low-speed areas and so on.
The main idea of implementing the above function is to determine the spital relation of the bike and the great number of geofences. Technically, there are so many approaches and solutions to achieve that, this page, would introduce an approach base on the GeoHash algorithm and Redis storage to build a high-performance geofence index for queries.
2. System Design
2.1 GeoHash
First, this page would introduce the GeoHash algorithm – a unique encoding method for geography location, it always used in spatial querying. It is a hierarchical spatial data structure which subdivides space into buckets of grid shape, which means if we want to represent a point by geoHash, the map would recursively divide into smaller and smaller grids till the precision level we wanted.
And then, as our desired precision (Level 7), the geohash encode value will look like a quaternary string:
1 | 28 29 4 14 10 19 11 |
For exact latitude and longitude translations Geohash is a spatial index of base4. To be a compact code it uses base 32 and represents its values by the following alphabet, that is the “standard textual representation”.
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
| Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
The geohash code of the quaternary string is: wx4fbmc, which represents an area in Beijing.
Till now, we got an encoding method for the spatial data. And the following page would introduce how it works to implement geofence query.
2.2 Redis
Redis is an open-source, in-memory KV data structure store that is used as a database or cache. It is often referred to as a data structure server because it allows users to store, retrieve, and manipulate data structures such as lists, sets, and hashes.
Redis is known for its high performance and scalability, and it is often used in high-traffic web applications and real-time systems. One of the reasons for its speed is that it stores all its data in RAM, making it faster to read and write than traditional disk-based databases.
Overall, Redis is a powerful and flexible tool for managing data, so in this project, it was used for data storage.
2.3 Geo index implementation
The fundamental concept behind implementing geofence spatial search is to use geohash values as an index. To begin with, we must calculate the geohash encoded value of the geofence. In other words, we need to determine the specific blocks of geohash that cover the geofence.
As the figure below, we can find that 6 geohash blocks overlap with the target geofence, and the geohash (level 7) code of the blocks are: gcpvhed, gcpvhee, gcpvhe8, gcpvhef, gcpvheg, gcpvhe9.
To determine the spatial relationship of a point with geofences, a possible approach is to calculate the geohash value of the point. This value can be used to retrieve all the geofences that share the same geohash value, indicating a potential intersection with the point. By focusing on this subset of geofences, it is then possible to calculate the spatial relationship of the point with each one of them. This strategy is similar to using indexes and allows for finding a small number of relevant geofences with higher efficiency.
Storing the geohash value of a fence in Redis can be an effective strategy. A suitable data structure for this purpose is Sets in Redis. To illustrate this approach, consider a geofence with an ID of 123. In this case, the geohash value of the fence can be stored in Redis, as shown in the figure below.
If another geofence shared the same geohash value with the fence, just append the id to the corresponding value in the Redis. This approach leverages the data structure of Sets in Redis to efficiently store and retrieve multiple geofences that have the same geohash value.
The last thing needed to do is determin the spatial relationship of the point with a single geofence. This part is not the focus of the content introduced in this article, please refer to my another post Using Ray Casting Algorithm to determine if a point inside a polygon