Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

86
LINES

< > BotCompany Repo | #1033829 // ScanlineBitMatrix - Scanline (runs) based implementation of BitMatrix. immutable

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (6001L/33K).

persistable sclass ScanlineBitMatrix extends AbstractMatrix<Bool> is BitMatrix {
  int bx1 = Int.MAX_VALUE, by1, bx2, by2; // bounding box of positive bits
  int pixels; // number of set bits
  
  // format for each line: start x, end x (excl.), start x, end x, ...
  int[] scanlineData;
  
  // pointer into scanlineData for each line
  int[] scanlineStarts;
  
  *(BitMatrix m) {
    super(m.getWidth(), m.getHeight());
    
    // find upper and lower bounding line
    while (by1 < h && bitMatrixRowEmpty(m, by1)) by1++;
    
    by2 = h;
    while (by2 > by1 && bitMatrixRowEmpty(m, by2-1)) by2--;
    
    int ptr = 0, pixels = 0;
    scanlineStarts = new int[by2-by1];
    new IntBuffer scanlineData;
    lineLoop: for (int y = by1; y < by2; y++) {
      scanlineStarts[y-by1] = l(scanlineData);
      
      for (int x = 0; x < w; ) {
        while (!m.get(x, y))
          if (++x >= w)
            continue lineLoop;
        
        int x2 = x+1;
        while (x2 < w && m.get(x2, y)) ++x2;
        
        scanlineData.add(x);
        scanlineData.add(x2);
        pixels += x2-x;
        if (x < bx1) bx1 = x;
        if (x2 > bx2) bx2 = x2;
        x = x2;
      }
    }
    this.scanlineData = scanlineData.toArray();
    this.pixels = pixels;
  }
  
  public Bool get(int x, int y) {
    if (x < bx1 || y < by1 || x >= bx2 || y >= by2) false;
    int ptr = scanlineStarts[y-by1];
    
    int end = y == by2-1 ? scanlineData.length : scanlineStarts[y-by1+1];

    // linear search for now
    while (ptr < end) {
      int x1 = scanlineData[ptr++];
      if (x < x1) false;
      int x2 = scanlineData[ptr++];
      if (x < x2) true;
    }
    
    false;
  }
  
  public void set(int x, int y, Bool a) { unimplemented(); }
  
  Rect boundingBoxOfTrueBits() { ret bx1 >= bx2 ? null : rect(bx1, by1, bx2, by2); }
  
  int nRuns() { ret scanlineData.length/2; }
  
  ItIt<Rect> runs() {
    ret new ItIt<Rect> {
      int y = 0, ptr = 0;
      
      public bool hasNext() { ret ptr < l(scanlineData); }
      public Rect next() {
        while (y < scanlineStarts.length-1
          && ptr >= scanlineStarts[y+1])
            ++y;
        int x1 = scanlineData[ptr++];
        int x2 = scanlineData[ptr++];
        ret rect(x1, by1+y, x2-x1, 1);
      }
    };
  }
  
  int pixelCount() { ret pixels; }
}

Author comment

Began life as a copy of #1033585

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj

No comments. add comment

Snippet ID: #1033829
Snippet name: ScanlineBitMatrix - Scanline (runs) based implementation of BitMatrix. immutable
Eternal ID of this version: #1033829/21
Text MD5: 9e7d5259d75e896eaae6d2cae473a473
Transpilation MD5: 4ff677ac0fbf96dea9f87b826921af27
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-01-13 16:11:11
Source code size: 2406 bytes / 86 lines
Pitched / IR pitched: No / No
Views / Downloads: 107 / 245
Version history: 20 change(s)
Referenced in: [show references]