algorithmgeometrypolygonmask

Tracing edges of pixels in a mask

I have a mask bitmap consisting of a 2D array of 1 and 0 values, which I would like to convert to a polygon, where the polygon traces exactly around the edges of the pixels. The regions in the mask can also contain holes. The output polygons should not contain any holes. An example is the following, where I would like to obtain the vertices of the polygon (the thick lines here).

enter image description here

Is there an easy to implement algorithm or set of algorithms for doing this?

Solution

  • Here is a rudimentary approach, that checks neighbors:

    const ctx = document.querySelector('#drawing').getContext('2d');

const matrix = [
  [0, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [1, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
];

renderGrid(ctx, matrix, { squareSize: 40, borderWidth: 1, outlineWidth: 4, padding: 10 });

function renderGrid(ctx, matrix, { squareSize = 40, borderWidth = 1, outlineWidth = 4, padding = 10 }) {
  const dpr = window.devicePixelRatio || 1;  // Handle high DPI screens
  const rows = matrix.length;
  const cols = matrix[0].length;
  const gridWidth = squareSize * cols;
  const gridHeight = squareSize * rows;
  const width = gridWidth + padding * 2;
  const height = gridHeight + padding * 2;

  // Set canvas size based on device pixel ratio
  ctx.canvas.width = width * dpr;
  ctx.canvas.height = height * dpr;

  // Scale the drawing based on the pixel ratio to ensure clarity
  ctx.scale(dpr, dpr);
  ctx.translate(0.5, 0.5);

  // Adjust size in CSS (logical pixels)
  ctx.canvas.style.width = `${width}px`;
  ctx.canvas.style.height = `${height}px`;

  // Calculate offsets for centering
  const xOffset = padding;
  const yOffset = padding;

  // Clear the canvas first
  ctx.clearRect(0, 0, width, height);

  // Draw the grid lines with offsets
  drawGrid(ctx, { gridWidth, gridHeight, rows, cols, squareSize, strokeStyle: 'black', borderWidth, xOffset, yOffset });

  // Draw the squares with offsets
  drawSquares(ctx, { matrix, rows, cols, squareSize, xOffset, yOffset });
  
  // Draw the outlines with offsets
  drawOutlines(ctx, { matrix, rows, cols, squareSize, outlineWidth, strokeStyle: 'black', xOffset, yOffset });
}

function drawSquares(ctx, { matrix, rows, cols, squareSize, xOffset, yOffset }) {
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (matrix[row][col] === 1) {
        ctx.fillStyle = 'hsla(120, 100%, 80%, 0.8)';
        ctx.fillRect(col * squareSize + xOffset, row * squareSize + yOffset, squareSize, squareSize);
      }
    }
  }
}

function drawOutlines(ctx, { matrix, rows, cols, squareSize, outlineWidth, strokeStyle, xOffset, yOffset }) {
  ctx.lineCap = 'round';
  const directions = [
    { dx: 0, dy: -1 },  // top
    { dx: 0, dy: 1 },   // bottom
    { dx: 1, dy: 0 },   // right
    { dx: -1, dy: 0 }   // left
  ];

  function isInBounds(row, col) {
    return row > -1 && row < rows && col > -1 && col < cols;
  }

  function getNeighbor({ row, col, dx, dy }) {
    const neighborRow = row + dy;
    const neighborCol = col + dx;
    return isInBounds(neighborRow, neighborCol) ? matrix[neighborRow][neighborCol] : null;
  }

  // Check for outlining each "group" of 1s
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      const type = matrix[row][col];
      
      if (type !== 1) continue;  // Skip if the current cell is not part of the group
      
      ctx.strokeStyle = strokeStyle;
      ctx.lineWidth = outlineWidth;

      for (const { dx, dy } of directions) {
        const neighbor = getNeighbor({ row, col, dx, dy });

        // Skip drawing if the neighbor is the same type
        if (neighbor === type) {
          continue;
        }

        // Calculate start and end points dynamically based on dx and dy
        const startX = col * squareSize + xOffset + (dx === 1 ? squareSize : 0);
        const startY = row * squareSize + yOffset + (dy === 1 ? squareSize : 0);
        const endX = startX + (dx !== 0 ? 0 : squareSize);
        const endY = startY + (dy !== 0 ? 0 : squareSize);

        // Draw the outline
        ctx.beginPath();
        ctx.moveTo(startX, startY);
        ctx.lineTo(endX, endY);
        ctx.stroke();
      }
    }
  }
}

function drawGrid(ctx, { gridWidth, gridHeight, rows, cols, squareSize, strokeStyle, borderWidth, xOffset, yOffset }) {
  // Draw the grid lines
  ctx.strokeStyle = strokeStyle;
  ctx.lineWidth = borderWidth;

  // Horizontal lines (draw between rows)
  for (let row = 1; row < rows; row++) {
    ctx.beginPath();
    ctx.moveTo(xOffset, row * squareSize + yOffset);
    ctx.lineTo(gridWidth + xOffset, row * squareSize + yOffset);
    ctx.stroke();
  }

  // Vertical lines (draw between columns)
  for (let col = 1; col < cols; col++) {
    ctx.beginPath();
    ctx.moveTo(col * squareSize + xOffset, yOffset);
    ctx.lineTo(col * squareSize + xOffset, gridHeight + yOffset);
    ctx.stroke();
  }

  // Draw the outer grid border
  ctx.strokeRect(xOffset, yOffset, gridWidth, gridHeight);
}
    #drawing {
  border: thin dashed red;
}
    <canvas id="drawing"></canvas>

    You can compute the merged polygon by create a unique set of points using sorted edges.

    const ctx = document.querySelector('#drawing').getContext('2d');

const matrix = [
  [0, 1, 0, 0, 0],
  [0, 1, 1, 1, 0],
  [1, 1, 0, 1, 0],
  [0, 1, 1, 1, 0],
];

renderGrid(ctx, matrix, {
  squareSize: 40,
  borderWidth: 1,
  outlineWidth: 4,
  padding: 10
});

// Main entry point to render the grid and polygons
function renderGrid(ctx, matrix, { squareSize = 40, borderWidth = 1, outlineWidth = 4, padding = 10 }) {
  const dpr = window.devicePixelRatio || 1;
  const rows = matrix.length;
  const cols = matrix[0].length;
  const gridWidth = squareSize * cols;
  const gridHeight = squareSize * rows;
  const width = gridWidth + padding * 2;
  const height = gridHeight + padding * 2;

  // Setup canvas with device pixel ratio for clarity
  setupCanvas(ctx, width, height, dpr);

  // Calculate offsets for centering
  const xOffset = padding;
  const yOffset = padding;

  // Clear the canvas first
  ctx.clearRect(0, 0, width, height);

  // Draw the grid and squares
  drawGrid(ctx, { gridWidth, gridHeight, rows, cols, squareSize, strokeStyle: 'black', borderWidth, xOffset, yOffset });
  drawSquares(ctx, { matrix, rows, cols, squareSize, xOffset, yOffset });

  // Process and render polygons
  const edges = extractEdgesFromMatrix(matrix, rows, cols, squareSize, xOffset, yOffset);
  const sortedEdges = chainEdgesIntoLoops(edges);
  renderPolygons(ctx, sortedEdges, outlineWidth, 'black');
}

// Setup the canvas size and scaling
function setupCanvas(ctx, width, height, dpr) {
  ctx.canvas.width = width * dpr;
  ctx.canvas.height = height * dpr;
  ctx.scale(dpr, dpr);
  ctx.translate(0.5, 0.5);
  ctx.canvas.style.width = `${width}px`;
  ctx.canvas.style.height = `${height}px`;
}

// Extract edges from the matrix
function extractEdgesFromMatrix(matrix, rows, cols, squareSize, xOffset, yOffset) {
  const uniqueEdges = new Set();

  function toggleEdge(edge) {
    const key = edge.join(',');
    if (uniqueEdges.has(key)) {
      uniqueEdges.delete(key); // Remove shared edges
    } else {
      uniqueEdges.add(key); // Add new unique edge
    }
  }

  // Traverse the matrix and toggle edges based on neighbors
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (matrix[row][col] === 1) {
        const tl = [col * squareSize + xOffset, row * squareSize + yOffset];
        const tr = [(col + 1) * squareSize + xOffset, row * squareSize + yOffset];
        const bl = [col * squareSize + xOffset, (row + 1) * squareSize + yOffset];
        const br = [(col + 1) * squareSize + xOffset, (row + 1) * squareSize + yOffset];

        toggleEdge([tl, tr]);
        toggleEdge([bl, br]);
        toggleEdge([tl, bl]);
        toggleEdge([tr, br]);
      }
    }
  }

  const edgePoints = Array.from(uniqueEdges).map(edge => edge.split(',').map(Number));
  return edgePoints.map(points => [
    [points[0], points[1]], 
    [points[2], points[3]]
  ]);
}

// Chain edges into continuous loops (polygons)
function chainEdgesIntoLoops(edges) {
  const loops = [];

  while (edges.length > 0) {
    const currentLoop = [];
    let currentEdge = edges.shift();
    currentLoop.push(currentEdge);

    while (true) {
      const nextEdgeIndex = edges.findIndex(edge => pointsEqual(currentEdge[1], edge[0]));
      if (nextEdgeIndex === -1) break;

      const nextEdge = edges[nextEdgeIndex];
      currentLoop.push(nextEdge);
      currentEdge = nextEdge;
      edges.splice(nextEdgeIndex, 1);
    }

    loops.push(currentLoop);
  }

  return loops;
}

// Render the polygons
function renderPolygons(ctx, sortedEdges, outlineWidth, strokeStyle) {
  sortedEdges.forEach(polygonEdges => {
    const simplifiedEdges = simplifyCollinearEdges(polygonEdges);
    renderPolygon(ctx, simplifiedEdges, outlineWidth, strokeStyle);
  });
}

// Simplify collinear edges
function simplifyCollinearEdges(edges) {
  if (edges.length <= 1) return edges;

  const simplifiedEdges = [];
  let currentStart = edges[0][0];
  let currentEnd = edges[0][1];

  for (let i = 1; i < edges.length; i++) {
    const [nextStart, nextEnd] = edges[i];

    if (isCollinear(currentStart, currentEnd, nextStart, nextEnd)) {
      currentEnd = nextEnd;
    } else {
      simplifiedEdges.push([currentStart, currentEnd]);
      currentStart = nextStart;
      currentEnd = nextEnd;
    }
  }

  simplifiedEdges.push([currentStart, currentEnd]);
  return simplifiedEdges;
}

// Render a single polygon
function renderPolygon(ctx, edges, outlineWidth, strokeStyle) {
  if (edges.length === 0) return;

  ctx.lineCap = 'round';
  ctx.strokeStyle = strokeStyle;
  ctx.lineWidth = outlineWidth;
  ctx.beginPath();
  ctx.moveTo(edges[0][0][0], edges[0][0][1]);

  for (let i = 0; i < edges.length; i++) {
    const [, [x, y]] = edges[i];
    ctx.lineTo(x, y);
  }

  ctx.stroke();
}

// Draw the grid lines and outer border
function drawGrid(ctx, { gridWidth, gridHeight, rows, cols, squareSize, strokeStyle, borderWidth, xOffset, yOffset }) {
  ctx.strokeStyle = strokeStyle;
  ctx.lineWidth = borderWidth;

  for (let row = 1; row < rows; row++) {
    ctx.beginPath();
    ctx.moveTo(xOffset, row * squareSize + yOffset);
    ctx.lineTo(gridWidth + xOffset, row * squareSize + yOffset);
    ctx.stroke();
  }

  for (let col = 1; col < cols; col++) {
    ctx.beginPath();
    ctx.moveTo(col * squareSize + xOffset, yOffset);
    ctx.lineTo(col * squareSize + xOffset, gridHeight + yOffset);
    ctx.stroke();
  }

  ctx.strokeRect(xOffset, yOffset, gridWidth, gridHeight);
}

// Draw the filled squares
function drawSquares(ctx, { matrix, rows, cols, squareSize, xOffset, yOffset }) {
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (matrix[row][col] === 1) {
        ctx.fillStyle = 'hsla(120, 100%, 80%, 0.8)';
        ctx.fillRect(col * squareSize + xOffset, row * squareSize + yOffset, squareSize, squareSize);
      }
    }
  }
}

// Utility functions

function pointsEqual(p1, p2) {
  return p1[0] === p2[0] && p1[1] === p2[1];
}

function isCollinear(start1, end1, start2, end2) {
  return (
    (start1[0] === end1[0] && start1[0] === start2[0] && start1[0] === end2[0]) ||  
    (start1[1] === end1[1] && start1[1] === start2[1] && start1[1] === end2[1])  
  );
}
    #drawing {
  border: thin dashed red;
}
    <canvas id="drawing"></canvas>