11.1 Geospatial Data Structures

How do you efficiently answer questions like "What restaurants are within 5km of me?" Scanning every restaurant on Earth for each query is absurd. Geospatial data structures solve this by organizing 2D (or 3D) spatial data so you can query regions, nearest neighbors, and intersections in milliseconds instead of seconds.

B-Trees — The Foundation

Before understanding any geospatial data structure, you need to understand the B-Tree. It is the most important data structure in databases, and every spatial index either is a variant of a B-Tree or tries to become one.

What Is a Database?

A database is software that stores data and lets you search it quickly.

Example table:

ID    Name    Age    Latitude    Longitude
1     Alice   25     40.7128     -74.006
2     Bob     31     40.7210     -74.002
3     John    22     40.7001     -73.998

What Is an Index?

Think of a textbook.

• Without an index: You search every page.
• With an index: You jump directly to the page.

Database indexes work exactly the same way. Instead of reading millions of rows, they jump directly to the data.

What Is a B-Tree?

A B-Tree is a special tree that keeps data sorted. It is the workhorse behind virtually every database you will ever use — PostgreSQL, MySQL, SQLite, they all use B-Trees for their primary indexing.

Imagine ages stored in a B-Tree:

         [  24  ]
        /       \
   [18,21]     [27,30]
   / | \       / | \
 18 19 20-21 22-23 24-26 27-29 30

Everything is in order. So if someone asks:

"Find everyone between age 20 and 30."

The database:

1. Jumps directly to 20
2. Reads until 30
3. Done

Very fast. One seek and a short read.

Why Is a B-Tree the Prize?

The B-Tree is the one data structure databases have spent 50 years tuning:

If you can squeeze your problem into a B-Tree shape, you inherit all of that for free.

Why Is Age Fast but Location Slow?

Age is one-dimensional (1D). It's just one number:

18   19   20   21   22   23   24   25   26   27   28   29   30
 |    |    |    |    |    |    |    |    |    |    |    |    |

Sorting is easy. Nearby ages stay together on disk.

Location has TWO numbers — latitude and longitude. You need both to compute distance. And sorting on just one of them breaks the closeness relationship we care about (see the introduction above).

This is the fundamental problem that every spatial index in this guide is trying to solve: how to make 2D location data behave as if it were in a B-Tree.

Latitude & Longitude — The Foundation

Before understanding any geospatial data structure, you must understand latitude and longitude, because every GPS location is stored as these two numbers.

Imagine the Earth as a Globe

The Earth is a sphere. Now imagine drawing imaginary lines all over it:

• Latitude lines — horizontal (east-west)
• Longitude lines — vertical (north-south)

Together they form a giant grid, like rows and columns in a spreadsheet.

          North Pole
               ●
             |   |   |      ← Longitude lines
      -------+---+-------
      -------+---+-------  ← Latitude lines
      -------+---+-------
             |   |   |
               ●
          South Pole

Every place on Earth can be found by giving one latitude and one longitude — exactly like giving a house address.

Latitude (North-South Position)

Latitude tells how far north or south you are from the Equator.

           North Pole
             +90°
               ●

      60° N ----------
      30° N ----------

Equator 0° ============
               ↑

      30° S ----------
      60° S ----------

               ●
             -90°
          South Pole

Values:

• North Pole = +90°
• Equator = 0°
• South Pole = −90°

Latitude always ranges from −90° to +90°

Examples:

• New York: 40.7128 → about 40.7° north of the Equator
• Mumbai: 19.0760 → about 19° north of the Equator
• Sydney: −33.8688 → negative means south of the Equator

Longitude (East-West Position)

Longitude tells how far east or west you are from the Prime Meridian (an imaginary line passing through Greenwich, England).

                 North Pole
                      ●
                      |
                      | 0°
                      |
                      |
West -----------------+---------------- East
        -180°         |          +180°
                      |
                      |
                      ●
                 South Pole

Values go from −180° to +180°

• Negative = West
• Positive = East

Examples:

• New York: −74.006 → about 74° west of the Prime Meridian
• Mumbai: 72.8777 → about 73° east of the Prime Meridian

Every Location Has Two Numbers

Think of a spreadsheet:

• Rows tell you up and down (latitude)
• Columns tell you left and right (longitude)

Together they uniquely identify a location:

Easy Way to Remember

• Latitude → North ↕ South (horizontal lines, values from −90° to +90°)
• Longitude → West ↔ East (vertical lines, values from −180° to +180°)
• A location is always (latitude, longitude)
• Example: Mumbai = (19.0760, 72.8777)

A geohash is simply a compact string that encodes those two coordinates — and the longer the string, the more precisely it identifies the location.

QuadTrees

The Problem

Imagine you have 10 million points on a map (restaurants, gas stations, users). A user asks: "Find all coffee shops within 500 meters of me."

Without spatial indexing:

Scan ALL 10 million points
For each: calculate distance to user
Filter: keep only those within 500m
Result: 12 coffee shops
Time: ~2 seconds (brute force)

That's terrible. A user staring at a spinner for 2 seconds? Unacceptable.

How QuadTrees Work

A QuadTree recursively divides a 2D space into 4 quadrants. Think of it like a map that keeps zooming into smaller regions.

The Mental Model:

Imagine a pizza.

You cut it into 4 slices (quadrants).

Each slice that's too crowded? Cut it into 4 more.

Keep cutting until each quadrant has ≤ N points.

That's a QuadTree.

Visual Example

Step 1: Start with the entire world map
┌─────────────────────────────┐
│           10M points         │
│         (too many!)          │
└─────────────────────────────┘

Step 2: Split into 4 quadrants
┌──────────┬──────────┐
│ NW: 2M   │ NE: 3M   │
│ points   │ points   │
├──────────┼──────────┤
│ SW: 2.5M │ SE: 2.5M │
│ points   │ points   │
└──────────┴──────────┘

Step 3: Each quadrant too crowded → split again
┌────┬────┬──────────┐
│ NW │ NW │ NE: 3M   │
│ 1  │ 2  │ points   │
│ 1M │ 1M │ ┌───┬──┐ │
├────┼────┤ │NE │NE│ │
│ SW │ SW │ │ 1 │ 2│ │
│ 1  │ 2  │ │1.5│1.5│ │
│1.2M│1.3M│ └───┴──┘ │
└────┴────┴──────────┘

Step 4: Keep splitting until each leaf ≤ N points

Data Structure

class QuadTreeNode:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary      # {x, y, width, height}
        self.capacity = capacity      # Max points per node
        self.points = []              # Points in this quadrant
        self.children = []            # NW, NE, SW, SE (or empty)
    
    def insert(self, point):
        if not self.contains(point):
            return False
        
        if len(self.points) < self.capacity:
            self.points.append(point)
            return True
        
        if not self.children:
            self.subdivide()
        
        for child in self.children:
            if child.insert(point):
                return True
        return False
    
    def subdivide(self):
        x, y, w, h = self.boundary
        nw = QuadTreeNode((x, y, w/2, h/2))
        ne = QuadTreeNode((x + w/2, y, w/2, h/2))
        sw = QuadTreeNode((x, y + h/2, w/2, h/2))
        se = QuadTreeNode((x + w/2, y + h/2, w/2, h/2))
        self.children = [nw, ne, sw, se]
    
    def query(self, range_boundary):
        results = []
        if not self.intersects(range_boundary):
            return results
        
        for point in self.points:
            if range_boundary.contains(point):
                results.append(point)
        
        for child in self.children:
            results.extend(child.query(range_boundary))
        
        return results

Query Flow

User at (40.7128, -74.0060) asks: "coffee shops within 500m"

1. Create search circle around user location
2. Start at root of QuadTree
3. If node doesn't intersect circle → skip (huge optimization!)
4. If node is leaf → check each point in node
5. If node has children → recurse into children that intersect
6. Return all matching points

Time complexity: O(log n + k) where k = number of results
vs. Brute force: O(n)

QuadTree Properties

When to Use QuadTrees

• Map tile rendering: Google Maps uses QuadTrees to load only visible tiles
• Collision detection: Game engines detect nearby objects
• Spatial indexing: "Find all points in this rectangle"
• Image compression: JPEG uses QuadTree-like decomposition

Limitations

1. Not great for clustered data: If all points are in one corner, one branch gets very deep
2. Static data only: Moving a point requires delete + reinsert
3. No overlap handling: Points at boundaries need special handling
4. Rectangle queries only (natively): Circular queries require extra logic

Why Can't a QuadTree Naturally Group a Park?

This is one of the most common questions when learning spatial indexing. The key difference is what is being divided.

QuadTree divides the space. It doesn't care where the objects are initially. It simply says:

"Take the world and split it into 4 equal squares."

+---------+---------+
|         |         |
|    NW   |   NE    |
|         |         |
+---------+---------+
|         |         |
|    SW   |   SE    |
|         |         |
+---------+---------+

Then each square is split again:

+----+----+----+----+
|    |    |    |    |
+----+----+----+----+
|    |    |    |    |
+----+----+----+----+
|    |    |    |    |
+----+----+----+----+
|    |    |    |    |
+----+----+----+----+

The divisions are fixed. They happen whether there are objects there or not.

Now imagine a park shaped like this:

##############
##############
##############

Overlay a QuadTree grid:

+-----+-----+
|#####|#####|
|#####|#####|
+-----+-----+
|#####|#####|
|#####|#####|
+-----+-----+

The park doesn't fit neatly inside one square. It spans multiple squares. So the QuadTree has to store references to the park in several nodes.

Now imagine a river:

~~~~~~~~~~~~~~~~~~~~~~~~

A QuadTree grid might look like:

+---+---+---+---+
|~~~|~~~|   |   |
+---+---+---+---+
|   |~~~|~~~|~~~|
+---+---+---+---+
|   |   |~~~|~~~|
+---+---+---+---+

The river crosses many squares. Instead of one place, it's spread across lots of nodes. Searching becomes less efficient.

R-Tree does something different. Instead of dividing the map first, an R-Tree looks at the objects themselves.

Suppose these parks are close together:

• Park A
• Park B
• Park C

The R-Tree says, "These are nearby. I'll put them in one group." Then it draws one rectangle around them:

+------------------+
| Park A           |
|                  |
| Park B           |
|                  |
| Park C           |
+------------------+

No unnecessary splitting. The rectangle is based on where the objects actually are.

Another Example: Imagine a city where buildings are concentrated downtown, and outside the city is mostly empty farmland.

QuadTree: It still divides everything:

+---+---+---+---+
|   |   |   |   |
+---+---+---+---+
|   |XXX|XXX|   |
+---+---+---+---+
|   |XXX|XXX|   |
+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

Notice all the empty squares. The QuadTree still has them.

R-Tree: The R-Tree ignores the empty farmland. It simply creates a rectangle around the buildings:

         +---------+
         | XXXXXXX |
         | XXXXXXX |
         +---------+

Much less wasted space.

The biggest conceptual difference:

A simple analogy: Imagine organizing books in a library.

• QuadTree: You first divide the room into equal floor tiles and say, "Every book belongs to the tile(s) it occupies." A large bookshelf may span several tiles.
• R-Tree: You ignore the floor tiles and instead group related books onto shelves, then label each shelf with the range of books it contains. When someone asks for a book, you check the shelf labels first.

That's why R-Trees are generally preferred for GIS databases and map data containing irregular shapes like parks, lakes, rivers, and country boundaries, while QuadTrees excel at organizing uniformly distributed point data.

KD Trees

The Idea

One year after the QuadTree (1975), the same researcher, Jon Bentley, came up with a binary cousin called the KD Tree (short for k-dimensional tree).

The key difference: instead of splitting all dimensions at once into four quadrants, alternate one dimension per level.

How KD Trees Work

Level 0: Split on X (longitude)
         |
         |

Level 1: Split on Y (latitude)
         -----

Level 2: Split on X again
         |

Level 3: Split on Y again
         -----

... and so on, cycling through dimensions.

Visual Example

Step 1: Split on longitude (vertical line)
┌─────────────────────────────┐
│                |             │
│     A         |      B      │
│                |             │
└─────────────────────────────┘

Step 2: Left side splits on latitude (horizontal line)
┌─────────────────────────────┐
│         -------             │
│     A   |       |    B      │
│         -------             │
└─────────────────────────────┘

Step 3: Right side splits on latitude
┌─────────────────────────────┐
│         -------             │
│     A   |   C   |----       │
│         -------     |  D    │
│                     ----    │
└─────────────────────────────┘

You get a binary tree for multi-dimensional data that's balanced (if you split at the median).

Query Flow

To find points near a location:

1. Start at the root
2. At each node, compare the query point against the split dimension
3. Go to the child that contains the query point
4. After reaching a leaf, check if the other branch could contain closer points (by comparing the distance to the split line)
5. If yes, recurse into that branch too

KD Tree Properties

Limitations

The same disk problem as QuadTrees. KD Trees use pointers everywhere. There's no clean mapping to disk pages.

In RAM:  Following pointers is cheap (nanoseconds)
On disk: Every pointer might point to a page you haven't loaded (milliseconds)

A few hops in and you're spending most of your query time
waiting on the disk instead of doing useful work.

KD Trees are great in memory but painful off of it.

BKD Trees (Block KD Trees)

The Modern Fix

The BKD Tree (Block KD Tree) solves the disk problem of regular KD Trees.

Instead of one point per node, points get packed into blocks sized to a disk page.

Regular KD Tree:           BKD Tree:
                           
Node → point               Block → [point, point, point, point, point]
Node → point               Block → [point, point, point, point, point]
Node → point               Block → [point, point, point, point, point]
Node → point               Block → [point, point, point, point, point]

Each node = 1 point        Each block = disk page size
Many random reads          Fewer, sequential reads

How BKD Trees Work

1. Batch build: Points are sorted and packed into page-sized blocks
2. Tree structure: Blocks are organized into a tree (like a KD Tree but with blocks instead of single points)
3. Query: Descend the tree, reading entire blocks at a time from disk

Why It's Faster

Regular KD Tree query:
  Read node (disk seek) → Read node (disk seek) → Read node (disk seek)
  3 seeks × 10ms each = 30ms

BKD Tree query:
  Read block (disk seek) → Read block (disk seek)
  2 seeks × 10ms each = 20ms
  But each block contains many points, so you check more per read

Who Uses BKD Trees?

Elasticsearch uses BKD Trees for their numeric and geo fields. When you run a geo-query in Elasticsearch, you're hitting a 50-year-old algorithm with a disk-friendly wrapper.

Limitation

BKD Trees are basically write-once. They're designed for immutable segments. That makes them a bad fit for data that changes a lot — like Uber where you have many moving drivers constantly updating their location.

R-Trees

The Problem with QuadTrees

QuadTrees work great for points. But what if your data has extent — bounding boxes, rectangles, regions?

QuadTree can handle:    Restaurant at (40.71, -74.00)
                        → Point query works

R-Tree can handle:      Central Park (polygon covering ~3.4 km²)
                        → Must index the ENTIRE REGION, not just a point

The fundamental issue: A QuadTree divides space into fixed squares. If a park, river, or road spans multiple squares, it must be stored in multiple nodes. An R-Tree doesn't divide space — it groups objects based on where they actually are, creating bounding rectangles around them. This makes R-Trees much more efficient for real-world geographic data like parks, lakes, roads, and country borders.

How R-Trees Work

An R-Tree is a balanced tree (like a B-Tree) where each node contains bounding rectangles instead of just keys.

The Mental Model:

Think of packing boxes for a move.

You have items scattered around your house.
You group nearby items into boxes.
You label each box with what's inside.

When someone asks "Where's the coffee mug?":
  1. Check box labels (which box might contain it?)
  2. Open only that box
  3. Find the mug

R-Tree does the same thing with geographic regions.

Beginner Explanation (Without Code)

Imagine you have a huge map of the world with millions of locations, roads, lakes, buildings, and country borders. If someone asks:

"Which objects are inside this area?"

You do not want to check every single object one by one. That would be extremely slow.

An R-Tree is a special data structure that helps computers quickly find geographic objects by organizing them into groups based on their location.

Start with a Simple Example

Imagine your bedroom is messy. Items are scattered everywhere:

• Books
• Clothes
• Chargers
• Shoes
• Headphones
• Pens

Your mom asks, "Where are the headphones?"

Method 1: Check everything Look under the bed. Look inside every drawer. Open every cupboard. Search every shelf. Eventually you'll find them. This works, but it's slow.

Method 2: Put similar things into boxes Instead, you organize your room:

• One box contains books
• Another contains clothes
• Another contains electronics

Now someone asks, "Where are the headphones?" You immediately think, "They're electronics." You only open one box. You don't waste time searching everywhere.

This is exactly how an R-Tree works. Instead of grouping household items, it groups objects that are close together geographically.

Think About a World Map

Imagine the Earth contains millions of geographic objects:

• Cities
• Rivers
• Lakes
• Roads
• Buildings
• Parks
• Country borders

Instead of storing all of them in one giant list, the R-Tree organizes them into groups:

World
│
├── North America
├── Europe
├── Asia
└── Africa

Each group contains only objects in that region. It keeps dividing:

North America
│
├── Canada
├── USA
└── Mexico

USA
│
├── East Coast
├── West Coast
├── South
└── Midwest

East Coast
│
├── New York
├── Boston
├── Washington
└── Philadelphia

New York
│
├── Central Park
├── Empire State Building
├── Times Square
└── Brooklyn Bridge

Notice something: You are not checking every object in America. You keep narrowing down the search.

What is a Bounding Box?

This is the most important idea in an R-Tree. Every group has an invisible rectangle around it.

        +----------------------+
        |                      |
        |   Central Park       |
        |                      |
        | Empire State         |
        |                      |
        | Brooklyn Bridge      |
        |                      |
        +----------------------+

The rectangle enclosing all these landmarks is called a Minimum Bounding Rectangle (MBR) or Bounding Box. It is simply the smallest rectangle that completely covers all the objects in that group.

For Europe, there is another large rectangle. For Asia, another. For every city, another. For every neighborhood, another.

Every node in the R-Tree stores one of these rectangles.

Why are Bounding Boxes Useful?

Suppose someone asks: "Show me everything inside California."

The computer looks at the top level:

World
  North America □
  Europe □
  Asia □
  Africa □

California is obviously not inside Europe. So Europe is skipped. Africa is skipped. Asia is skipped. Only North America is searched.

Already, millions of objects have been ignored.

Inside North America:

  Canada □
  USA □
  Mexico □

California isn't in Canada. Skip. Not in Mexico. Skip. Only USA remains.

Inside USA:

  East Coast □
  West Coast □
  South □
  Midwest □

California is on the West Coast. The other three regions are ignored.

The search keeps getting smaller and smaller. Instead of checking millions of objects, maybe only a few thousand need to be examined.

This is why R-Trees are fast.

How Does the Computer Know Which Groups to Skip?

It compares rectangles.

Imagine your search area is shown in red:

+------------------------+
|                        |
|      Search Area       |
|                        |
+------------------------+

Now imagine another rectangle representing Texas:

+--------+
|        |
| Texas  |
|        |
+--------+

The two rectangles don't touch. So every object inside Texas can be ignored. No roads. No lakes. No buildings. Nothing. One simple rectangle comparison eliminates thousands of objects.

Now suppose another rectangle represents California:

+----------------+
|                |
| Search Area    |
|                |
| California     |
|                |
+----------------+

These rectangles overlap. That means some objects inside California might match. So the search continues into California.

Why Is It Called an R-Tree?

The "R" stands for Rectangle. Every group is represented by a rectangle. The tree is literally a tree made of rectangles.

Why Are Objects Grouped Together?

Nearby objects are likely to be searched together. Imagine:

• House
• Garage
• Garden

All close together. The R-Tree places them in one rectangle.

Another rectangle might contain:

• School
• Hospital
• Library

A completely different part of town.

Searching becomes much faster because nearby objects stay together.

What Happens When a New Object Is Added?

Suppose a new coffee shop opens in New York:

1. The R-Tree finds the New York group
2. It places the coffee shop there
3. Then it updates the New York bounding box if necessary
4. If the coffee shop lies outside the old rectangle, the rectangle expands slightly
5. Then the parent rectangle is updated
6. Eventually the whole tree stays correct

Unlike some spatial structures, the entire tree does not need to be rebuilt for every new object.

Why Is the Tree Balanced?

An R-Tree is designed to keep all leaf nodes at roughly the same depth. Think of a family tree where every branch has nearly the same number of levels.

This means searches don't become very deep. Even if there are millions of objects, the number of levels remains relatively small:

World
   ↓
Continent
   ↓
Country
   ↓
State
   ↓
City
   ↓
Objects

Only a handful of steps are needed to reach the desired area.

Why Can Bounding Boxes Overlap?

Unlike a grid, real-world geographic features have irregular shapes. Suppose two parks are close together:

+---------+
| Park A  |
|      +---------+
|      | Park B  |
+------+---------+

Their bounding rectangles might overlap. This overlap is acceptable. When searching that overlapping area, the R-Tree may check both groups. Although it means a little extra work, it handles irregular geographic data much better than forcing everything into fixed squares.

Visual Example

Root node: entire world
├── [North America: 10M shapes]
│   ├── [US East: 3M shapes]
│   │   ├── [Northeast: 1M shapes]
│   │   │   ├── [New York: 200K shapes]
│   │   │   │   ├── Central Park (polygon)
│   │   │   │   ├── Empire State Building (point)
│   │   │   │   └── ...
│   │   │   └── [Boston: 150K shapes]
│   │   └── [Southeast: 1.5M shapes]
│   └── [US West: 2M shapes]
├── [Europe: 8M shapes]
│   └── ...
└── [Asia: 15M shapes]
    └── ...

Bounding Box Concept

Every node in the R-Tree stores a Minimum Bounding Rectangle (MBR):

Node MBR: {min_lat: 40.4774, max_lat: 40.9176, min_lon: -74.2591, max_lon: -73.7004}
This covers the entire New York City area.

Query: "Find shapes within bounding box B"
  → If node MBR doesn't intersect B → skip entire subtree
  → If node MBR intersects B → recurse into children
  → At leaf level → check individual shapes

R-Tree Query Flow

Query: "Find shapes within bounding box B"

1. Start at root node
2. For each child node:
   a. Check if child's MBR intersects B
   b. If NO intersection → skip entire subtree (huge optimization!)
   c. If INTERSECTS → recurse into that child
3. At leaf level → check individual shapes against B
4. Return all matching shapes

Time complexity: O(log n + k) where k = number of results
vs. Brute force: O(n)

R-Tree Insertion

class RTreeNode:
    def __init__(self, is_leaf=False):
        self.children = []       # Child nodes or entries
        self.mbr = None          # Minimum bounding rectangle
        self.is_leaf = is_leaf
    
    def update_mbr(self):
        """Recalculate MBR to encompass all children"""
        min_lat = min(child.mbr.min_lat for child in self.children)
        max_lat = max(child.mbr.max_lat for child in self.children)
        min_lon = min(child.mbr.min_lon for child in self.children)
        max_lon = max(child.mbr.max_lon for child in self.children)
        self.mbr = MBR(min_lat, max_lat, min_lon, max_lon)

R-Tree vs QuadTree Comparison

Real-World Usage

• PostGIS: PostgreSQL extension using R-Trees for spatial queries
• SQLite R-Tree: Built-in spatial indexing
• Elasticsearch: geo_shape type uses R-Tree internally
• Google Maps: Uses R-Tree-like structures for polygon queries

The Big Picture — R-Tree as a Filing Cabinet

You can think of an R-Tree as a filing cabinet for locations:

1. Instead of storing every map object in one giant list, it groups nearby objects
2. Every group has a bounding rectangle (MBR) that encloses everything inside it
3. During a search, the computer first checks these rectangles
4. If a rectangle doesn't overlap the search area, the entire group is skipped
5. If it does overlap, the search continues into smaller groups
6. This process repeats until the relevant individual objects are found

This hierarchical grouping allows R-Trees to search through millions of geographic objects while examining only a tiny fraction of them, making spatial queries much faster than checking every object individually.

Geohashing

The Idea

What if you could convert a 2D coordinate (latitude, longitude) into a single string that encodes both the location AND the precision?

Geohash = a string that represents a geographic area

New York City:     dr5ru
Central Park:      dr5ru7
Central Park Zoo:  dr5ru7r
More precise:      dr5ru7rx
Even more:         dr5ru7rxy

Key insight: The longer the string, the smaller (more precise) the area.

How Geohashing Works

Geohashing uses binary subdivision — repeatedly dividing the world into halves.

Step 1: Divide longitude (east-west)

Longitude range: -180 to +180

First bit: Is the point in the left half or right half?
  Left half (-180 to 0)  → 0
  Right half (0 to +180) → 1

New York (lon = -74.006):
  Is -74.006 in [-180, 0] or [0, 180]?
  → Left half → bit = 0
  Remaining range: [-180, 0]

Is -74.006 in [-180, -90] or [-90, 0]?
  → Right half → bit = 1
  Remaining range: [-90, 0]

Is -74.006 in [-90, -45] or [-45, 0]?
  → Left half → bit = 0
  Remaining range: [-90, -45]

Continue until desired precision...

Step 2: Divide latitude (north-south)

Same process for latitude, interleaved with longitude bits.

New York (lat = 40.7128):
  Is 40.7128 in [0, 90] or [-90, 0]?
  → Upper half → bit = 1
  ... continue

Step 3: Interleave bits and encode

Longitude bits: 0 1 0 1 1 0 0 1 ...
Latitude bits:  1 0 1 0 0 1 1 0 ...

Interleaved: 01 10 01 10 11 00 01 10 ...

Group into 5-bit chunks (base32):
  01100 = 12 → 's'
  11001 = 25 → 'z'
  11000 = 24 → 'y'
  10000 = 16 → 'k'
  ...

Result: "dr5ru" (simplified)

Geohash Precision Table

The Magic of Prefix Matching

Geohashes with shared prefixes are nearby!

dr5ru  = Central Park
dr5ru7 = Central Park Zoo (shares "dr5ru" prefix → nearby!)
dr5ru9 = Somewhere else nearby (shares "dr5ru")
dr5rv  = Different neighborhood (shares "dr5" only)

This means: "Find nearby places" becomes "Find strings with matching prefixes!"

-- Find all places with geohash starting with 'dr5ru'
SELECT * FROM places WHERE geohash LIKE 'dr5ru%';
 
-- Much faster than:
SELECT * FROM places WHERE ST_Distance(location, POINT(-74.006, 40.7128)) < 1000;

Geohash Is Really a Stack of Bits

Here's the part that's worth pausing on. Each character in a geohash picks one of 32 options, which is exactly five bits.

A geohash like "dr5ru" isn't really a string.
It's a stack of bits.

'd' = 13 in base32 = 01101 in binary
'r' = 17 in base32 = 10001 in binary
'5' = 5  in base32 = 00101 in binary
'r' = 17 in base32 = 10001 in binary
'u' = 28 in base32 = 11100 in binary

Concatenated: 01101 10001 00101 10001 11100

That's 25 bits. Read them straight through as a number
and you've got an integer. Same bits, same sort order.

That's why Redis can store a geohash as a 52-bit integer and PostgreSQL can store it as text. And both indexes behave exactly the same way.

Redis GEO Internals: How It Actually Works

When you call GEOADD, Redis doesn't just store the string. Here's what happens under the hood:

1. Redis computes a 52-bit geohash integer from your lat/lon
2. Stores it in a sorted set (Redis's name for a B-Tree-like structure)
3. The sorted set keeps entries ordered by their geohash score

GEOADD drivers -74.0060 40.7128 "driver_001"
  → Computes geohash integer: 4071860210811908
  → ZADD drivers 4071860210811908 "driver_001"

Nearby query is just a ZRANGEBYSCORE against that sorted set.
Basically, a range scan over geohash integers.

This is one of the most elegant uses of an existing data structure
that you'll find in production.

# How Redis GEO actually stores data (simplified)
import redis
 
r = redis.Redis()
 
# GEOADD is syntactic sugar for ZADD with geohash score
# When you do:
r.geoadd("drivers", (-74.0060, 40.7128, "driver_001"))
 
# Redis internally does something like:
geohash_int = compute_52bit_geohash(40.7128, -74.0060)
r.zadd("drivers", {"driver_001": geohash_int})
 
# GEORADIUS is syntactic sugar for ZRANGEBYSCORE
# Find all drivers whose geohash integers fall in a range
# that covers the search circle

Geohash in Redis (Nearby Users)

import geohash2
 
# Store user location
def store_user_location(user_id, lat, lon):
    geohash = geohash2.encode(lat, lon, precision=7)
    redis.hset("user_locations", user_id, f"{lat},{lon},{geohash}")
    redis.zadd(f"geo:{geohash[:5]}", {user_id: score_from_geohash(geohash)})
 
# Find nearby users (same geohash prefix)
def find_nearby_users(lat, lon, radius_km):
    geohash = geohash2.encode(lat, lon, precision=7)
    prefix = geohash[:5]  # Neighborhood-level
    
    # Find all users with same prefix
    nearby = redis.zrange(f"geo:{prefix}", 0, -1)
    
    # Filter by actual distance
    result = []
    for user_id in nearby:
        stored_lat, stored_lon = get_user_coords(user_id)
        distance = haversine(lat, lon, stored_lat, stored_lon)
        if distance <= radius_km:
            result.append(user_id)
    
    return result

Geohash Limitations

Edge case: Adjacent areas may have different prefixes

Point A: dr5ru7 → geohash: dr5ru7
Point B: dr5ru9 → geohash: dr5ru9

These are 200 meters apart but...
Point C: dr5rv0 → geohash: dr5rv0
This is right next to A but shares LESS prefix!

Solution: Also check 8 neighboring geohashes

Solution — Check Neighbors:

def find_nearby(lat, lon, precision=6):
    geohash = geohash2.encode(lat, lon, precision=precision)
    neighbors = geohash2.neighbors(geohash)
    
    # Check center + all 8 neighbors
    candidates = [geohash] + list(neighbors.values())
    
    results = []
    for gh in candidates:
        results.extend(query_by_geohash(gh))
    
    return results

Post-Filtering: The Final Step

After querying the 3x3 grid of geohash cells, you have candidates — not exact results. The standard fix is called post-filtering:

Step 1: Query 9 cells (current + 8 neighbors)
        → Returns ~200 candidate points

Step 2: For each candidate, compute EXACT distance
        → Haversine formula: sqrt((Δlat)² + (Δlon)² × cos(lat))

Step 3: Discard points outside your radius
        → 200 candidates → 12 actual matches

This is fast because:
  - Step 1 uses the B-Tree index (very fast)
  - Step 2 only runs on ~200 points (not millions)
  - Step 3 is simple math

Almost every encoded-key index in production does some version of this trick at query time. The index gets you close (candidates), then exact distance math filters to the real answer.

When to Use Geohashing

• Simple nearby search: "Users within 5km"
• Redis geospatial queries: Redis GEO commands use geohashing internally
• URL sharing: https://geohash.org/dr5ru7 shares a precise location
• Database indexing: Add geohash column for fast prefix queries

Geohash vs R-Tree for Overlapping Regions

Geohash also divides the Earth into squares. Yes, geohash repeatedly divides the Earth into smaller and smaller rectangles (often called cells):

World
│
├── Big Cell
│   ├── Smaller Cell
│   │   ├── Smaller Cell
│   │   │   ├── Smaller Cell

Eventually you get small cells like:

+-----+-----+
| abc | abd |
+-----+-----+
| abe | abf |
+-----+-----+

Each square has a unique geohash. So geohash is also a fixed spatial partition, similar in spirit to a QuadTree.

What happens if a park crosses two geohash cells?

+---------+---------+
|#########|#########|
|#########|#########|
+---------+---------+

The park spans two cells. Which geohash should represent the park? Usually systems do one of these:

1. Store the park in multiple cells
2. Store only its center point
3. Store its bounding box separately

So yes, objects can cross geohash boundaries, just like they can cross QuadTree squares.

Then why use geohash? Because geohash is mainly designed for finding nearby points, not complex shapes.

Imagine Uber drivers — each driver is just a point (one GPS location). Each point belongs to exactly one geohash cell. Finding nearby drivers becomes easy:

Find everyone whose geohash starts with "dr5ru"
Then calculate the exact distance.

This is very fast. But a park is not a point — it has an area. It may cover several geohash cells. That's why geohash isn't ideal for indexing polygons.

An R-Tree is much better because it stores the park using its own bounding rectangle:

      +----------------+
      |                |
      |     PARK       |
      |                |
      +----------------+

The rectangle is based on the object — not on a predefined grid.

What about overlap?

• Geohash: The cells themselves never overlap. Each location belongs to exactly one cell. However, objects can overlap multiple cells.
• R-Tree: The rectangles themselves can overlap. Imagine two parks close together:

+-------------+
|   Park A    |
|        +-------------+
|        |   Park B    |
+--------+-------------+

The bounding rectangles overlap. That's completely normal in an R-Tree.

Why do geohashes have the "neighbor problem"?

Suppose you're standing exactly here:

+-----+-----+
| abc | abd |
+--X--+-----+
| abe | abf |
+-----+-----+

You are very close to the boundary. A nearby restaurant might be in cell abd, while you're in abc. If you search only abc, you'll miss the restaurant. That's why geohash searches usually check the current cell plus its 8 neighboring cells.

Why doesn't R-Tree have this issue? Because R-Trees don't rely on fixed grid boundaries. They search by asking: "Does this bounding rectangle intersect my search area?" If yes, they continue. It doesn't matter where an imaginary grid boundary would have been.

Summary:

Both QuadTrees and Geohash partition space into fixed regions, so large objects can span multiple regions. The key advantage of an R-Tree is that it doesn't force objects into a fixed grid; instead, it builds its hierarchy around the objects themselves, which is why it's much more effective for irregular geographic shapes.

S2 — Google's Spherical Indexing

The Problem with Geohash on a Globe

Geohash works great when we're mapping out a city. But it starts to hurt when you look at a globe.

The problem is that geohash treats latitude and longitude as if they lived on a flat rectangle. The Earth isn't flat.

A degree of longitude:
  At the equator:  ~111 km
  At the poles:    nearly 0 km

So a cell that's one geohash character wide is:
  - A fat square at the equator
  - A tiny sliver near each of the poles

You want cells of roughly equal area everywhere on Earth. And you want a 1D ordering that preserves locality on a sphere, not just a rectangle.

How S2 Works

Around 2011, Google built S2 to fix this. The trick:

1. Wrap the sphere in a cube (6 faces)
2. Project the Earth onto its six flat surfaces
3. Subdivide each face into cells that stay roughly the same size anywhere on the globe

         ┌───────┐
        /│       /│
       / │      / │
      ┌───────┐  │
      │  │    │  │
      │  └────│──┘
      │ /     │ /
      │/      │/
      └───────┘

Earth projected onto cube faces
Then each face subdivided into cells

S2 Cell IDs

Every location gets a 64-bit integer called an S2 Cell ID.

Like geohash, the IDs are hierarchical:

Truncate the ID → get a coarser parent cell
Longer ID → more precise location

S2 vs Geohash

Who Uses S2?

• MongoDB — 2D sphere index uses S2. When your geoquery correctly handles a polygon that crosses the anti-meridian, that's S2 under the hood. Flat-Earth indexes treat such a polygon as stretching all the way around the globe. But S2 knows better.
• Google Maps — Uses S2 for map tile systems and spatial indexing.

H3 — Uber's Hexagonal Indexing

Beginner Explanation — Think of H3 as a Way to Divide the Earth

Think of H3 as a way to divide the entire Earth into small hexagonal (6-sided) tiles, just like dividing a city into neighborhoods. Every GPS location belongs to one of these hexagons.

The main idea is:

Instead of remembering millions of latitude/longitude coordinates, we remember which hexagon a location belongs to.

Why Hexagons? (Not Squares)

Geohashing uses squares. H3 uses hexagons. Why?

Imagine You're Playing a Board Game

Square grid:

┌───┬───┬───┐
│ A │ B │ C │
├───┼───┼───┤
│ D │ X │ E │
├───┼───┼───┤
│ F │ G │ H │
└───┴───┴───┘

Suppose you're standing at X. Your neighbors are:

• Up (B)
• Down (G)
• Left (D)
• Right (E)

These are close. But the diagonal cells (A, C, F, H) are farther away.

Distance isn't the same:

• Straight neighbors = 1 unit away
• Diagonal neighbors = √2 ≈ 1.41 units away

Squares have uneven neighbor distances.

Hexagon grid:

Now imagine hexagons:

      ○
   ○  X  ○
      ○
   ○     ○

A hexagon always has 6 neighbors. The important part:

Every neighbor is exactly the same distance from the center.

      ○
   ○  X  ○
      ○
   ○     ○

All = same distance

This makes calculations much easier.

Why Does Uber Like Hexagons?

Imagine you're looking for the nearest driver.

With squares:

• Driver A → 1 km away
• Driver B (diagonal) → 1.41 km away

Both are neighbors, but one is farther.

With hexagons:

• Driver A → 1 km
• Driver B → 1 km
• Driver C → 1 km
• Driver D → 1 km
• Driver E → 1 km
• Driver F → 1 km

Every neighboring hexagon is equally close. This makes "find nearby drivers" much simpler.

Better Sampling

Suppose you're counting cars.

With squares:

↑
← X →
↓

Movement naturally favors horizontal and vertical directions. Diagonal movement behaves differently. This introduces bias.

With hexagons:

  ↖  ↑  ↗

   X

  ↙  ↓  ↘

Everything is symmetric. Hexagons spread equally in all directions.

Efficient Tiling

Some shapes leave gaps:

Circles:

○ ○ ○
 ○ ○

Gaps everywhere.

Squares:

□□□□
□□□□

No gaps.

Hexagons:

⬢⬢⬢
⬢⬢⬢

Also no gaps. Nature uses hexagons too — examples include honeycombs, snowflakes, and basalt columns — because they pack space efficiently.

Hexagon advantages:

1. Uniform distance: All 6 neighbors are equidistant from center
2. Better sampling: No bias toward diagonal/orthogonal neighbors
3. Efficient tiling: Hexagons tile the plane perfectly
4. Hierarchical: H3 supports 16 resolution levels (zoom levels)

H3 Resolution Levels

Resolution 0: ~4,860 km per edge   (continent-level)
Resolution 1: ~1,832 km per edge
Resolution 2: ~690 km per edge
Resolution 3: ~261 km per edge     (country-level)
Resolution 4: ~98 km per edge      (state-level)
Resolution 5: ~37 km per edge      (metro-level)
Resolution 6: ~14 km per edge      (city-level)
Resolution 7: ~5.2 km per edge     (neighborhood)
Resolution 8: ~1.96 km per edge    (district)
Resolution 9: ~745 m per edge      (local)
Resolution 10: ~283 m per edge     (street)
Resolution 11: ~107 m per edge     (block)
Resolution 12: ~40 m per edge      (building)
Resolution 13: ~15 m per edge      (fine detail)
Resolution 14: ~5.8 m per edge     (very fine)
Resolution 15: ~2.2 m per edge     (cm-level)

How H3 Works — Beginner Version

Think of Google Maps. When zoomed out, you see the entire Earth. Zoom in, you see countries. Zoom again, cities. Again, streets. Again, buildings.

H3 works exactly like this. Each resolution means a different hexagon size.

Suppose you have GPS coordinates:

• Latitude = 40.7128
• Longitude = -74.0060

Step 1: Take the GPS location: (40.7128, -74.0060)

Step 2: Imagine wrapping the Earth with millions of tiny hexagons.

🌍

⬢⬢⬢⬢⬢
⬢⬢⬢⬢⬢
⬢⬢⬢⬢⬢

Step 3: Find which hexagon contains your point.

⬢ ⬢ ⬢

⬢ X ⬢

⬢ ⬢ ⬢

Your location belongs to one specific hexagon.

Step 4: Return that hexagon's ID. Example: 8928308280fffff

Instead of storing:

40.7128
-74.0060

You can store:

8928308280fffff

Technical H3 Workflow

Step 1: Take a lat/lon coordinate
  lat = 40.7128, lon = -74.0060

Step 2: Project onto an icosahedron (20-sided polyhedron)
  The icosahedron's faces are divided into hexagons

Step 3: Flatten the icosahedron back to 2D
  Result: A global hexagonal grid

Step 4: Find which hexagon contains the point
  H3 index: 0x8928308280fffff

What Is the Icosahedron?

The Earth is a sphere. Putting perfect hexagons directly on a sphere is difficult. Uber solves this by first imagining the Earth as an icosahedron, which is a 20-faced 3D shape.

      /\
     /__\

Many triangular faces

Each triangular face is divided into hexagons, and then mapped back onto the globe. This keeps distortion much lower than simply drawing a square grid over latitude and longitude.

H3 Index Structure

Beginner: Think of an H3 index like a ZIP code. A ZIP code tells you an area. An H3 index tells you which hexagon on Earth you're in. You usually don't need to understand the bits inside it — the library handles that.

Technical:

H3 Index: 0x8928308280fffff

Binary: 1000 1001 0010 1000 0011 0000 1000 0010 1000 0000 1111 1111 1111 1111 1111

Breakdown:
  Mode bit (1):     H3 index (not other encoding)
  Resolution (00101): Resolution 5
  Base cell (146):   One of 122 base cells
  Digits (308280fffff): Hierarchical cell digits

H3 in Python

import h3
 
# Convert lat/lon to H3 index
lat, lon = 40.7128, -74.0060
h3_index = h3.latlng_to_cell(lat, lon, resolution=9)
print(h3_index)  # 0x8928308280fffff
 
# Convert H3 index back to lat/lon
center = h3.cell_to_latlng(h3_index)
print(center)  # (40.7128, -74.0060)
 
# Get all hexagons within a radius
nearby = h3.grid_disk(h3_index, k=10)  # 10 hexagons radius
print(f"{len(nearby)} hexagons in range")
 
# Find hexagons along a path
origin = h3.latlng_to_cell(40.7128, -74.0060, 9)
destination = h3.latlng_to_cell(40.7589, -73.9851, 9)
path = h3.grid_path(origin, destination)
print(f"Path has {len(path)} hexagons")

Nearby Hexagons — Beginner

nearby = h3.grid_disk(cell, 2)

Imagine:

       ⬢
    ⬢ ⬢ ⬢
  ⬢ ⬢ X ⬢ ⬢
    ⬢ ⬢ ⬢
       ⬢

Instead of searching every driver in a city, Uber only checks drivers in the current hexagon and nearby hexagons. This greatly speeds up searches.

H3 Hierarchical Parent-Child

One large hexagon can be divided into 7 smaller hexagons.

Large Hexagon:

      ⬢

Becomes:

⬢ ⬢ ⬢
⬢ ⬢ ⬢
   ⬢

This creates a hierarchy:

Country
   ↓
City
   ↓
Neighborhood
   ↓
Street
   ↓
Building

Each smaller hexagon has one parent, and each larger hexagon has several children. This makes it easy to switch between coarse and fine geographic views.

Technical H3 Parent-Child

Resolution 7 parent:
┌─────────────┐
│  Resolution │
│     7       │
│  (5.2 km)   │
└─────────────┘
       │
       ▼ subdivides into 7 children
┌───┬───┬───┐
│ 7 │ 7 │ 7 │  Each child is Resolution 8 (1.96 km)
├───┼───┼───┤
│ 7 │ 7 │ 7 │
├───┼───┼───┤
│ 7 │ 7 │ 7 │
└───┴───┴───┘

Each H3 cell has a parent at resolution-1
Each H3 cell has 7 children at resolution+1

Real Uber Example

Imagine three drivers and one rider:

Without H3:

• Compare the rider's GPS coordinates with every driver's GPS coordinates
• Calculate distances repeatedly

With H3:

1. Find the rider's hexagon
2. Find drivers in the same hexagon
3. If none are available, check neighboring hexagons
4. Continue outward if needed

       ⬢
    ⬢ ⬢ ⬢
  ⬢ ⬢ X ⬢ ⬢
    ⬢ ⬢ ⬢
       ⬢

Instead of searching every driver in a city, Uber only checks drivers in the current hexagon and nearby hexagons. This reduces the search space dramatically and makes matching much faster.

Uber's Use Cases

H3 vs Geohash Comparison

When to Use H3

• Ride-sharing: Uber, Lyft use H3 for driver-rider matching
• Delivery zones: Define delivery areas as sets of hexagons
• Traffic analysis: Aggregate vehicle counts per hexagon
• Climate data: Grid-based weather and environmental data
• Telecom: Cell tower coverage areas

H3 vs Geohash (Simple Comparison)

Beginner Summary — H3

1. H3 divides the Earth into hexagons
2. Every GPS location belongs to one hexagon
3. Each hexagon has a unique ID called an H3 index
4. Hexagons have six equally distant neighbors, making nearby searches more consistent than squares
5. Different resolutions let you zoom from continent-sized cells down to building-sized cells
6. Companies like Uber use H3 to quickly find nearby drivers, define delivery zones, calculate surge pricing, and analyze geographic data efficiently

The Two Camps: Custom Trees vs Encoded Keys

Everything we've looked so far — QuadTrees, KD Trees, BKD Trees, R-Trees — they're all custom tree structures. They work, but they're complicated. Your database needs special indexing code, special query code, special tooling.

What if instead we skipped all of that?

What if we could take latitude and longitude and turn them into a single number — just one integer — where numerically close integers meant geographically close locations?

If we had an integer, then we could use a regular B-Tree — that boring thing our database already has — and range scans would just work out of the box.

This is the idea that took over most of the industry.

Camp 1: Custom Spatial Trees

The database ships a purpose-built tree tuned to behave like a B-Tree on disk.

PostgreSQL     → R-Tree variant (via PostGIS)
Elasticsearch  → BKD Tree

Strengths:

• Index points, lines, polygons, and complex geometries
• Exact answers to questions like "Does this highway intersect this country?"
• Rich spatial query support

Weaknesses:

• Database needs a real spatial extension (not available in every setup)
• Writes can be expensive (R-Tree inserts run a rectangular packing heuristic)
• BKD Trees are write-once (bad for moving data like drivers)

Camp 2: Encoded Keys

Turn latitude and longitude into a single sortable integer, drop it into a regular B-Tree, and you're done.

Redis         → Geohash (52-bit integer in a sorted set)
MongoDB       → S2 (64-bit cell ID)
Uber          → H3 (64-bit hexagonal cell ID)

Strengths:

• Works in any database with a B-Tree or sorted structure
• No spatial extension required
• Writes are dirt cheap (a driver moving = one integer update)
• Hierarchical IDs (zoom out by truncating the ID)

Weaknesses:

• Mostly stuck with points (not polygons)
• Boundary artifacts (two locations a meter apart can land on different keys)
• Usually need to query neighbor cells and post-filter by exact location

Decision Framework

Need shapes and exact geometry?
  → Custom tree (R-Tree via PostGIS)
  → But understand the limitations on write throughput

Have points at scale with heavy writes?
  → Encoded keys (Geohash, S2, H3)
  → Simple, fast, and works with any B-Tree database

The Trade-offs at a Glance

How Each Index Actually Works

Here's how each one organizes space and how search traverses it:

Visual Intuition

Quad Tree:

World
│
├── NW
├── NE   ← query here
├── SW
└── SE

Every level narrows down to a smaller geographic area.

KD Tree:

Split by longitude
        │
   Left │ Right
         │
     Split by latitude

Each comparison removes half of the remaining search space.

R-Tree:

Root
│
├── Rectangle A
│      ├── Restaurant
│      ├── Hotel
│      └── Cafe
│
└── Rectangle B
       ├── Park
       ├── School
       └── Hospital

If your query is inside Rectangle A, the database never even looks inside Rectangle B.

How Encoded Keys Work (Geohash / H3 / S2)

With encoded keys, you don't traverse a spatial tree. Instead:

GPS
   ↓
Encode to H3 ID
   ↓
B-tree
   ↓
Jump directly to that ID

The "spatial intelligence" is in the encoding (H3/Geohash/S2), not in the tree.

The One-Sentence Difference

Custom trees: Partition space, then traverse only the partitions that could contain the answer.

Encoded keys: Encode each location into a sortable ID, then let a standard B-tree retrieve matching IDs efficiently.

Geo-Fencing

What Is Geo-Fencing?

A geo-fence is a virtual boundary around a real-world geographic area. When a device enters or exits this boundary, the system triggers an action.

Geo-fence example:
  "When a delivery driver enters a 500m radius of the customer's address,
   send a push notification: 'Your driver is almost here!'"

Types of Geo-Fences

1. CIRCULAR
   Center: lat/lon
   Radius: meters
   
   "All users within 2km of Starbucks"
   
2. POLYGON
   Custom shape defined by vertices
   
   "All vehicles within downtown Manhattan"
   Vertices: [lat1,lon1], [lat2,lon2], ..., [latN,lonN]
   
3. GEOTAG / GEOFENCE ID
   Pre-defined area (hexagon, grid cell)
   
   "All users within H3 hexagon 0x8928308280fffff"

Geo-Fence Implementation

# Simple circular geo-fence
def is_inside_geofence(user_lat, user_lon, fence_lat, fence_lon, radius_m):
    distance = haversine(user_lat, user_lon, fence_lat, fence_lon)
    return distance <= radius_m
 
# Polygon geo-fence (ray casting algorithm)
def is_inside_polygon(lat, lon, polygon_vertices):
    """
    Ray casting algorithm: cast a ray from the point
    and count intersections with polygon edges.
    Odd intersections = inside, Even = outside.
    """
    n = len(polygon_vertices)
    inside = False
    
    j = n - 1
    for i in range(n):
        lat_i, lon_i = polygon_vertices[i]
        lat_j, lon_j = polygon_vertices[j]
        
        if ((lat_i > lat) != (lat_j > lat) and
            lon < (lon_j - lon_i) * (lat - lat_i) / (lat_j - lat_i) + lon_i):
            inside = not inside
        j = i
    
    return inside

Geo-Fence Triggering Mechanism

Approach 1: PUSH-BASED (Server monitors location)
  GPS → Device sends location to server every 10 seconds
  Server checks: Is this location inside any geo-fence?
  If yes → trigger action (notification, log, etc.)

Approach 2: PUSH-BASED (Device checks locally)
  Geo-fence boundaries sent to device
  Device checks GPS against boundaries locally
  Only contacts server when enter/exit event occurs
  → More battery efficient

Approach 3: HYBRID (Geofence-as-a-service)
  Geofence stored in cloud
  Device SDK handles boundary checking
  Server receives enter/exit webhooks

Geo-Fence Performance Optimization

Problem: Checking 10,000 geo-fences for 1 million location updates per second

Solution 1: Spatial Index

Use QuadTree or R-Tree to index geo-fences
When location arrives:
  1. Query spatial index for nearby geo-fences
  2. Only check those geo-fences (not all 10,000)
  
Performance: O(log n) instead of O(n)

Solution 2: Geohash Pre-filter

For each geo-fence:
  1. Compute geohash of center
  2. For incoming location:
     a. Compute geohash of user
     b. If prefixes don't match → not inside (skip expensive check)
     c. If prefixes match → do precise distance check

Solution 3: Grid-Based Pre-computation

Divide world into grid cells
For each cell, pre-compute which geo-fences contain it
When location arrives:
  1. Look up cell's geo-fence list
  2. Check only those geo-fences

Real-World Geo-Fence Use Cases