Find hamiltonian and build android.graphics.Region from this

HamiltonianRegion.java

import android.graphics.Path;
import android.graphics.Rect;
import android.graphics.Region;
import android.graphics.RegionIterator;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;


/**
 * Created by dp on 14/05/14.
 */
public class HamiltonianRegion implements Comparator<HamiltonianRegion.Edge> {

  Region region;

  public HamiltonianRegion() {
    this.region = new Region();
  }

  public HamiltonianRegion(Region region) {
    this.region = region;
  }

  @Override
  public int compare(Edge lhs, Edge rhs) {
    return (lhs.x == rhs.x) ? lhs.top() - rhs.top() : lhs.x - rhs.x;
  }

  public static class Edge {

    public static final int Y0Link = 0x01;
    public static final int Y1Link = 0x02;
    public static final int CompleteLink = (Y0Link | Y1Link);

    private int x;
    private int y0, y1;

    private int flags;
    private Edge next = null;

    public void set(int x, int y0, int y1) {
      assert (y0 != y1);

      this.x = x;
      this.y0 = y0;
      this.y1 = y1;
      this.flags = 0;
    }

    public int top() {
      return Math.min(this.y0, this.y1);
    }
  }

  public void add(Rect r) {
    region.op(r, Region.Op.UNION);
  }

  public Path getBoundaryPath() {
    RegionIterator iter = new RegionIterator(region);
    Rect r = new Rect();
    List<Edge> edges = new ArrayList<Edge>();
    while (iter.next(r)) {
      Edge edge0 = new Edge();
      edge0.set(r.left, r.bottom, r.top);
      edges.add(edge0);

      Edge edge1 = new Edge();
      edge1.set(r.right, r.top, r.bottom);
      edges.add(edge1);
    }

    Collections.sort(edges, this);

    for (int i = 0; i < edges.size(); ++i) {
      findLink(i, edges);
    }

    Path path = new Path();
    int count = edges.size();
    Iterator<Edge> it = edges.iterator();
    do {
      count -= extractPath(it, path);
    } while (count > 0);

    return path;
  }

  private void findLink(int start, List<Edge> edges) {
    Edge base = edges.get(start);
    if (base.flags == Edge.CompleteLink) {
      assert (base.next != null);
      return;
    }

    int y0 = base.y0;
    int y1 = base.y1;

    if ((base.flags & Edge.Y0Link) == 0) {
      for (int j = start + 1; j < edges.size(); ++j) {
        Edge e = edges.get(j);
        if ((e.flags & Edge.Y1Link) == 0 && y0 == e.y1) {
          assert (e.next == null);

          e.next = base;
          e.flags |= Edge.Y1Link;
          break;
        }
      }
    }

    if ((base.flags & Edge.Y1Link) == 0) {
      for (int j = start + 1; j < edges.size(); ++j) {
        Edge e = edges.get(j);
        if ((e.flags & Edge.Y0Link) == 0 && y1 == e.y0) {
          assert (base.next == null);
          base.next = e;
          e.flags |= Edge.Y0Link;
          break;
        }
      }
    }

    base.flags = Edge.CompleteLink;
  }

  private int extractPath(Iterator<Edge> iterator, Path path) {
    Edge edge = null;
    while (iterator.hasNext()) {
      edge = iterator.next();
      if (0 != edge.flags) {
        break;
      }
    }

    if (edge == null) {
      return 0;
    }

    Edge base = edge;
    Edge prev = edge;
    edge = edge.next;
    assert (edge != base);

    int count = 1;
    path.moveTo(prev.x, prev.y0);
    prev.flags = 0;
    do {
      if (prev.x != edge.x || prev.y1 != edge.y0) {
        path.lineTo(prev.x, prev.y1);
        path.lineTo(edge.x, edge.y0);
      }

      prev = edge;
      edge = edge.next;
      count += 1;
      prev.flags = 0;
    } while (edge != base);
    path.lineTo(prev.x, prev.y1);
    path.close();

    return count;
  }
}