Spatial Data Models

1. Types of Spatial Data Models in GIS

A data model in GIS is a mathematical and conceptual framework used to represent real-world geographic features in a digital format. The primary spatial data models used to abstract and manage this information include:

• Vector Data Model: Represents discrete geographic features using coordinates to form points, lines, and polygons. It is ideal for objects with distinct boundaries, such as buildings, administrative borders, or road networks.
• Raster Data Model: Represents continuous spatial phenomena through a grid of equally sized cells (pixels), where each cell holds a specific value. It is best suited for continuous data like elevation, temperature, or satellite imagery.
• TIN (Triangulated Irregular Network): A vector-based representation of a continuous surface consisting of non-overlapping, contiguous triangles. It is primarily used for high-precision elevation modeling and terrain analysis.

2. The Network Data Model

The Network Data Model is a specialized, topologically structured vector model designed to represent interconnected linear features. It defines how lines connect to each other at nodes (intersections) to model the flow of resources or movement.

• Examples: It is heavily used in civil engineering and urban planning to map road networks (for finding the shortest route), river systems (for tracing hydrological flow), and utility grids (such as water pipes or electrical lines to manage distribution and outages).

3. Attribute Variables: Qualitative vs. Quantitative

Attribute data provides the descriptive, non-spatial information linked to spatial geometries. These variables are broadly categorized into two types:

4. Levels of Measurement and their Impact on Symbology

The scale of measurement of attribute data dictates the analytical operations possible and directly determines the symbology used to visually communicate the map's message.

• Nominal Data: Categorical data with no inherent order or ranking (e.g., land use types like forest, agriculture, urban).
  • Symbology: Represented using "Unique Values." Different categories are shown using distinct, unranked colors or distinct symbols (e.g., green for forest, gray for urban).
• Ordinal Data: Categorical data that has a logical order or rank, but the intervals between ranks are not mathematically equal (e.g., risk zones classified as low, medium, and high).
  • Symbology: Represented using "Graduated Colors," typically a sequential color ramp (e.g., light yellow for low risk, transitioning to dark red for high risk).
• Interval Data: Numeric data with a known, equal interval between values, but lacking a true zero point (e.g., Temperature in Celsius or elevation above sea level, where zero does not signify the absolute absence of the quantity).
  • Symbology: Often mapped using classified numeric ranges with graduated color schemes, or diverging color ramps to show variation above and below a central mean.
• Ratio Data: Numeric data with a true, absolute zero point, allowing for proportional comparisons (e.g., population count, area, distance).
  • Symbology: Effectively represented using "Proportional Symbols" (e.g., larger circles for cities with higher populations) or "Graduated Colors" normalized by area (like a choropleth map showing population density).

1. Vector vs. Raster Data Models

Geographic Information Systems (GIS) use two main ways to represent the real world: Vector and Raster.

2. Types of Raster Models

Raster models are grouped into three basic types based on what their grid cells represent:

• Continuous (Surface) Rasters: Values change gradually. For example, an elevation map where cell values represent height above sea level. There are no sudden boundaries.
• Discrete (Thematic) Rasters: Values represent categories. For example, a land-use map where all cells representing "forest" have a value of 1, and all cells representing "water" have a value of 2.
• Image Rasters: Values represent light or energy. This is typical for satellite imagery or drone photos.

3. Raster Compression & Vectorization

Raster files (grids) can get huge. We use compression techniques to make the files smaller without losing information.

• Run Length Encoding (RLE):
  • How it works: Instead of saving the value of every single cell in a row, it groups identical values together.
  • Example: If a row has five cells of "Forest" (Value 1), instead of storing 1, 1, 1, 1, 1, RLE stores it as (5 of 1).
• Region Quadtree:
  • How it works: It divides the entire map grid into four large square blocks (quadrants). If a block is completely uniform (e.g., all water), it stops. If a block has mixed values (e.g., water and land), it splits that block into four smaller blocks. It repeats this until every block contains only one uniform value.
• Vectorization (Concept):
  • How it works: This is the process of converting a Raster grid into Vector lines and polygons. Think of it as tracing a scanned pixelated image to create smooth, editable lines.

4. Raster Data Storage Formats (BSQ, BIL, BIP)

When working with satellite images that have multiple layers (like a Red band, a Green band, and a Blue band), the computer needs a rule for how to store that data line-by-line.

• BSQ (Band Sequential): Stores all the data for Band 1 first, then all the data for Band 2, and so on. (Great if you only want to look at one band at a time).
• BIL (Band Interleaved by Line): Stores row 1 of Band 1, then row 1 of Band 2, then row 1 of Band 3. Then it moves to row 2. (A good middle-ground format).
• BIP (Band Interleaved by Pixel): Stores pixel 1 of Band 1, pixel 1 of Band 2, pixel 1 of Band 3. Then moves to pixel 2. (Great for analyzing the exact color of a specific spot quickly).

3.4 Indexing and Hierarchical Data Structures

No direct past exam questions have been asked from this section, but it is part of the syllabus and may appear in future exams.

When a GIS database contains millions of spatial features (e.g., every building in Kathmandu Valley), finding which features fall within a query area requires an efficient search strategy. Spatial indexing organizes features so the system doesn't have to check every single feature — it can quickly narrow down candidates.

Why Spatial Indexing is Needed

Without indexing, a spatial query like "Find all buildings within 1 km of this road" would require checking every building in the entire database — a brute-force approach that becomes impossibly slow with large datasets. Spatial indexes partition space into manageable regions so only relevant features are examined.

Common Spatial Indexing Methods

1. Grid Index: The study area is divided into a regular grid of equal-sized cells. Each feature is assigned to the cell(s) it overlaps. During a query, only features in the relevant cells are checked.
   • Advantage: Simple to implement
   • Disadvantage: Inefficient when features are unevenly distributed (many empty cells, some overloaded cells)
2. Quadtree: A hierarchical structure that recursively subdivides space into four quadrants. Areas with more features are subdivided further, while empty areas remain as large, undivided blocks. (This is related to the quadtree compression technique covered in Section 3.3.)
   • Advantage: Adapts to data density — more detail where needed
   • Disadvantage: More complex to build and maintain
3. R-Tree (Rectangle Tree): Groups nearby spatial objects into minimum bounding rectangles (MBRs) and organizes them in a balanced tree structure. When searching, the algorithm first checks which bounding rectangles intersect the query window, then examines the actual features only within matching rectangles.
   • Advantage: Very efficient for both point and polygon data; used in most modern GIS (PostGIS, ArcGIS)
   • Disadvantage: MBRs can overlap, causing some redundant checks

Hierarchical Data Structures

In the context of GIS, hierarchical structures organize spatial data in a tree-like fashion where:

• The root represents the entire study area
• Each branch represents a spatial subdivision
• The leaves contain the actual data values or feature references

Examples include the quadtree (divides into 4), octree (divides into 8, used for 3D data), and k-d trees (binary space partitioning). These structures enable fast spatial searches with time complexity of O(log n) instead of O(n).

1. Concept and Importance of Topology

What is Topology? Topology is a set of rules and mathematical concepts that define the spatial relationships between adjacent or connected geographic features (points, lines, and polygons) in a vector data model. It dictates how features share geometry.

Why is it important in GIS?

• Data Quality and Validation: Topology ensures data integrity by preventing common digitizing errors. It forces boundaries to match perfectly, eliminating overlapping polygons or empty gaps (slivers) between adjacent features like land parcels.
• Connectivity (Network Analysis): It explicitly defines how lines connect at intersections (nodes). This is absolutely critical for network analysis, such as finding the shortest driving route, modeling water flow in pipes, or analyzing traffic.
• Adjacency and Containment: Topology allows the GIS software to "know" spatial facts without calculating them on the fly. It knows which countries share a border (adjacency) or which cities are located entirely within a specific province (containment).

2. The TIN (Triangulated Irregular Network) Data Model

What is a TIN? A TIN is a digital data structure used to represent continuous 3D surfaces most commonly terrain or elevation. It constructs this surface using a network of non-overlapping contiguous triangles. The corners of these triangles are created from irregularly spaced data points (called mass points) where each point contains an X Y and Z (elevation) coordinate.

Does TIN belong to Raster or Vector?

A TIN strictly belongs to the vector data model.

Why? Unlike a raster model which relies on a uniform grid of identical square cells (pixels) to represent a surface a TIN is built entirely from fundamental vector geometries. It uses points (the nodes with XYZ coordinates) connected by lines (the edges) to form polygons (the triangular faces). Because it does not use a continuous pixel grid it is classified as a vector surface model.

3. Topology within the TIN Data Model

What is topology in a TIN?

In a TIN model topology refers to the explicit mathematical relationships maintained between its components: the nodes edges and triangular faces.

• The Structure: The TIN database doesn't just draw triangles; it explicitly records which three nodes make up a specific triangle and which triangles share a common edge.
• The Rule: In a proper TIN topology every edge is shared by exactly two adjacent triangles (unless it is on the outer boundary of the model) and multiple triangles share the same corner node.
• The Benefit: Because these topological relationships are hardcoded the GIS can rapidly perform complex 3D surface analyses across the terrain such as calculating slope aspect (the direction a slope faces) and line-of-sight visibility without having to recalculate how the points connect every time.

Numerical Procedures

1. Run Length Encoding (RLE)

(Applies to questions asking for Run Length Encoding)

This method compresses data by grouping identical adjacent cell values in a single row.

1. Read Row by Row: Start at the top-left cell of the raster grid and read across the first row.
2. Count Consecutive Values: Count how many times a specific value repeats sequentially.
3. Write the Pair: Write down the count followed by the value. (For example if you see five cells with the number "27" write it as (5 27) or 5:27).
4. Reset at Changes or New Rows: When the number changes start a new count. When you reach the end of a row always start a fresh count for the next row (standard row-by-row RLE).
5. Final Output: Your answer should be a linear list of these pairs for the entire grid.

2. Quadtree Encoding

(Applies to questions asking for Quad tree encoding)

This is a spatial compression method that divides grids into four quadrants (NW NE SW SE).

1. Check the Whole Grid: Look at the entire grid (e.g. 8x8). Does every single cell have the exact same value?
   • If yes: The entire grid is just one value. Stop.
   • If no: Proceed to Step 2.
2. Divide into Four: Split the grid evenly into four quadrants.
3. Evaluate Each Quadrant: Look at the top-left quadrant (NW) first.
   • Are all cells inside it identical? If yes record that value.
   • If there are mixed values split that specific quadrant into four smaller quadrants.
4. Repeat (Recurse): Continue this process of evaluating and splitting for the NE SW and SE quadrants. Keep splitting mixed blocks until every block you have contains only a single uniform value.
5. Final Output: Draw a tree diagram. The top root is the whole grid branching into 4 nodes. Uniform nodes stop (leaf nodes). Mixed nodes branch into 4 more nodes.

3. Block Encoding

(Applies to questions asking for Block encoding)

Instead of grouping rows or dividing by strict quadrants this method looks for the largest possible square blocks of identical values anywhere in the grid.

1. Find the Largest Squares: Scan the grid for the biggest possible square (e.g. 4x4) where all cells are the exact same value.
2. Record the Block: Write down three things for that block:
   • Its starting coordinate (usually the row and column of its top-left or bottom-left corner).
   • The size of the square (e.g. 4).
   • The value of the cells inside it.
3. Move to Smaller Squares: Once you've mapped out the largest squares find the next largest (e.g. 2x2 squares) and record them.
4. Record Single Cells: Finally any leftover cells that don't form a 2x2 or larger square must be recorded as 1x1 blocks.
5. Final Output: A list of coordinates sizes and values.

4. Chain Encoding

(Applies to questions asking for Chain encoding)

This method is used to trace the boundary of a specific feature (like a polygon of "forest" cells). It relies on a directional grid (usually 0 to 7 where 0 is East 1 is North-East 2 is North etc.).

1. Pick a Start Node: Choose an outer boundary pixel of the shape you are tracing. Record its (X Y) coordinate as the starting point.
2. Trace the Boundary: Move to the next adjacent pixel along the boundary of the shape.
3. Record the Direction: Write down the directional code (0-7) that corresponds to the direction you just moved.
4. Loop Back: Continue moving along the edge recording the direction code for every step until you arrive back at your starting pixel.
5. Final Output: The starting coordinate followed by a sequence of directional numbers.

5. Value Point Encoding

(Applies to questions asking for Value point encoding)

This is basically an index of coordinates for every value.

1. List Unique Values: Look at the grid and write down every unique value that appears (e.g. Forest Water Settlement).
2. Find Coordinates: Establish a coordinate system (e.g. top-left cell is 0 0 or 1 1).
3. Group by Value: For each unique value simply write a list of the (X Y) coordinates of every single cell that contains that value.
4. Final Output: A grouped list: Value A: (1 1) (1 2) (2 1)...

6. Calculating Percentage Decrease in Size

(Applies to questions asking for % decrease in size)

This proves how effective your compression was.

1. Calculate Uncompressed Size: Count the total number of cells in the original grid (e.g. an 8x8 grid = 64 cells).
2. Calculate Compressed Size: Count the number of data elements in your compressed version. (For RLE count the number of data pairs you created. For Quadtree count the total number of leaf nodes in your tree).
3. Apply the Formula: Use the standard percentage decrease formula:
   Percentage Decrease = ((Uncompressed Size − Compressed Size) / Uncompressed Size) × 100%

Solved Numerical Examples (Past Exam Questions)

The following are fully worked solutions from past examination papers demonstrating the practical application of every raster encoding method. Study the step-by-step approach carefully — the same methodology applies to any grid you encounter in the exam.

Example 1

Given Grid (8 × 8):

Original (uncompressed) size = 8 × 8 = 64 cells.

Solution (a) — Full Raster:

Simply list every cell value row by row. Total stored values = 64 (no compression).

F F F F W W F F  |  F F F F W W F F  |  F F F F O O F F  |  F F F F O O F F  |  F F F F S S S S  |  F F F F S S S S  |  F F F F S S W W  |  F F F F S S W W

Solution (b) — Run-Length Encoding (RLE):

Total RLE pairs = 3 + 3 + 3 + 3 + 2 + 2 + 3 + 3 = 22

Solution (c) — Quadtree Encoding:

Recursively divide the 8 × 8 grid into four equal quadrants. If a quadrant is homogeneous (all cells same value), it becomes a leaf node. Otherwise, subdivide again.

• Root (8 × 8): Not uniform → Split into four 4 × 4 quadrants
  • NW (R1–4, C1–4): All F → Leaf: F
  • NE (R1–4, C5–8): Mixed (W, F, O) → Split into four 2 × 2
    • NE-NW (R1–2, C5–6): All W → Leaf: W
    • NE-NE (R1–2, C7–8): All F → Leaf: F
    • NE-SW (R3–4, C5–6): All O → Leaf: O
    • NE-SE (R3–4, C7–8): All F → Leaf: F
  • SW (R5–8, C1–4): All F → Leaf: F
  • SE (R5–8, C5–8): Mixed (S, W) → Split into four 2 × 2
    • SE-NW (R5–6, C5–6): All S → Leaf: S
    • SE-NE (R5–6, C7–8): All S → Leaf: S
    • SE-SW (R7–8, C5–6): All S → Leaf: S
    • SE-SE (R7–8, C7–8): All W → Leaf: W

Total leaf nodes = 10 (F, W, F, O, F, F, S, S, S, W)

Solution (d) — Value Point Encoding:

List every unique value and the (Row, Col) coordinates of each cell containing that value:

Unique values = 4. All 64 cell positions are recorded, grouped under their respective values.

Example 3

Given Grid (8 × 8):

Original size = 8 × 8 = 64 cells.

Quadtree Decomposition:

• Root (8 × 8): Not uniform → Split
  • NW (R1–4, C1–4): All 12 → Leaf: 12
  • NE (R1–4, C5–8): All 10 → Leaf: 10
  • SW (R5–8, C1–4): Mixed → Split
    • SW-NW (R5–6, C1–2): All 9 → Leaf: 9
    • SW-NE (R5–6, C3–4): Mixed (7, 2, 1, 3) → Split
      • SW-NE-NW (R5, C3): 7 → Leaf: 7
      • SW-NE-NE (R5, C4): 2 → Leaf: 2
      • SW-NE-SW (R6, C3): 1 → Leaf: 1
      • SW-NE-SE (R6, C4): 3 → Leaf: 3
    • SW-SW (R7–8, C1–2): All 3 → Leaf: 3
    • SW-SE (R7–8, C3–4): All 8 → Leaf: 8
  • SE (R5–8, C5–8): Mixed → Split
    • SE-NW (R5–6, C5–6): All 6 → Leaf: 6
    • SE-NE (R5–6, C7–8): All 4 → Leaf: 4
    • SE-SW (R7–8, C5–6): All 2 → Leaf: 2
    • SE-SE (R7–8, C7–8): All 5 → Leaf: 5

Total leaf nodes = 13: (12, 10, 9, 7, 2, 1, 3, 3, 8, 6, 4, 2, 5)

Example 4

Given Grid (8 × 8):

Original size = 8 × 8 = 64 cells.

Solution (a) — Run-Length Encoding (RLE) [4 marks]:

Total RLE pairs = 4 + 4 + 4 + 4 + 1 + 1 + 3 + 1 = 22

Solution (b) — Quadtree Encoding [2 marks]:

• Root (8 × 8): Not uniform → Split
  • NW (R1–4, C1–4): Mixed (25, 31) → Split
    • NW-NW (R1–2, C1–2): All 25 → Leaf: 25
    • NW-NE (R1–2, C3–4): All 31 → Leaf: 31
    • NW-SW (R3–4, C1–2): All 25 → Leaf: 25
    • NW-SE (R3–4, C3–4): All 31 → Leaf: 31
  • NE (R1–4, C5–8): Mixed (25, 3) → Split
    • NE-NW (R1–2, C5–6): All 25 → Leaf: 25
    • NE-NE (R1–2, C7–8): All 3 → Leaf: 3
    • NE-SW (R3–4, C5–6): All 25 → Leaf: 25
    • NE-SE (R3–4, C7–8): All 3 → Leaf: 3
  • SW (R5–8, C1–4): All 27 → Leaf: 27
  • SE (R5–8, C5–8): Mixed (27, 35) → Split
    • SE-NW (R5–6, C5–6): All 27 → Leaf: 27
    • SE-NE (R5–6, C7–8): All 27 → Leaf: 27
    • SE-SW (R7–8, C5–6): All 27 → Leaf: 27
    • SE-SE (R7–8, C7–8): Mixed (35, 27) → Split
      • SE-SE-NW (R7, C7): 35 → Leaf: 35
      • SE-SE-NE (R7, C8): 27 → Leaf: 27
      • SE-SE-SW (R8, C7): 27 → Leaf: 27
      • SE-SE-SE (R8, C8): 27 → Leaf: 27

Total leaf nodes = 16

Solution (c) — Block Encoding [2 marks]:

Identify the largest homogeneous rectangular blocks:

Total blocks = 9

Solution (d) — Chain Encoding [2 marks]:

Chain encoding traces the boundary of each connected region using the 8-direction Freeman chain code:

2 = North (↑)    0 = East (→)    6 = South (↓)    4 = West (←)

Trace the boundary of each distinct region clockwise from its top-left cell:

Example 5

Given Grid (8 × 8):

Original size = 8 × 8 = 64 cells.

Solution (a) — Quadtree Encoding:

• Root (8 × 8): Not uniform → Split
  • NW (R1–4, C1–4): All 1 → Leaf: 1
  • NE (R1–4, C5–8): Mixed (3, 4, 5) → Split
    • NE-NW (R1–2, C5–6): All 3 → Leaf: 3
    • NE-NE (R1–2, C7–8): All 4 → Leaf: 4
    • NE-SW (R3–4, C5–6): Mixed (3,3,5,5) → Split
      • NE-SW-NW (R3, C5): 3 → Leaf: 3
      • NE-SW-NE (R3, C6): 3 → Leaf: 3
      • NE-SW-SW (R4, C5): 5 → Leaf: 5
      • NE-SW-SE (R4, C6): 5 → Leaf: 5
    • NE-SE (R3–4, C7–8): Mixed (4,4,5,4) → Split
      • NE-SE-NW (R3, C7): 4 → Leaf: 4
      • NE-SE-NE (R3, C8): 4 → Leaf: 4
      • NE-SE-SW (R4, C7): 5 → Leaf: 5
      • NE-SE-SE (R4, C8): 4 → Leaf: 4
  • SW (R5–8, C1–4): Mixed (2, 1) → Split
    • SW-NW (R5–6, C1–2): All 2 → Leaf: 2
    • SW-NE (R5–6, C3–4): All 2 → Leaf: 2
    • SW-SW (R7–8, C1–2): All 1 → Leaf: 1
    • SW-SE (R7–8, C3–4): All 1 → Leaf: 1
  • SE (R5–8, C5–8): Mixed (5, 3) → Split
    • SE-NW (R5–6, C5–6): All 5 → Leaf: 5
    • SE-NE (R5–6, C7–8): All 5 → Leaf: 5
    • SE-SW (R7–8, C5–6): All 3 → Leaf: 3
    • SE-SE (R7–8, C7–8): All 5 → Leaf: 5

Total leaf nodes = 19

Solution (b) — Run-Length Encoding (RLE):

Total RLE pairs = 3 + 3 + 3 + 3 + 2 + 2 + 3 + 3 = 22

Example 6

Given Grid (8 × 8):

Original size = 8 × 8 = 64 cells.

Solution (a) — Run-Length Encoding (RLE):

Total RLE pairs = 1 + 1 + 1 + 1 + 3 + 6 + 2 + 2 = 17

Solution (b) — Quadtree Encoding:

• Root (8 × 8): Not uniform → Split
  • NW (R1–4, C1–4): All 12 → Leaf: 12
  • NE (R1–4, C5–8): All 12 → Leaf: 12
  • SW (R5–8, C1–4): Mixed → Split
    • SW-NW (R5–6, C1–2): All 5 → Leaf: 5
    • SW-NE (R5–6, C3–4): Mixed (6, 6, 61, 62) → Split
      • SW-NE-NW (R5, C3): 6 → Leaf: 6
      • SW-NE-NE (R5, C4): 6 → Leaf: 6
      • SW-NE-SW (R6, C3): 61 → Leaf: 61
      • SW-NE-SE (R6, C4): 62 → Leaf: 62
    • SW-SW (R7–8, C1–2): All 7 → Leaf: 7
    • SW-SE (R7–8, C3–4): All 7 → Leaf: 7
  • SE (R5–8, C5–8): Mixed → Split
    • SE-NW (R5–6, C5–6): Mixed (9,6,9,62) → Split to 4 leaves
    • SE-NE (R5–6, C7–8): All 9 → Leaf: 9
    • SE-SW (R7–8, C5–6): All 9 → Leaf: 9
    • SE-SE (R7–8, C7–8): All 9 → Leaf: 9

Total Quadtree leaf nodes = 2 (NW, NE) + 6 (SW children) + 7 (SE children) = 15 nodes (approx).

Interactive Raster Encoding Solver

Enter values into the 8×8 grid below (or load an exam preset) and instantly compute Run-Length Encoding (RLE), Quadtree Encoding, and percentage decrease. The solver shows every step of the encoding process.

Total leaf nodes = 16

Example 7

Given Grid (8 × 8):

Original size = 8 × 8 = 64 cells.

Solution (a) — Run-Length Encoding (RLE):

Total RLE pairs = 4 + 4 + 3 + 2 + 2 + 4 + 3 + 2 = 24

Solution (b) — Quadtree Encoding:

• Root (8 × 8): Not uniform → Split
  • NW (R1–4, C1–4): Mixed → Split
    • NW-NW (R1–2, C1–2): All 88 → Leaf: 88
    • NW-NE (R1–2, C3–4): Mixed (75, 34, 33, 75) → Split
      • NW-NE-NW (R1, C3): 75 → Leaf: 75
      • NW-NE-NE (R1, C4): 34 → Leaf: 34
      • NW-NE-SW (R2, C3): 33 → Leaf: 33
      • NW-NE-SE (R2, C4): 75 → Leaf: 75
    • NW-SW (R3–4, C1–2): Mixed (88, 88, 77, 77) → Split
      • NW-SW-NW (R3, C1): 88 → Leaf: 88
      • NW-SW-NE (R3, C2): 88 → Leaf: 88
      • NW-SW-SW (R4, C1): 77 → Leaf: 77
      • NW-SW-SE (R4, C2): 77 → Leaf: 77
    • NW-SE (R3–4, C3–4): Mixed (88, 34, 77, 77) → Split
      • NW-SE-NW (R3, C3): 88 → Leaf: 88
      • NW-SE-NE (R3, C4): 34 → Leaf: 34
      • NW-SE-SW (R4, C3): 77 → Leaf: 77
      • NW-SE-SE (R4, C4): 77 → Leaf: 77
  • NE (R1–4, C5–8): All 9 → Leaf: 9
  • SW (R5–8, C1–4): All 56 → Leaf: 56
  • SE (R5–8, C5–8): Mixed → Split
    • SE-NW (R5–6, C5–6): Mixed (56, 56, 33, 25) → Split
      • SE-NW-NW (R5, C5): 56 → Leaf: 56
      • SE-NW-NE (R5, C6): 56 → Leaf: 56
      • SE-NW-SW (R6, C5): 33 → Leaf: 33
      • SE-NW-SE (R6, C6): 25 → Leaf: 25
    • SE-NE (R5–6, C7–8): All 10 → Leaf: 10
    • SE-SW (R7–8, C5–6): All 33 → Leaf: 33
    • SE-SE (R7–8, C7–8): Mixed (33, 9, 33, 33) → Split
      • SE-SE-NW (R7, C7): 33 → Leaf: 33
      • SE-SE-NE (R7, C8): 9 → Leaf: 9
      • SE-SE-SW (R8, C7): 33 → Leaf: 33
      • SE-SE-SE (R8, C8): 33 → Leaf: 33

Total leaf nodes = 25

End of Chapter 3 – Spatial Data Models