Marching Squares and IDW Algorithm

Author: Win Aung Cho
12-Jun-2026 01:54:23 PM*

Contouring algorithms

Marching Squares algorithm

The Marching Squares algorithm converts this continuous grid into smooth contour lines (isolines) by analyzing cells independently.

Grid & Thresholding:

The space is divided into a grid of squares. For every corner of a square, a discrete value is evaluated against a specific threshold (or "isovalue").

Binary State:

If a corner's value is above the threshold, it is marked as 1 (or "inside"). If below, it is marked as 0 (or "outside").

Lookup & Connect:

Since a square has 4 corners, there are 2⁴ = 16 possible binary states for any given square. These 16 cases determine how the contour line traverses the square.

Javascript နဲ့ရေးထားတဲ့ Marching Squares algorithm နဲ့ grid data အသုံးပြုထားတာ

Advertise here

Java script code for marching squares algorithm

const grid = [
  [10, 15, 15, 20, 8, 6],
  [12, 15, 17, 19, 10, 10],
  [18, 20, 10, 16, 14, 16],
  [10, 10, 8, 18, 10, 16],
  [0, 0, 0, 10, 6, 12]
];
let gridsize = 100;

function getCellCase(grid, x, y, level) {
  // Get the 4 corners of a 2x2 cell
  const c00 = grid[y][x] >= level ? 1 : 0;
  const c10 = grid[y][x + 1] >= level ? 1 : 0;
  const c11 = grid[y + 1][x + 1] >= level ? 1 : 0;
  const c01 = grid[y + 1][x] >= level ? 1 : 0;

  // Convert to 4-bit integer
  return (c00 << 3) | (c10 << 2) | (c11 << 1) | c01;
}

function interpolate(val1, val2, level) {
  // Linear interpolation to find the exact point on the grid edge
  return (level - val1) / (val2 - val1);
}

function getContourLines(grid, level) {
  const lines = [];
  const rows = grid.length;
  const cols = grid[0].length;

  for (let y = 0; y < rows - 1; y++) {
    for (let x = 0; x < cols - 1; x++) {
      const cellCase = getCellCase(grid, x, y, level);
      //alert(level + ", " + cellCase);
      // Calculate coordinates for the 4 edges (top, right, bottom, left)
      const top = { x: x + interpolate(grid[y][x], grid[y][x + 1], level), y: y };
      const right = { x: x + 1, y: y + interpolate(grid[y][x + 1], grid[y + 1][x + 1], level) };
      const bottom = { x: x + interpolate(grid[y + 1][x], grid[y + 1][x + 1], level), y: y + 1 };
      const left = { x: x, y: y + interpolate(grid[y][x], grid[y + 1][x], level) };

      let p1 = null, p2 = null;

      // Define standard contour line segments based on the 16 cases
      switch (cellCase) {
        case 1: case 14: p1 = left; p2 = bottom; break;
        case 2: case 13: p1 = bottom; p2 = right; break;
        case 3: case 12: p1 = left; p2 = right; break;
        case 4: case 11: p1 = top; p2 = right; break;
        case 5: // Saddle point ambiguity
        case 10: p1 = left; p2 = top; p3 = bottom; p4 = right; break;
        case 6: case 9: p1 = top; p2 = bottom; break;
        case 7: case 8: p1 = left; p2 = top; break;
      }

      if (p1 != null && p2 != null) lines.push({ p1, p2 });
      if (cellCase === 5 || cellCase === 10) {
         // Handle saddle crossing properly
         // (Simplified to 2 segments for the basic 4-point case)
         lines.push({ p1: p3, p2: p4 });
      }
    }
  }
  return lines;
}

Lookup figures and binary code

Advertise here

Inverse Distance Weighting (IDW) algorithm

The Inverse Distance Weighting (IDW) algorithm is used for spatial interpolation, estimating unknown values from known scattered points by giving more weight to closer points.

Concept:

To calculate the value at an unknown point, IDW averages the values of nearby known points. The influence of each known point is inversely proportional to its distance from the unmeasured point.

Formula:

The weight wᵢ is calculated as wᵢ = 1 / dⁿ, where d is the distance and n is the power parameter (usually n=2). Closer points have exponentially greater weight.

Javascript နဲ့ရေးထားတဲ့ IDW & Marching Squares algorithm နဲ့ scatter points ကိုသုံးထားတာ

Advertise here

Javascript for IDW algorithm

const points = Array.from({ length: 50 }, () => ({
    x: Math.random() * 500,
    y: Math.random() * 500,
    value: Math.random() * 100
}));

function interpolateIDW(points, gridWidth, gridHeight, power = 2) {
    const grid = [];
    
    for (let y = 0; y < gridHeight; y++) {
        grid[y] = [];
        for (let x = 0; x < gridWidth; x++) {
            let totalWeight = 0;
            let totalValue = 0;
            let exactMatch = false;

            for (const p of points) {
                const dx = x - p.x;
                const dy = y - p.y;
                const distance = Math.sqrt(dx * dx + dy * dy);

                // If the grid pixel is exactly on a data point, use its value directly
                if (distance === 0) {
                    grid[y][x] = p.value;
                    exactMatch = true;
                    break;
                }

                const weight = 1 / Math.pow(distance, power);
                totalWeight += weight;
                totalValue += p.value * weight;
            }

            if (!exactMatch) {
                grid[y][x] = totalValue / totalWeight;
            }
        }
    }
    return grid;
}

Android Java နဲ့ရေးထားတဲ့ IDW & Marching Squares algorithm နဲ့ scatter points ကိုသုံးထားတာ

Advertise here

Author: Win Aung Cho
12-Jun-2026 01:54:23 PM*