Chapter 3 Numericals – Raster Encoding

Key Formulas & Process

1. Full Raster Encoding

Every cell stores its own value. Total storage = rows × cols values.

Formula: Full Size = rows × columns

This is the baseline against which all compression methods are compared.

2. Run-Length Encoding (RLE)

Scans each row left-to-right. Consecutive identical values are stored as a single (value, count) pair.

Size: RLE Size = Total pairs × 2 (each pair has a value and a count)

Process:

• Read row left to right

• Count consecutive identical values

• Write (value, count) for each run

• Repeat for all rows

3. Block Encoding

Stores rectangular blocks of identical values as (value, r1, c1, r2, c2).

Size: Block Size = Number of blocks × 5

Better for data with large rectangular regions of uniform value.

4. Quadtree Encoding

Recursively divides the grid into 4 equal quadrants: NW, NE, SW, SE.

• If a quadrant is uniform (all same value) → it becomes a leaf node

• If a quadrant is mixed → subdivide into 4 again

• Requires power-of-2 grid size (4×4, 8×8, 16×16, etc.)

Total nodes = internal nodes + leaf nodes

5. Percentage Decrease

Formula: % Decrease = (Full − Encoded) / Full × 100

Process Steps

Draw/read the grid and note its dimensions (rows × columns)
Compute Full Raster size = total cells
For RLE: scan each row, group consecutive identical values into (value, count) pairs, sum all pairs
For Quadtree: check if entire grid is uniform; if not, split into NW/NE/SW/SE and recurse
For Block: identify largest rectangular uniform blocks and encode as (value, r1, c1, r2, c2)
Calculate % decrease for each method

Q1. 6×6 Grid — RLE & Block Encoding VERIFIED

Exam: 2074 Bhadra Q1b [6 Marks]

Question: Encode the following 6×6 raster using Run-Length Encoding and Block Encoding. Calculate the percentage decrease for each.

	C1	C2	C3	C4	C5	C6
R1	25	25	25	25	25	25
R2	25	25	25	25	25	25
R3	25	25	25	25	25	25
R4	5	5	5	10	10	10
R5	5	5	5	12	12	12
R6	5	5	5	15	12	12

Full Raster = 6 × 6 = 36 cells

Solution (a) — Run-Length Encoding

Scan each row left to right, grouping consecutive identical values:

⚙ RLE_2074Bhadra.calc

// Run-Length Encoding (row by row)
Row 1: (25,6)                      // 1 pair  — all 25s
Row 2: (25,6)                      // 1 pair  — all 25s
Row 3: (25,6)                      // 1 pair  — all 25s
Row 4: (5,3)(10,3)                // 2 pairs — split at col 4
Row 5: (5,3)(12,3)                // 2 pairs — split at col 4
Row 6: (5,3)(15,1)(12,2)          // 3 pairs — 3 runs
// Total pairs = 1 + 1 + 1 + 2 + 2 + 3 = 10
Total RLE = 10 pairs = 20 values
// Percentage decrease
% Decrease = (36 − 20) / 36 × 100
% Decrease = 16 / 36 × 100
% Decrease = 44.44%

GIS CalculationUTF-8

Solution (b) — Block Encoding

Identify the largest rectangular blocks of uniform values:

⚙ Block_2074Bhadra.calc

// Block Encoding: (value, r1, c1, r2, c2)
// Each entry = 5 values
Block 1: (25, 1,1, 3,6)    // 3×6 = 18 cells — top 3 rows
Block 2: ( 5, 4,1, 6,3)    // 3×3 =  9 cells — bottom-left
Block 3: (10, 4,4, 4,6)    // 1×3 =  3 cells — row 4 right
Block 4: (12, 5,4, 5,6)    // 1×3 =  3 cells — row 5 right
Block 5: (15, 6,4, 6,4)    // 1×1 =  1 cell  — single cell
Block 6: (12, 6,5, 6,6)    // 1×2 =  2 cells — row 6 right
                             // Check: 18+9+3+3+1+2 = 36 ✓
Total = 6 blocks × 5 values/block = 30 values
% Decrease = (36 − 30) / 36 × 100
% Decrease = 16.67%
// RLE (44.44%) beats Block (16.67%) for this grid

GIS CalculationUTF-8

Answer: RLE = 20 values (44.44% decrease) | Block = 30 values (16.67% decrease). RLE is more efficient for this grid because rows have long runs but the lower-right corner has irregular rectangular shapes.

Q2. 8×8 Grid — RLE & Quadtree VERIFIED

Exam: 2081 Chaitra [8 Marks]

Question: Perform Run-Length Encoding and construct a Quadtree for the following 8×8 raster. Calculate percentage decrease for each.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	88	88	75	34	9	9	9	9
R2	88	88	33	75	9	9	9	9
R3	88	88	88	34	9	9	9	9
R4	77	77	77	77	9	9	9	9
R5	56	56	56	56	56	56	10	10
R6	56	56	56	56	33	25	10	10
R7	56	56	56	56	33	33	33	9
R8	56	56	56	56	33	33	33	33

Full Raster = 8 × 8 = 64 cells

Solution (a) — Run-Length Encoding

⚙ RLE_2081Chaitra.calc

// Run-Length Encoding (row by row)
Row 1: (88,2)(75,1)(34,1)(9,4)    // 4 pairs
Row 2: (88,2)(33,1)(75,1)(9,4)   // 4 pairs
Row 3: (88,3)(34,1)(9,4)          // 3 pairs
Row 4: (77,4)(9,4)                 // 2 pairs
Row 5: (56,6)(10,2)                // 2 pairs
Row 6: (56,4)(33,1)(25,1)(10,2)  // 4 pairs
Row 7: (56,4)(33,3)(9,1)           // 3 pairs
Row 8: (56,4)(33,4)                // 2 pairs
// Total = 4+4+3+2+2+4+3+2 = 24 pairs
Total RLE = 24 pairs = 48 values
% Decrease = (64 − 48) / 64 × 100
% Decrease = 25.0%

GIS CalculationUTF-8

Solution (b) — Quadtree Encoding

The 8×8 grid is divided into four 4×4 quadrants. Each quadrant is checked for uniformity:

⚙ Quadtree_2081Chaitra.calc

// Quadtree Decomposition (8×8)
Level 0 (8×8): Not uniform → split into 4 quadrants
// ── NW Quadrant (R1-4, C1-4) ──
NW (4×4): {88,88,75,34,88,88,33,75,88,88,88,34,77,77,77,77}
  Not uniform → split into 4
  NW-NW (R1-2, C1-2): all 88 ✓  Leaf
  NW-NE (R1-2, C3-4): {75,34,33,75} → 4 leaves
  NW-SW (R3-4, C1-2): {88,88,77,77} → 4 leaves
  NW-SE (R3-4, C3-4): {88,34,77,77} → 4 leaves
  // NW total: 1 internal + (1+4+4+4) = 17 nodes
// ── NE Quadrant (R1-4, C5-8) ──
NE (4×4): all 9 ✓  1 leaf node
// ── SW Quadrant (R5-8, C1-4) ──
SW (4×4): all 56 ✓  1 leaf node
// ── SE Quadrant (R5-8, C5-8) ──
SE (4×4): {56,56,10,10,33,25,10,10,33,33,33,9,33,33,33,33}
  Not uniform → split into 4
  SE-NW (R5-6, C5-6): {56,56,33,25} → 4 leaves
  SE-NE (R5-6, C7-8): all 10 ✓  Leaf
  SE-SW (R7-8, C5-6): all 33 ✓  Leaf
  SE-SE (R7-8, C7-8): {33,9,33,33} → 4 leaves
  // SE total: 1 internal + (4+1+1+4) + 1 = 13 nodes
Total leaf nodes = 1 + 12 + 1 + 1 + 10 = 25
Total internal = 1(root) + 1(NW) + 1(SE) = 3

GIS CalculationUTF-8

Answer: RLE = 48 values (25.0% decrease). Quadtree has 25 leaf nodes and 3 internal nodes. This grid is quite heterogeneous, so neither method achieves great compression.

Q3. 8×8 Grid — RLE & Quadtree VERIFIED

Exam: 2080 Chaitra Q7 [8 Marks]

Question: Perform RLE and Quadtree encoding on the following 8×8 raster.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	25	25	31	31	31	31
R2	25	25	25	25	31	31	31	31
R3	25	25	27	27	31	31	35	35
R4	25	25	27	27	31	31	35	35
R5	3	3	3	3	3	3	3	3
R6	3	3	3	3	3	3	3	3
R7	3	3	3	3	3	3	3	3
R8	3	3	3	3	3	3	3	3

Full Raster = 8 × 8 = 64 cells

⚙ RLE_2080Chaitra.calc

// Run-Length Encoding
Row 1: (25,4)(31,4)               // 2 pairs
Row 2: (25,4)(31,4)               // 2 pairs
Row 3: (25,2)(27,2)(31,2)(35,2)  // 4 pairs
Row 4: (25,2)(27,2)(31,2)(35,2)  // 4 pairs
Row 5: (3,8)                       // 1 pair
Row 6: (3,8)                       // 1 pair
Row 7: (3,8)                       // 1 pair
Row 8: (3,8)                       // 1 pair
// Total = 2+2+4+4+1+1+1+1 = 16 pairs
Total RLE = 16 pairs = 32 values
% Decrease = (64 − 32) / 64 × 100 = 50.0%

GIS CalculationUTF-8

⚙ Quadtree_2080Chaitra.calc

// Quadtree Decomposition
Root (8×8): Not uniform → split
NW (R1-4, C1-4): mixed → split
  NW-NW (R1-2, C1-2): all 25 ✓ Leaf
  NW-NE (R1-2, C3-4): all 25 ✓ Leaf
  NW-SW (R3-4, C1-2): all 25 ✓ Leaf
  NW-SE (R3-4, C3-4): all 27 ✓ Leaf
NE (R1-4, C5-8): mixed → split
  NE-NW (R1-2, C5-6): all 31 ✓ Leaf
  NE-NE (R1-2, C7-8): all 31 ✓ Leaf
  NE-SW (R3-4, C5-6): all 31 ✓ Leaf
  NE-SE (R3-4, C7-8): all 35 ✓ Leaf
SW (R5-8, C1-4): all 3 ✓ 1 leaf
SE (R5-8, C5-8): all 3 ✓ 1 leaf
Leaf nodes = 4 + 4 + 1 + 1 = 10   Internal = 3

GIS CalculationUTF-8

Answer: RLE = 32 values (50% decrease). Quadtree = 10 leaf nodes, 3 internal. This grid compresses well because the bottom half is entirely value 3, and the top has regular 2×2 blocks.

Q4. 8×8 Grid — RLE & Quadtree VERIFIED

Exam: 2076 Bhadra Q3b [6 Marks]

Question: Perform RLE and Quadtree encoding for the following 8×8 raster.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	1	1	1	1	2	2	2	2
R2	1	1	1	1	2	2	2	2
R3	1	1	1	1	2	2	2	2
R4	1	1	1	1	2	2	2	2
R5	3	3	3	3	4	4	5	5
R6	3	3	3	3	4	4	5	5
R7	3	3	3	3	4	4	5	5
R8	3	3	3	3	4	4	5	5

Full Raster = 8 × 8 = 64 cells

⚙ RLE_2076Bhadra.calc

// Run-Length Encoding
Row 1–4: (1,4)(2,4)                // 2 pairs each × 4 rows = 8
Row 5–8: (3,4)(4,2)(5,2)         // 3 pairs each × 4 rows = 12
// Total = 8 + 12 = 20 pairs
Total RLE = 20 pairs = 40 values
% Decrease = (64 − 40) / 64 × 100 = 37.5%
// Quadtree
NW (R1-4, C1-4): all 1 ✓ Leaf
NE (R1-4, C5-8): all 2 ✓ Leaf
SW (R5-8, C1-4): all 3 ✓ Leaf
SE (R5-8, C5-8): mixed → 4 sub-quads all uniform: 4,5,4,5 → 4 leaves

GIS CalculationUTF-8

Answer: RLE = 40 values (37.5% decrease). Quadtree = 7 leaf nodes, 2 internal. Quadtree is extremely efficient here because the grid naturally aligns with power-of-2 boundaries.

Q5. 8×8 Grid — RLE & Quadtree VERIFIED

Exam: 2075 Bhadra Q3a [8 Marks]

Question: Encode the following land-use raster using RLE and Quadtree compression.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	10	10	9	7	7	7
R2	12	12	10	10	2	6	6	6
R3	4	4	1	1	3	3	8	8
R4	4	4	1	1	3	3	5	5
R5	4	4	4	4	3	3	3	3
R6	4	4	4	4	3	3	3	3
R7	4	4	4	4	3	3	3	3
R8	4	4	4	4	3	3	3	3

Full Raster = 8 × 8 = 64 cells

⚙ RLE_2075Bhadra.calc

// Run-Length Encoding
Row 1: (12,2)(10,2)(9,1)(7,3)   // 4 pairs
Row 2: (12,2)(10,2)(2,1)(6,3)   // 4 pairs
Row 3: (4,2)(1,2)(3,2)(8,2)    // 4 pairs
Row 4: (4,2)(1,2)(3,2)(5,2)    // 4 pairs
Row 5: (4,4)(3,4)                // 2 pairs
Row 6: (4,4)(3,4)                // 2 pairs
Row 7: (4,4)(3,4)                // 2 pairs
Row 8: (4,4)(3,4)                // 2 pairs
// Total = 4+4+4+4+2+2+2+2 = 24 pairs
Total RLE = 24 pairs = 48 values
% Decrease = (64 − 48) / 64 × 100 = 25.0%
// Quadtree: NW mixed(4 sub → all 2×2 uniform: 12,10,4,1 = 4 leaves)
//           NE mixed(4 sub → all mixed → 16 leaves at 1×1)
//           SW: all 4 → 1 leaf   SE: all 3 → 1 leaf

GIS CalculationUTF-8

⚙ Quadtree_2075Bhadra.calc

// Quadtree Decomposition
Root (8×8): Not uniform → split
NW (R1-4, C1-4): mixed → split
  NW-NW: all 12 ✓   NW-NE: all 10 ✓
  NW-SW: all  4 ✓   NW-SE: all  1 ✓
  // 4 leaves
NE (R1-4, C5-8): mixed → split
  NE-NW: {9,7,2,6} → 4 leaves  NE-NE: {7,7,6,6} → 4 leaves
  NE-SW: {3,3,3,3} ✓ Leaf     NE-SE: {8,8,5,5} → 4 leaves
  // 1 + 12 = 13 leaves + 4 internals
SW (R5-8, C1-4): all 4 ✓ 1 leaf
SE (R5-8, C5-8): all 3 ✓ 1 leaf
Total leaves = 4 + 13 + 1 + 1 = 19
Internal nodes = 1 + 1 + 4 = 6
Total nodes = 25

GIS CalculationUTF-8

Answer: RLE = 48 values (25.0% decrease). Quadtree = 19 leaf nodes, 6 internal. The NE quadrant is highly heterogeneous, limiting compression.

Q6. 8×8 Land-Use Grid (F, W, O, S) VERIFIED

Exam: 2073 Magh Q3 [6 Marks]

Question: Encode the following land-use raster using RLE and Quadtree. F=Forest, W=Water, O=Open, S=Settlement.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	F	F	F	F	W	W	W	W
R2	F	F	F	F	W	W	W	W
R3	F	F	F	F	W	W	W	W
R4	F	F	F	F	W	W	W	W
R5	O	O	O	O	S	S	S	S
R6	O	O	O	O	S	S	S	S
R7	O	O	O	O	S	S	S	S
R8	O	O	O	O	S	S	S	S

Full Raster = 8 × 8 = 64 cells

⚙ RLE_LandUse_2073Magh.calc

// This is a perfectly aligned grid — best case!
Row 1–4: (F,4)(W,4)   // 2 pairs × 4 rows = 8
Row 5–8: (O,4)(S,4)   // 2 pairs × 4 rows = 8
Total RLE = 16 pairs = 32 values
% Decrease = (64 − 32) / 64 × 100 = 50.0%
// Quadtree — perfect alignment with 4×4 quadrants
NW: all F ✓   NE: all W ✓
SW: all O ✓   SE: all S ✓
Quadtree = 1 root + 4 leaves = 5 nodes total
// This is the MINIMUM possible quadtree for an 8×8 grid!
// Only 4 values needed vs. 64 — 93.75% decrease

GIS CalculationUTF-8

Answer: RLE = 32 values (50% decrease). Quadtree = just 4 leaf nodes + 1 root (93.75% decrease). This is the ideal case — four uniform quadrants perfectly aligned with power-of-2 boundaries.

Q7. 8×8 Grid — Quadtree Compression VERIFIED

Exam: 2073 Bhadra Q3c [6 Marks]

Question: Compress the following raster using Quadtree encoding.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	5	5	6	6	6	6
R2	12	12	5	5	6	6	6	6
R3	61	61	62	62	6	6	6	6
R4	61	61	62	62	6	6	6	6
R5	7	7	7	7	9	9	9	9
R6	7	7	7	7	9	9	9	9
R7	7	7	7	7	9	9	9	9
R8	7	7	7	7	9	9	9	9

Full Raster = 8 × 8 = 64 cells

⚙ Quadtree_2073Bhadra.calc

// Quadtree Decomposition
Root (8×8): Not uniform → split
NW (R1-4, C1-4): mixed → split
  NW-NW (R1-2, C1-2): all 12 ✓ Leaf
  NW-NE (R1-2, C3-4): all  5 ✓ Leaf
  NW-SW (R3-4, C1-2): all 61 ✓ Leaf
  NW-SE (R3-4, C3-4): all 62 ✓ Leaf
  // NW = 1 internal + 4 leaves
NE (R1-4, C5-8): all 6 ✓ 1 leaf
SW (R5-8, C1-4): all 7 ✓ 1 leaf
SE (R5-8, C5-8): all 9 ✓ 1 leaf
Total leaves = 4 + 1 + 1 + 1 = 7
Internal = 1 (root) + 1 (NW) = 2

GIS CalculationUTF-8

Answer: Quadtree = 7 leaf nodes, 2 internal, 9 total nodes. Only 7 values stored vs 64 — 89.06% decrease. This grid is well-structured with uniform 2×2 and 4×4 blocks, making quadtree very efficient.

Q8. 8×8 Grid — RLE, Quadtree, Block & Chain NEW

Exam: 2080 Chaitra Q7 [4+2+2+2 = 10 Marks]

Question: Explain run length encoding using the following raster data. Also produce each of the following encoding for this data: (a) Quad tree encoding (b) Block encoding (c) Chain encoding.

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	31	31	25	25	3	3
R2	25	25	31	31	25	25	3	3
R3	25	25	31	31	25	25	3	3
R4	25	25	31	31	25	25	3	3
R5	27	27	27	27	27	27	27	27
R6	27	27	27	27	27	27	27	27
R7	27	27	27	27	27	27	35	27
R8	27	27	27	27	27	27	27	27

Full Raster = 8 × 8 = 64 cells

Solution (a) — Run-Length Encoding

⚙ RLE_Q8.calc

// Run-Length Encoding (row by row)
Row 1: (25,2)(31,2)(25,2)(3,2)     // 4 pairs
Row 2: (25,2)(31,2)(25,2)(3,2)     // 4 pairs
Row 3: (25,2)(31,2)(25,2)(3,2)     // 4 pairs
Row 4: (25,2)(31,2)(25,2)(3,2)     // 4 pairs
Row 5: (27,8)                          // 1 pair
Row 6: (27,8)                          // 1 pair
Row 7: (27,6)(35,1)(27,1)           // 3 pairs
Row 8: (27,8)                          // 1 pair
// Total = 4+4+4+4+1+1+3+1 = 22 pairs
Total RLE = 22 pairs = 44 values
% Decrease = (64 − 44) / 64 × 100
% Decrease = 31.25%

GIS CalculationUTF-8

Solution (b) — Quadtree Encoding

⚙ Quadtree_Q8.calc

// Quadtree Decomposition (8×8)
Root (8×8): Not uniform → split
// ── NW Quadrant (R1-4, C1-4) ──
NW (4×4): mixed → split
  NW-NW (R1-2, C1-2): all 25 ✓ Leaf
  NW-NE (R1-2, C3-4): all 31 ✓ Leaf
  NW-SW (R3-4, C1-2): all 25 ✓ Leaf
  NW-SE (R3-4, C3-4): all 31 ✓ Leaf
  // NW = 1 internal + 4 leaves
// ── NE Quadrant (R1-4, C5-8) ──
NE (4×4): mixed → split
  NE-NW (R1-2, C5-6): all 25 ✓ Leaf
  NE-NE (R1-2, C7-8): all 3 ✓ Leaf
  NE-SW (R3-4, C5-6): all 25 ✓ Leaf
  NE-SE (R3-4, C7-8): all 3 ✓ Leaf
  // NE = 1 internal + 4 leaves
// ── SW Quadrant (R5-8, C1-4) ──
SW (4×4): all 27 ✓ 1 leaf
// ── SE Quadrant (R5-8, C5-8) ──
SE (4×4): mixed → split
  SE-NW (R5-6, C5-6): all 27 ✓ Leaf
  SE-NE (R5-6, C7-8): all 27 ✓ Leaf
  SE-SW (R7-8, C5-6): all 27 ✓ Leaf
  SE-SE (R7-8, C7-8): {35,27,27,27} → 4 leaves (1×1 each)
  // SE = 2 internals + 7 leaves
Total leaf nodes = 4 + 4 + 1 + 7 = 16
Internal nodes = 1(root) + 1(NW) + 1(NE) + 2(SE) = 5
Total nodes = 21

GIS CalculationUTF-8

Solution (c) — Block Encoding

⚙ Block_Q8.calc

// Block Encoding: (value, r1, c1, r2, c2)
Block 1: (25, 1,1, 4,2)   // 4×2 = 8 cells
Block 2: (31, 1,3, 4,4)   // 4×2 = 8 cells
Block 3: (25, 1,5, 4,6)   // 4×2 = 8 cells
Block 4: ( 3, 1,7, 4,8)   // 4×2 = 8 cells
Block 5: (27, 5,1, 8,6)   // 4×6 = 24 cells
Block 6: (27, 5,7, 6,8)   // 2×2 = 4 cells
Block 7: (35, 7,7, 7,7)   // 1×1 = 1 cell
Block 8: (27, 7,8, 7,8)   // 1×1 = 1 cell
Block 9: (27, 8,7, 8,8)   // 1×2 = 2 cells
                            // Check: 8+8+8+8+24+4+1+1+2 = 64 ✓
Total = 9 blocks × 5 values/block = 45 values
% Decrease = (64 − 45) / 64 × 100
% Decrease = 29.69%

GIS CalculationUTF-8

Solution (d) — Chain Encoding

Chain encoding traces the boundary of each region using Freeman chain codes. Using 4-direction codes: 0=East, 1=South, 2=West, 3=North. Format: (start_row, start_col, value, chain)

⚙ Chain_Q8.calc

// Chain Encoding (Freeman 4-direction)
// 0=East  1=South  2=West  3=North
Region 25 (R1-4, C1-2): Start (1,1)
  Chain: 0,0, 1,1,1,1, 2,2, 3,3,3,3  // 12 codes
Region 31 (R1-4, C3-4): Start (1,3)
  Chain: 0,0, 1,1,1,1, 2,2, 3,3,3,3  // 12 codes
Region 25 (R1-4, C5-6): Start (1,5)
  Chain: 0,0, 1,1,1,1, 2,2, 3,3,3,3  // 12 codes
Region 3 (R1-4, C7-8): Start (1,7)
  Chain: 0,0, 1,1,1,1, 2,2, 3,3,3,3  // 12 codes
Region 27 (R5-8, C1-8, hole at R7C7): Start (5,1)
  Outer: 0,0,0,0,0,0,0,0, 1,1,1,1, 2,2,2,2,2,2,2,2, 3,3,3,3 // 24
  Hole at (7,7): 0, 1, 2, 3  // 4 codes
Region 35 (R7, C7): Start (7,7)
  Chain: 0, 1, 2, 3  // 4 codes (single cell)

GIS CalculationUTF-8

Answer: RLE = 44 values (31.25% decrease). Quadtree = 16 leaves + 5 internal = 21 nodes. Block = 45 values (29.69% decrease). The single cell of value 35 at (R7,C7) disrupts compression in the SE quadrant.

Q9. 8×8 Land-Use Grid — Full Raster, RLE, Quadtree & Value Point NEW

Exam: 2073 Magh Q3 [6 Marks]

Question: How is the following raster encoded using full raster encoding, run length encoding, quad tree encoding, and value point encoding? (F=Forest, W=Water, O=Open Space, S=Settlement)

	C1	C2	C3	C4	C5	C6	C7	C8
R1	F	F	F	F	W	W	F	F
R2	F	F	F	F	W	W	F	F
R3	F	F	F	F	O	O	F	F
R4	F	F	F	F	O	O	F	F
R5	F	F	F	F	S	S	S	S
R6	F	F	F	F	S	S	S	S
R7	F	F	F	F	S	S	W	W
R8	F	F	F	F	S	S	W	W

Full Raster = 8 × 8 = 64 cells

Solution (a) — Full Raster Encoding

Every cell value is stored individually, row by row:

⚙ FullRaster_Q9.calc

// Full Raster — store every cell value
Row 1: F F F F W W F F
Row 2: F F F F W W F F
Row 3: F F F F O O F F
Row 4: F F F F O O F F
Row 5: F F F F S S S S
Row 6: F F F F S S S S
Row 7: F F F F S S W W
Row 8: F F F F S S W W
Total = 64 values // no compression

GIS CalculationUTF-8

Solution (b) — Run-Length Encoding

⚙ RLE_Q9.calc

// Run-Length Encoding (row by row)
Row 1: (F,4)(W,2)(F,2)          // 3 pairs
Row 2: (F,4)(W,2)(F,2)          // 3 pairs
Row 3: (F,4)(O,2)(F,2)          // 3 pairs
Row 4: (F,4)(O,2)(F,2)          // 3 pairs
Row 5: (F,4)(S,4)               // 2 pairs
Row 6: (F,4)(S,4)               // 2 pairs
Row 7: (F,4)(S,2)(W,2)          // 3 pairs
Row 8: (F,4)(S,2)(W,2)          // 3 pairs
// Total = 3+3+3+3+2+2+3+3 = 22 pairs
Total RLE = 22 pairs = 44 values
% Decrease = (64 − 44) / 64 × 100
% Decrease = 31.25%

GIS CalculationUTF-8

Solution (c) — Quadtree Encoding

⚙ Quadtree_Q9.calc

// Quadtree Decomposition (8×8)
Root (8×8): Not uniform → split
NW (R1-4, C1-4): all F ✓ 1 leaf
NE (R1-4, C5-8): mixed → split
  NE-NW (R1-2, C5-6): all W ✓ Leaf
  NE-NE (R1-2, C7-8): all F ✓ Leaf
  NE-SW (R3-4, C5-6): all O ✓ Leaf
  NE-SE (R3-4, C7-8): all F ✓ Leaf
  // NE = 1 internal + 4 leaves
SW (R5-8, C1-4): all F ✓ 1 leaf
SE (R5-8, C5-8): mixed → split
  SE-NW (R5-6, C5-6): all S ✓ Leaf
  SE-NE (R5-6, C7-8): all S ✓ Leaf
  SE-SW (R7-8, C5-6): all S ✓ Leaf
  SE-SE (R7-8, C7-8): all W ✓ Leaf
  // SE = 1 internal + 4 leaves
Total leaf nodes = 1 + 4 + 1 + 4 = 10
Internal nodes = 1(root) + 1(NE) + 1(SE) = 3
Total nodes = 13

GIS CalculationUTF-8

Solution (d) — Value Point Encoding

Each unique value is listed with all cell positions where it occurs: (value, row, col)

⚙ ValuePoint_Q9.calc

// Value Point Encoding
// Lists each unique value with every (row,col) where it occurs
F (Forest): 40 occurrences
  R1-8 C1-4 (32 cells) + R1-2 C7-8 (4) + R3-4 C7-8 (4)
  = (1,1)(1,2)(1,3)(1,4)...(8,4), (1,7)(1,8)...(4,8)
W (Water): 8 occurrences
  R1-2 C5-6 (4 cells) + R7-8 C7-8 (4 cells)
  = (1,5)(1,6)(2,5)(2,6)(7,7)(7,8)(8,7)(8,8)
O (Open): 4 occurrences
  = (3,5)(3,6)(4,5)(4,6)
S (Settlement): 12 occurrences
  R5-6 C5-8 (8 cells) + R7-8 C5-6 (4 cells)
  = (5,5)(5,6)(5,7)(5,8)(6,5)(6,6)(6,7)(6,8)(7,5)(7,6)(8,5)(8,6)
Check: 40 + 8 + 4 + 12 = 64 ✓

GIS CalculationUTF-8

Answer: Full raster = 64 values. RLE = 44 values (31.25% decrease). Quadtree = 10 leaves + 3 internal = 13 nodes. Value point encoding groups 64 cells under 4 unique values (F:40, W:8, O:4, S:12).

Q10. Vector Data Model — Label Components NEW

Exam: 2074 Bhadra Q1c [2 Marks]

Question: Label vertex, node, arc, and polygon for the following figure.

Given Figure

Labeled Figure — Nodes, Vertices, Arcs & Polygons

Key Definitions

Node: A topological junction point where two or more arcs meet. Nodes are always at the endpoints of arcs. (Marked as red circles)

Vertex: An intermediate point along an arc that defines its shape/curvature. A vertex is NOT a junction — only one arc passes through it. (Marked as blue diamonds)

Arc: A line segment connecting two nodes. May contain vertices along its length. (Labeled in green)

Polygon: A closed area bounded by one or more arcs forming a complete ring. (Labeled in purple)

Solution — Identifying Each Component

⚙ VectorLabel_Q10.calc

// ═══ NODES (9 total) ═══
// Rule: a node is where 2+ arcs meet
N1  — top-left corner      (arcs: a8, a1)
N2  — top-centre           (arcs: a1, a2, a9)  // 3 arcs!
N3  — top-right corner     (arcs: a2, a3)
N4  — right                (arcs: a3, a10, a4)  // 3 arcs!
N5  — bottom-right corner  (arcs: a4, a5)
N6  — bottom-centre        (arcs: a5, a6, a11)  // 3 arcs!
N7  — bottom-left corner   (arcs: a6, a7)
N8  — left                 (arcs: a7, a8, a12)  // 3 arcs!
N9  — CENTRE junction     (arcs: a9, a10, a11, a12)  // 4 arcs!
// ═══ ARCS (12 total) ═══
// 8 boundary arcs + 4 internal arcs
a1  N1 → N2   (outer, top)         has vertex v1
a2  N2 → N3   (outer, top-right)   has vertex v2
a3  N3 → N4   (outer, right)
a4  N4 → N5   (outer, bottom-right)
a5  N5 → N6   (outer, bottom)
a6  N6 → N7   (outer, bottom-left)  has vertex v3
a7  N7 → N8   (outer, left)
a8  N8 → N1   (outer, top-left)
a9  N2 → N9   (internal, vertical)
a10 N9 → N4   (internal, horizontal)
a11 N9 → N6   (internal, diagonal ↘)
a12 N8 → N9   (internal, diagonal ↗)
// ═══ VERTICES (3 total) ═══
// Points where boundary bends but NO intersection
v1  on arc a1 (between N1 and N2)
v2  on arc a2 (between N2 and N3)
v3  on arc a6 (between N6 and N7)
// ═══ POLYGONS (5 total) ═══
P1  bounded by  a8, a1, a9, a12   (top-left region)
P2  bounded by  a9, a2, a3, a10   (top-right region)
P3  bounded by  a10, a4, a5, a11  (bottom-right region)
P4  bounded by  a11, a6, a7, a12  (bottom-left region)
P5  // = Universe polygon (outside the figure)

GIS CalculationUTF-8

Summary Table

Component	Count	List
Nodes	9	N1, N2, N3, N4, N5, N6, N7, N8, N9
Arcs	12	a1–a8 (boundary) + a9, a10, a11, a12 (internal)
Vertices	3	v1 (on a1), v2 (on a2), v3 (on a6)
Polygons	5	P1 (top-left), P2 (top-right), P3 (bottom-right), P4 (bottom-left), P5 (outside/universe)

Component

Count

List

Nodes

N1, N2, N3, N4, N5, N6, N7, N8, N9

Arcs

a1–a8 (boundary) + a9, a10, a11, a12 (internal)

Vertices

v1 (on a1), v2 (on a2), v3 (on a6)

Polygons

P1 (top-left), P2 (top-right), P3 (bottom-right), P4 (bottom-left), P5 (outside/universe)

Answer: The figure has 9 nodes (N1–N9 — all boundary corners plus central junction N9), 12 arcs (8 boundary + 4 internal all radiating from N9), 3 vertices (v1, v2, v3 — bends on the boundary that are not junctions), and 5 polygons (4 internal regions + universe polygon).

Q11. Vector Data Model — Label & Write Vector Models NEW

Exam: 2071 Bhadra Q3b [6 Marks]

Question: Label vertex, node, arc, and polygon for the given figure and write different vector models of the given figure.

Part (a) — Labeled Figure

From the figure: 9 Nodes (N1–N9), 12 Arcs (a1–a12), 3 Vertices (v1–v3), 5 Polygons (P1–P4 + P5 universe).

Part (b) — Three Vector Data Models

Model 1: Spaghetti Model (No Topology)

Each polygon is stored as an independent, closed list of coordinates. Shared boundaries are duplicated. No relationship between polygons is recorded.

⚙ Spaghetti_Q11.calc

// Spaghetti Model — each polygon = independent ring
// Shared edges stored TWICE → redundant
P1: N8 → N1 → v1 → N2 → N9 → N8
    // edge N8–N9 duplicated in P4, P5
    // edge N2–N9 duplicated in P2
P2: N2 → v2 → N3 → N4 → N9 → N2
    // edge N9–N4 duplicated in P3
P3: N9 → N4 → N5 → N6 → N9
    // edge N9–N6 duplicated in P4
P4: N9 → N6 → v3 → N7 → N8 → N9
// Problem: edge N2–N9 appears in P1 & P2 (stored twice!)

GIS CalculationUTF-8

Model 2: Topological Model (Node-Arc-Polygon)

Stores three related tables. No shared boundary is duplicated. Each arc records its left and right polygon.

⚙ Topological_Q11.calc

// ═══════ NODE TABLE ═══════
Node  |  Arcs at this node
 N1   |  a8, a1
 N2   |  a1, a2, a9
 N3   |  a2, a3
 N4   |  a3, a10, a4
 N5   |  a4, a5
 N6   |  a5, a11, a6
 N7   |  a6, a7
 N8   |  a7, a12, a8
 N9   |  a9, a10, a11, a12   // central hub
// ═══════ ARC TABLE ═══════
Arc  | Start | End | Left Poly | Right Poly | Vertices
 a1   |  N1    | N2  |  P1        |  P5 (out)   |  v1
 a2   |  N2    | N3  |  P2        |  P5 (out)   |  v2
 a3   |  N3    | N4  |  P2        |  P5 (out)   |  —
 a4   |  N4    | N5  |  P3        |  P5 (out)   |  —
 a5   |  N5    | N6  |  P3        |  P5 (out)   |  —
 a6   |  N6    | N7  |  P4        |  P5 (out)   |  v3
 a7   |  N7    | N8  |  P4        |  P5 (out)   |  —
 a8   |  N8    | N1  |  P1        |  P5 (out)   |  —
 a9   |  N2    | N9  |  P1        |  P2         |  —
 a10  |  N9    | N4  |  P2        |  P3         |  —
 a11  |  N9    | N6  |  P3        |  P4         |  —
 a12  |  N8    | N9  |  P4        |  P1         |  —
// Note: internal arcs (a9–a12) have TWO internal
// polygons (left & right). Boundary arcs have P5 on one side.
// ═══════ POLYGON TABLE ═══════
Poly | Bounding Arcs
 P1   |  a8, a1, a9, a12     // top-left region
 P2   |  a9, a2, a3, a10     // top-right region
 P3   |  a10, a4, a5, a11    // bottom-right region
 P4   |  a11, a6, a7, a12    // bottom-left region
 P5   |  a1–a8 (all boundary) // universe / outside
// ═══════ VERTEX TABLE ═══════
Vertex | On Arc | Position
 v1     |  a1     |  between N1 and N2  // top-left bend
 v2     |  a2     |  between N2 and N3  // top-right bend
 v3     |  a6     |  between N6 and N7  // bottom-left bend
// Advantage: shared edges stored ONCE
// e.g. arc a9 (N2–N9) separates P1 and P2
//      → no duplication unlike spaghetti model

GIS CalculationUTF-8

Model 3: Network Model

⚙ Network_Q11.calc

// Network Model — connectivity & flow
// Used for: roads, pipelines, utility networks
Nodes = junctions (N1–N9)
Links = arcs with cost/impedance attributes
Link  | From | To | Cost
 a1    |  N1   | N2 |  d(N1,N2)
 a2    |  N2   | N3 |  d(N2,N3)
 ...   |  ...  | .. |  ...
 a9    |  N2   | N9 |  d(N2,N9)
 a10   |  N9   | N4 |  d(N9,N4)
// Focuses on shortest paths / connectivity
// Does NOT store polygon areas
// Best for route analysis, not area analysis

GIS CalculationUTF-8

Comparison of Three Models

Feature	Spaghetti	Topological	Network
Topology stored?	No	Yes	Partial
Shared edges duplicated?	Yes	No	No
Polygon info?	Yes (redundant)	Yes (efficient)	No
Neighbour queries?	Slow	Fast	N/A
Routing / flow?	No	No	Yes
Storage	Large	Medium	Small
Best for	Simple display	Spatial analysis	Transportation

Feature

Spaghetti

Topological

Network

Topology stored?

Yes

Partial

Shared edges duplicated?

Yes

Polygon info?

Yes (redundant)

Yes (efficient)

Neighbour queries?

Slow

Fast

N/A

Routing / flow?

Yes

Storage

Large

Medium

Small

Best for

Simple display

Spatial analysis

Transportation

Answer: (1) Spaghetti model stores each polygon as independent coordinate rings — simple but redundant (shared edges duplicated). (2) Topological (Node-Arc-Polygon) model eliminates redundancy with Node, Arc, and Polygon tables; each arc records left/right polygon, enabling neighbour queries. (3) Network model focuses on node connectivity and arc costs for routing — does not store area polygons.

	C1	C2	C3	C4	C5	C6
R1	25	25	25	25	25	25
R2	25	25	25	25	25	25
R3	25	25	25	25	25	25
R4	5	5	5	10	10	10
R5	5	5	5	12	12	12
R6	5	5	5	15	12	12

	C1	C2	C3	C4	C5	C6	C7	C8
R1	88	88	75	34	9	9	9	9
R2	88	88	33	75	9	9	9	9
R3	88	88	88	34	9	9	9	9
R4	77	77	77	77	9	9	9	9
R5	56	56	56	56	56	56	10	10
R6	56	56	56	56	33	25	10	10
R7	56	56	56	56	33	33	33	9
R8	56	56	56	56	33	33	33	33

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	25	25	31	31	31	31
R2	25	25	25	25	31	31	31	31
R3	25	25	27	27	31	31	35	35
R4	25	25	27	27	31	31	35	35
R5	3	3	3	3	3	3	3	3
R6	3	3	3	3	3	3	3	3
R7	3	3	3	3	3	3	3	3
R8	3	3	3	3	3	3	3	3

	C1	C2	C3	C4	C5	C6	C7	C8
R1	1	1	1	1	2	2	2	2
R2	1	1	1	1	2	2	2	2
R3	1	1	1	1	2	2	2	2
R4	1	1	1	1	2	2	2	2
R5	3	3	3	3	4	4	5	5
R6	3	3	3	3	4	4	5	5
R7	3	3	3	3	4	4	5	5
R8	3	3	3	3	4	4	5	5

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	10	10	9	7	7	7
R2	12	12	10	10	2	6	6	6
R3	4	4	1	1	3	3	8	8
R4	4	4	1	1	3	3	5	5
R5	4	4	4	4	3	3	3	3
R6	4	4	4	4	3	3	3	3
R7	4	4	4	4	3	3	3	3
R8	4	4	4	4	3	3	3	3

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	5	5	6	6	6	6
R2	12	12	5	5	6	6	6	6
R3	61	61	62	62	6	6	6	6
R4	61	61	62	62	6	6	6	6
R5	7	7	7	7	9	9	9	9
R6	7	7	7	7	9	9	9	9
R7	7	7	7	7	9	9	9	9
R8	7	7	7	7	9	9	9	9

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	31	31	25	25	3	3
R2	25	25	31	31	25	25	3	3
R3	25	25	31	31	25	25	3	3
R4	25	25	31	31	25	25	3	3
R5	27	27	27	27	27	27	27	27
R6	27	27	27	27	27	27	27	27
R7	27	27	27	27	27	27	35	27
R8	27	27	27	27	27	27	27	27

	C1	C2	C3	C4	C5	C6
R1	25	25	25	25	25	25
R2	25	25	25	25	25	25
R3	25	25	25	25	25	25
R4	5	5	5	10	10	10
R5	5	5	5	12	12	12
R6	5	5	5	15	12	12

	C1	C2	C3	C4	C5	C6	C7	C8
R1	88	88	75	34	9	9	9	9
R2	88	88	33	75	9	9	9	9
R3	88	88	88	34	9	9	9	9
R4	77	77	77	77	9	9	9	9
R5	56	56	56	56	56	56	10	10
R6	56	56	56	56	33	25	10	10
R7	56	56	56	56	33	33	33	9
R8	56	56	56	56	33	33	33	33

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	25	25	31	31	31	31
R2	25	25	25	25	31	31	31	31
R3	25	25	27	27	31	31	35	35
R4	25	25	27	27	31	31	35	35
R5	3	3	3	3	3	3	3	3
R6	3	3	3	3	3	3	3	3
R7	3	3	3	3	3	3	3	3
R8	3	3	3	3	3	3	3	3

	C1	C2	C3	C4	C5	C6	C7	C8
R1	1	1	1	1	2	2	2	2
R2	1	1	1	1	2	2	2	2
R3	1	1	1	1	2	2	2	2
R4	1	1	1	1	2	2	2	2
R5	3	3	3	3	4	4	5	5
R6	3	3	3	3	4	4	5	5
R7	3	3	3	3	4	4	5	5
R8	3	3	3	3	4	4	5	5

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	10	10	9	7	7	7
R2	12	12	10	10	2	6	6	6
R3	4	4	1	1	3	3	8	8
R4	4	4	1	1	3	3	5	5
R5	4	4	4	4	3	3	3	3
R6	4	4	4	4	3	3	3	3
R7	4	4	4	4	3	3	3	3
R8	4	4	4	4	3	3	3	3

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	5	5	6	6	6	6
R2	12	12	5	5	6	6	6	6
R3	61	61	62	62	6	6	6	6
R4	61	61	62	62	6	6	6	6
R5	7	7	7	7	9	9	9	9
R6	7	7	7	7	9	9	9	9
R7	7	7	7	7	9	9	9	9
R8	7	7	7	7	9	9	9	9

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	31	31	25	25	3	3
R2	25	25	31	31	25	25	3	3
R3	25	25	31	31	25	25	3	3
R4	25	25	31	31	25	25	3	3
R5	27	27	27	27	27	27	27	27
R6	27	27	27	27	27	27	27	27
R7	27	27	27	27	27	27	35	27
R8	27	27	27	27	27	27	27	27

	C1	C2	C3	C4	C5	C6
R1	25	25	25	25	25	25
R2	25	25	25	25	25	25
R3	25	25	25	25	25	25
R4	5	5	5	10	10	10
R5	5	5	5	12	12	12
R6	5	5	5	15	12	12

	C1	C2	C3	C4	C5	C6	C7	C8
R1	88	88	75	34	9	9	9	9
R2	88	88	33	75	9	9	9	9
R3	88	88	88	34	9	9	9	9
R4	77	77	77	77	9	9	9	9
R5	56	56	56	56	56	56	10	10
R6	56	56	56	56	33	25	10	10
R7	56	56	56	56	33	33	33	9
R8	56	56	56	56	33	33	33	33

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	25	25	31	31	31	31
R2	25	25	25	25	31	31	31	31
R3	25	25	27	27	31	31	35	35
R4	25	25	27	27	31	31	35	35
R5	3	3	3	3	3	3	3	3
R6	3	3	3	3	3	3	3	3
R7	3	3	3	3	3	3	3	3
R8	3	3	3	3	3	3	3	3

	C1	C2	C3	C4	C5	C6	C7	C8
R1	1	1	1	1	2	2	2	2
R2	1	1	1	1	2	2	2	2
R3	1	1	1	1	2	2	2	2
R4	1	1	1	1	2	2	2	2
R5	3	3	3	3	4	4	5	5
R6	3	3	3	3	4	4	5	5
R7	3	3	3	3	4	4	5	5
R8	3	3	3	3	4	4	5	5

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	10	10	9	7	7	7
R2	12	12	10	10	2	6	6	6
R3	4	4	1	1	3	3	8	8
R4	4	4	1	1	3	3	5	5
R5	4	4	4	4	3	3	3	3
R6	4	4	4	4	3	3	3	3
R7	4	4	4	4	3	3	3	3
R8	4	4	4	4	3	3	3	3

	C1	C2	C3	C4	C5	C6	C7	C8
R1	12	12	5	5	6	6	6	6
R2	12	12	5	5	6	6	6	6
R3	61	61	62	62	6	6	6	6
R4	61	61	62	62	6	6	6	6
R5	7	7	7	7	9	9	9	9
R6	7	7	7	7	9	9	9	9
R7	7	7	7	7	9	9	9	9
R8	7	7	7	7	9	9	9	9

	C1	C2	C3	C4	C5	C6	C7	C8
R1	25	25	31	31	25	25	3	3
R2	25	25	31	31	25	25	3	3
R3	25	25	31	31	25	25	3	3
R4	25	25	31	31	25	25	3	3
R5	27	27	27	27	27	27	27	27
R6	27	27	27	27	27	27	27	27
R7	27	27	27	27	27	27	35	27
R8	27	27	27	27	27	27	27	27