Sort Multiple Barcodes in Reading Order

In places like laboratories, we often need to scan a tray of multiple tubes with barcodes on the top (like the following image).

Batch QR Codes

The tubes may be used for Covid-19 PCR test. They need to be retrieved in reading order (from left to right and line by line from the top to bottom). It would be convenient if we can scan all the barcodes, sort the results and output the results to CSV files for further use.

In this article, we are going to create a web app which can read multiple or dense barcodes and write a sorting algorithm in JavaScript to sort the results in reading order.

Create a Web App to Read Multiple Barcodes

  1. Create a new vanilla TypeScript project using Vite.

    npm create vite@latest example -- --template vanilla-ts

  2. Install Dynamsoft Barcode Reader as a dependency.

    npm install dynamsoft-javascript-barcode

  3. In the index.html, add an input element for selecting a file, a button to read barcodes and an SVG element to show the results.

    <!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <link rel="icon" type="image/svg+xml" href="/vite.svg" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Vite + TS</title>
  </head>
  <body>
    <div id="app">
      <div class="barcode-reader">
        <div>
          Load local image:
          <input type="file" id="barcodeFile" accept=".jpg,.jpeg,.png,.bmp" />
        </div>
        <div>
          <button id="decodeButton">Decode</button>
        </div>
        <div id="status"></div>
        <svg id="resultSVG" version="1.1" xmlns="http://www.w3.org/2000/svg"></svg>
      </div>
    </div>
    <script type="module" src="/src/main.ts"></script>
  </body>
</html>

  4. Load the selected image file and display it in the SVG element.

    let img;
window.onload = function(){
  let barcodeFile = document.getElementById('barcodeFile') as HTMLInputElement;
  barcodeFile.addEventListener("change",function(){
    loadImageFromFile();
  })
}

function loadImageFromFile() { 
  console.log("loadImageFromFile");
  let barcodeFile = document.getElementById('barcodeFile') as HTMLInputElement;
  let files = barcodeFile.files as FileList;
  if (files.length == 0) {
    return;
  }
  let file = files[0];
  let fileReader = new FileReader();
  fileReader.onload = function(e:any){
    loadImage(e.target.result);
  };
  fileReader.onerror = function () {
    console.warn('oops, something went wrong.');
  };
  fileReader.readAsDataURL(file);
}

function loadImage(imgsrc:string){
  if (imgsrc) {
    img = new Image();
    img.src = imgsrc;
    img.onload = function(){
      let svgElement = document.getElementById("resultSVG") as HTMLElement;
      svgElement.innerHTML = "";
      let svgImage = document.createElementNS("http://www.w3.org/2000/svg", "image");
      svgImage.setAttribute("href",imgsrc);
      svgElement.setAttribute("viewBox","0 0 "+img.width+" "+img.height);
      svgElement.appendChild(svgImage);
    }
  }
}

  5. Read barcodes from the selected image and overlay the results in the SVG element when the decode button is clicked. Initialize Dynamsoft Barcode Reader if it has not been initialized. You may need to apply for a license to use it.

    let reader:BarcodeReader;
let results:TextResult[];
window.onload = function(){
  let decodeButton = document.getElementById('decodeButton') as HTMLButtonElement;
  decodeButton.addEventListener("click",function(){
    decodeImg();
  })
}
   
async function decodeImg(){
  if (!img) {
    return;
  }
  let status = document.getElementById("status") as HTMLElement;
  if (!reader) {
    await initDBR();
  }
  status.innerText = "decoding...";
  results = await reader.decode(img);
  console.log(results);
  overlayResults(results);
  status.innerText = "";
}
   
async function initDBR(){
  let status = document.getElementById("status") as HTMLElement;
  status.innerText = "initializing...";
  BarcodeReader.engineResourcePath = "https://cdn.jsdelivr.net/npm/dynamsoft-javascript-barcode@9.6.10/dist/";
  BarcodeReader.license = "DLS2eyJoYW5kc2hha2VDb2RlIjoiMjAwMDAxLTE2NDk4Mjk3OTI2MzUiLCJvcmdhbml6YXRpb25JRCI6IjIwMDAwMSIsInNlc3Npb25QYXNzd29yZCI6IndTcGR6Vm05WDJrcEQ5YUoifQ=="; //one-day public trial
  reader = await BarcodeReader.createInstance();
  status.innerText = "";
}

    Functions for overlaying the results with polygons indicating the location and text indicating their index (code based on this article):

    function overlayResults(results:TextResult[]){
  let svgElement = document.getElementById("resultSVG") as HTMLElement;
  clearElements(svgElement,"a");
  for (let i = 0; i < results.length; i++) {
    const result = results[i];
    let a = document.createElementNS("http://www.w3.org/2000/svg","a");
    let polygon = document.createElementNS("http://www.w3.org/2000/svg","polygon");
    polygon.setAttribute("points",getPointsAttributeFromResult(result));
    polygon.setAttribute("class","barcode-polygon");
    let title = document.createElementNS("http://www.w3.org/2000/svg","title");
    title.textContent = result.barcodeFormatString + ": " + result.barcodeText;
    const rect = getRectangleFromResult(result);
    const center:Point =  {x:rect.x+rect.width/2,y:rect.y+rect.height/2};
    let text = document.createElementNS("http://www.w3.org/2000/svg","text");
    let fontSize = 25;
    text.setAttribute("x",(center.x - fontSize/2).toString());
    text.setAttribute("y",center.y.toString());
    text.classList.add("order");
    text.style.fontSize = fontSize.toString();
    text.textContent  = (i + 1).toString();
    polygon.append(title);
    a.append(polygon);
    a.append(text);
    svgElement.append(a);
  }
}
   
      
function getPointsAttributeFromResult(result:TextResult) {
  let value = "";
  value = value + result.localizationResult.x1 + " " + result.localizationResult.y1 + " ";
  value = value + result.localizationResult.x2 + " " + result.localizationResult.y2 + " ";
  value = value + result.localizationResult.x3 + " " + result.localizationResult.y3 + " ";
  value = value + result.localizationResult.x4 + " " + result.localizationResult.y4 + " ";
  return value.trim();
}

function clearElements(parent:HTMLElement,tagName:string){
  let elements=parent.getElementsByTagName(tagName);
  while (elements.length>0){
    let ele=elements[0];
    ele.remove();
  }
}

Run the demo and we can use it to read barcodes from images:

npm run dev

Multiple barcodes reader

Sort the Results in Reading Order

Next, we need to sort the results in reading order.

Write a Shape Sorter

We are going to write a universal sorter for shapes like polygons and rectangles first.

Here is a brief overview of the method we are going to adopt.

  1. Sort the rectangles (polygons will be converted to rectangles) based on their distance to the top-left corner.
  2. Cluster the rectangles into lines. If a rectangle overlaps with another rectangle vertically, they belong to the same line.
  3. Sort the lines from top to bottom.
  4. Sort the rectangles in one line from left to top.
  5. Get all the rectangles line by line.

Next, let’s implement it in TypeScript.

  1. Define interfaces in definition.ts.

    export interface Point {
  x:number;
  y:number;
}

export interface Mapping {
  originalIndex?:number;
}

export interface Polygon {
  points:Point[];
  mapping?:Mapping;
}

export interface Rectangle {
  x:number;
  y:number;
  width:number;
  height:number;
  mapping?:Mapping;
}

  2. Create a class named ShapeSorter with two methods: sortPolygons and sortRectangles and a horizontal property.

    The polygons are converted to rectangles for sorting.

    horizontal:boolean = true; sort based on rows or columns.
export default class ShapeSorter {
  sortPolygons(polygons:Polygon[]): Mapping[] {
    let rectangles:Rectangle[] = [];
    for (let index = 0; index < polygons.length; index++) {
      const polygon = polygons[index];
      rectangles.push(this.convertPolygonToRectangle(polygon));
    }
    return this.sortRectangles(rectangles);
  }
     
  sortRectangles(rectangles:Rectangle[]): Mapping[] {}
     
  convertPolygonToRectangle(polygon:Polygon):Rectangle{
    let minX:number;
    let minY:number;
    let maxX:number;
    let maxY:number;
    minX = polygon.points[0].x;
    minY = polygon.points[0].y;
    maxX = 0;
    maxY = 0;
    for (let index = 0; index < polygon.points.length; index++) {
      const point = polygon.points[index];
      minX = Math.min(minX,point.x);
      minY = Math.min(minY,point.y);
      maxX = Math.max(maxX,point.x);
      maxY = Math.max(maxY,point.y); 
    }
        
    const rect:Rectangle = {
      x:minX,
      y:minY,
      width: maxX-minX,
      height:maxY - minY,
      mapping:polygon.mapping
    }
    return rect;
  }
}

  3. Deep copy the rectangles array before sorting it since we are going to delete elements from it.

    rectangles = JSON.parse(JSON.stringify(rectangles));

  4. Sort the rectangles based on their distance to the top-left corner.

    rectangles.sort((a, b) => (a.x**2 + a.y**2) - (b.x**2 + b.y**2));

  5. Create a method to cluster the rectangles into lines.

    getLines(rectangles:Rectangle[]):Rectangle[][] {
  let lines:Rectangle[][] = [];
  while (rectangles.length > 0) {
    let rect = rectangles[0];
    let clustered = this.clusterRectanglesToOneLine(rectangles,rect);
    if (clustered) {
      lines.push(clustered);
    } else {
      lines.push([rect]); //single rectangle as a line
    }
    rectangles.shift(); //delete the base rect
  }
  if (this.horizontal) {
    lines.sort((a, b) => (a[0].y - b[0].y));
  }else{
    lines.sort((a, b) => (a[0].x - b[0].x));
  }
     
  return lines;
}
clusterRectanglesToOneLine(rectangles:Rectangle[],baseRect:Rectangle):Rectangle[]|undefined{
  let line:Rectangle[] = [];
  for (let index = rectangles.length - 1; index >= 1; index--) { // start from the second element
    const rect = rectangles[index];
    if (this.rectanglesInOneLine(baseRect,rect)) {
      line.push(rect);
      rectangles.splice(index, 1); //delete the rectangle clustered
    }
  }
  if (line.length>0) {
    line.push(baseRect);
    if (this.horizontal) {
      line.sort((a, b) => (a.x - b.x));
    }else{
      line.sort((a, b) => (a.y - b.y));
    }
    return line;
  }else{
    return undefined;
  }
}
   
rectanglesInOneLine(r1:Rectangle, r2:Rectangle) {
  if (this.horizontal) {
    let y = Math.max(r1.y, r2.y);
    let maxY1 = r1.y + r1.height;
    let maxY2 = r2.y + r2.height;
    let intersectH = Math.min(maxY1, maxY2) - y;
    if (intersectH>this.threshold) {
      return true;
    }else{
      return false;
    }
  }else{
    let x = Math.max(r1.x, r2.x);
    let maxX1 = r1.x + r1.width;
    let maxX2 = r2.x + r2.width;
    let intersectW = Math.min(maxX1, maxX2) - x;
    if (intersectW>0) {
      return true;
    }else{
      return false;
    }
  }
}

  6. Return the mappings for the users to sort their specific results.

    sortRectangles(rectangles:Rectangle[]): Mapping[] {
  rectangles = JSON.parse(JSON.stringify(rectangles));
  rectangles.sort((a, b) => (a.x**2 + a.y**2) - (b.x**2 + b.y**2))
  let lines = this.getLines(rectangles);
  return this.getMappingsFromRectangles(this.getRectangesFromLines(lines)); //return the mappings
}

getMappingsFromRectangles(rectangles:Rectangle[]): Mapping[] {
  let mappings:Mapping[] = [];
  for (let index = 0; index < rectangles.length; index++) {
    const rect = rectangles[index];
    if (rect.mapping) {
      mappings.push(rect.mapping);
    }
  }
  return mappings;
}

Use the Sorter to Sort Barcode Results

  1. Convert the barcode results to polygons. The original index is appended to each polygon.

    function polygonsFromTextResults(){
  let polygons = [];
  for (let index = 0; index < results.length; index++) {
    const result = results[index];
    polygons.push(getPolygonFromResult(result,index));
  }
  return polygons;
}

function getPolygonFromResult(result:TextResult,index:number):Polygon{
  const point1:Point = {x:result.localizationResult.x1,y:result.localizationResult.y1};
  const point2:Point = {x:result.localizationResult.x2,y:result.localizationResult.y2};
  const point3:Point = {x:result.localizationResult.x3,y:result.localizationResult.y3};
  const point4:Point = {x:result.localizationResult.x4,y:result.localizationResult.y4};
  const polygon:Polygon = {points:[point1,point2,point3,point4],mapping:{originalIndex:index}};
  return polygon;
}

  2. Add a sort button and sort the polygons using the sorter.

    HTML:

    <button id="sortButton">Sort</button>

    TypeScript:

    window.onload = function(){
  let sortButton = document.getElementById('sortButton') as HTMLButtonElement;
  sortButton.addEventListener("click",function(){
    sortTextResults();
  })
}
   
function sortTextResults(){
  let sorter = new ShapeSorter();
  let polygons = polygonsFromTextResults();
  let mappings = sorter.sortPolygons(polygons);
  reorderResultsAndUpdateOverlay(mappings);
}

  3. After getting the mappings, we can reorder the barcode results and update the overlay in the SVG element.

    function reorderResultsAndUpdateOverlay(mappings:Mapping[]){
  let newResults:TextResult[] = [];
  for (let index = 0; index < mappings.length; index++) {
    const mapping = mappings[index];
    const originalIndex = mapping.originalIndex;
    if (originalIndex != undefined) {
      newResults.push(results[originalIndex]);
    }
  }
  results = newResults;
  overlayResults(results);
}

All right, we can now sort the barcodes in reading order.

Multiple barcodes reader

Bundle the Sorting Functions into a Library

We can bundle the sorter as a JavaScript library with microbundle.

  1. Run npm init to create a new project.
  2. Install microbundle as the bundler: npm i -D microbundle.

  3. In the package.json, add the following:

    {
  "type": "module",
  "source": "src/shape-sorter.ts",
  "main": "./dist/shape-sorter.js",
  "exports": {
    "require": "./dist/shape-sorter.cjs",
    "default": "./dist/shape-sorter.modern.js"
  },
  "unpkg": "./dist/shape-sorter.umd.js",
  "amdName": "ShapeSorter",
  "scripts": {
    "build": "microbundle build",
    "dev": "microbundle watch"
  }
}
  4. Place definition.ts and shape-sorter.ts in the src folder.

  5. Run the following to build the library.

    npm run build

The library has been published to npmjs.

Drawbacks

This algorithm may not work well if the barcodes are lined in angles.

Source Code

You can find the source code of the project in the following repo: https://github.com/tony-xlh/shape-sorter