Bipartite.cs

using UnityEngine;
using System.Collections.Generic;
using System.Linq;

// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]
public class Bipartite {
	private const int MAX = 100001;
	private const int NIL = 0;
	private const int INF = 100000;
	
	private List<List<int>> G;//new List<List<int>>(Max);
	private int n;
	private int m;
	public int[] match;
	private int[] dist;

	public Bipartite(List<List<int>> adj, int hcount, int vcount)
	{
		G=adj;
		n=hcount;
		m=vcount;
		match = new int[n+m+1];
		dist = new int[n+m+1];
	}

	private bool bfs() {
	    int i, u, v, len;
	    Queue< int > Q = new Queue<int>();
	    for(i=1; i<=n; i++) {
	        if(match[i]==NIL) {
	            dist[i] = 0;
	            Q.Enqueue(i);
	        }
	        else dist[i] = INF;
	    }
	    dist[NIL] = INF;
	    while(Q.Count>0) {
	        u = Q.Dequeue();
	        if(u!=NIL) {
	            len = G[u].Count;
	            for(i=0; i<len; i++) {
	                v = G[u][i];
	                if(dist[match[v]]==INF) {
	                    dist[match[v]] = dist[u] + 1;
	                    Q.Enqueue(match[v]);
	                }
	            }
	        }
	    }
	    return (dist[NIL]!=INF);
	}
	
	private bool dfs(int u) {
	    int i, v, len;
	    if(u!=NIL) {
	        len = G[u].Count;
	        for(i=0; i<len; i++) {
	            v = G[u][i];
	            if(dist[match[v]]==dist[u]+1) {
	                if(dfs(match[v])) {
	                    match[v] = u;
	                    match[u] = v;
	                    return true;
	                }
	            }
	        }
	        dist[u] = INF;
	        return false;
	    }
	    return true;
	}
	
	public int hopcroft_karp() {
	    int matching = 0, i;
	    // match[] is assumed NIL for all vertex in G
	    while(bfs())
	        for(i=1; i<=n; i++)
	            if(match[i]==NIL && dfs(i))
	                matching++;
	    return matching;
	}
	
	public List<int> MinimumCover;
	public List<int> MaximumIndependentSet;
	
	public void CalcCover()
	{
		List<int> V = new List<int>();
		for(int i=0;i<=m+n;i++)
		{
			V.Add(i);
		}
		List<int> Match = new List<int>(match);
		var L = V.Where (i => i>=1 && i<=n).ToList();
		var R = V.Where (i => i>n).ToList();
		var E_m = Match.Where(i => i>=1);
		var E_0 = V.Where ( i => E_m.Contains(i)==false && i>=1 );
				
		List<int> T = E_0.Where( i => i<=n).ToList();
		
		bool modified=true;
		while(modified)
		{
			modified=false;
			
			//Calculate T
			foreach (int i in T)
			{
				if (i<=n)
				{
					//go left to right along edges of E_0 (aka match==0)
					List<int> opposite = G[i];
					List<int> allowedopposite = opposite.Where( j => match[i]!=j).ToList();
					if (allowedopposite.Count>0)
					{
						foreach(int k in allowedopposite)
						{
							modified = modified || T.AddUnique(k);
						}
						if (modified)
						{
							break;
						}
					}
				}
				else
				{
					var opposite = G[i];
					var allowedopposite = opposite.Where( j => match[j]>=1);
					if (allowedopposite.Any())
					{
						foreach(int k in allowedopposite)
						{
							modified = modified || T.AddUnique(k);
						}
						if (modified)
						{
							break;
						}
					}
				}
			}
			
			//mvc = (L\T) U  (R intersection T)
			var MVC = 
					L.Where( i => T.Contains(i)==false)
				.Union(
					R.Where ( i => T.Contains(i)==true)
				);
			
			MinimumCover = MVC.ToList();
			MaximumIndependentSet = V.Where( i => MinimumCover.Contains(i)==false && i>=1).ToList();
			
		}
	}
}

PartitionAlgorithm.cs

using UnityEngine;
using System.Collections.Generic;
using System.Linq;

public class PartitionAlgorithm : MonoBehaviour {
	
	private static void PrintGrid(int[,] grid)
	{
		if (verbose==false)
			return;
		string s="";
		for (int j=1;j<grid.GetLength(1)-1;j++)
		{
			for (int i=1;i<grid.GetLength(0)-1;i++)
			{
				s+=grid[i,j];
			}
			s+="\n";
		}
		Debug.Log(s);
	}
	
	private static void SimplifyGrid(int[,] grid)
	{
		List<int> found = new List<int>();
		for (int i=1;i<grid.GetLength(0)-1;i++)
		{
			for (int j=1;j<grid.GetLength(1)-1;j++)
			{
				int n = grid[i,j];
				if (n>0 && !found.Contains(n))
					found.Add(n);
			}
		}
				
		for (int i=1;i<grid.GetLength(0)-1;i++)
		{
			for (int j=1;j<grid.GetLength(1)-1;j++)
			{
				if (grid[i,j]>0)
				{
					grid[i,j]=found.IndexOf(grid[i,j])+1;
				}
			}
		}
	}
	
	private static int GridMax(int[,] grid)
	{
		int max=0;
		for (int i=1;i<grid.GetLength(0)-1;i++)
		{
			for (int j=1;j<grid.GetLength(1)-1;j++)
			{
				if (grid[i,j]>max)
				{
					max=grid[i,j];
				}
			}
		}
		return max;
	}
	
	
	public struct HEdge 
	{
		public HEdge(int _x, int _y, int _w)
		{
			x=_x;
			y=_y;
			w=_w;
		}
		
		override public string ToString()
		{
			return "("+x+","+y+","+w+")";
		}
		public readonly int x;
		public readonly int y;
		public readonly int w;
		public int x2 {
			get {return x+w;}
		}
	}
	
	public struct VEdge
	{
		public VEdge(int _x, int _y, int _h)
		{
			x=_x;
			y=_y;
			h=_h;
		}
		
		override public string ToString()
		{
			return "("+x+","+y+","+h+")";
		}
		public readonly int x;
		public readonly int y;
		public readonly int h;
		public int y2 {
			get {return y+h;}
		}
	}
	
	private static bool ContainsCorner(HEdge edge_h, Pair<int> corner)
	{
		if (edge_h.y!=corner.y)
			return false;
		else if (edge_h.x==corner.x )
			return true;
		else if (edge_h.x2==corner.x)
			return true;
		else
			return false;
	}
	
	private static bool ContainsCorner(VEdge edge_v, Pair<int> corner)
	{
		if (edge_v.x!=corner.x)
			return false;
		else if (edge_v.y==corner.y )
			return true;
		else if (edge_v.y2==corner.y)
			return true;
		else
			return false;
	}
	
	private static bool Intersects(HEdge edge_h, VEdge edge_v)
	{
		if (edge_v.x<edge_h.x || edge_v.x>edge_h.x2)
			return false;
		if (edge_h.y<edge_v.y || edge_h.y>edge_v.y2)
			return false;
		
		return true;
	}
	
	//needs it to be somewhere other than the end-point of the segments to return true.
	private static bool IntersectsStrict(HEdge edge_h, VEdge edge_v)
	{
		if (edge_v.x<=edge_h.x || edge_v.x>=edge_h.x2)
			return false;
		if (edge_h.y<=edge_v.y || edge_h.y>=edge_v.y2)
			return false;
		
		return true;
	}
	
	private static List<VEdge> GenerateVEdges(int[,] grid)
	{
		List<VEdge> result = new List<VEdge>();
		int height=0;
		for (int i=1;i<grid.GetLength(0);i++)
		{			
			for (int j=0;j<grid.GetLength(1)-1;j++)
			{
				if (grid[i-1,j] != grid[i,j])
				{
					height++;
					
					if ((grid[i-1,j+1]==0) == (grid[i,j+1]==0))
					{
						VEdge ledge = new VEdge(i,j-height+1,height);
						result.Add(ledge);
						height=0;
					}
				}
			}
		}
		return result;
	}
	
	private static List<HEdge> GenerateHEdges(int[,] grid)
	{
		List<HEdge> result = new List<HEdge>();
		int height=0;
		for (int i=1;i<grid.GetLength(1);i++)
		{			
			for (int j=0;j<grid.GetLength(0)-1;j++)
			{
				if (grid[j,i-1] != grid[j,i])
				{
					height++;
					
					if ((grid[j+1,i-1]==0) == (grid[j+1,i]==0))
					{
						HEdge ledge = new HEdge(j-height+1,i,height);
						result.Add(ledge);
						height=0;
					}
				}
			}
		}
		return result;
	}		
	
	public class GridRect
	{
		override public string ToString()
		{
			return "("+x+","+y+","+w+","+h+")";
		}
		public int x;
		public int y;
		public int w;
		public int h;
		
		public int b {
			get {return y+h;}
		}
		public int r {
			get {return x+w;}
		}
		
		public int area()
		{
			return w*h;
		}
		public GridRect(int _x, int _y, int _w, int _h)
		{
			x=_x;
			y=_y;
			w=_w;
			h=_h;
		}
		
		public bool Contains(int px, int py)
		{
			return px<x || px>=r || py<y || py>=b;			
		}
		
		public bool bottombounds(HEdge hEdge)
		{
			if (hEdge.y !=b)
				return false;
			if (hEdge.x2<=x || hEdge.x>=r)
				return false;
			return true;
		}
		
		public bool rightbounds(VEdge vEdge)
		{
			if (vEdge.x !=r)
				return false;
			if (vEdge.y2<=y || vEdge.y>=b)
				return false;
			return true;
		}
		
		public List<Pair<int>> Points()
		{
			List<Pair<int>> result = new List<Pair<int>>();
			for (int i=0;i<w;i++)
			{
				for (int j=0;j<h;j++)
				{
					result.Add(new Pair<int>(x+i,y+j));
				}
			}
			return result;
		}
	}
	
	
	private static bool Find(int tile, int[,] grid, out Pair<int> result)
	{
		for (int i=1;i<grid.GetLength(0)-1;i++)
		{
			for (int j=1;j<grid.GetLength(1)-1;j++)
			{
				if (grid[i,j]==tile)
				{
					result = new Pair<int>(i,j);
					return true;
				}
			}
		}
		result = new Pair<int>(0,0);
		return false;
	}
	
	private static void FloodFill(int[,] grid, Pair<int> target, int col)
	{
		int toreplace = grid[target.x,target.y];		
		grid[target.x,target.y]=col;
		
		bool replacedany=true;
		while(replacedany)
		{
			replacedany=false;
			for (int i=1;i<grid.GetLength(0)-1;i++)
			{
				for (int j=1;j<grid.GetLength(1)-1;j++)
				{
					if (grid[i,j]==toreplace)
					{
						if (grid[i-1,j]==col ||
							grid[i+1,j]==col ||
							grid[i,j-1]==col ||
							grid[i,j+1]==col)
						{
							replacedany=true;
							grid[i,j]=col;
						}
					}
				}
			}
		}
	}	
	
	private static bool verbose=false;
	public static List<GridRect> ProcessGrid(int[,] inputgrid)
	{
		if (verbose)
		{
			Debug.Log("NEW GRID NEW GRID\nNEW GRID NEW GRID");
		}
		
		int[,] grid = new int[inputgrid.GetLength(0)+2,inputgrid.GetLength(1)+2];
		for (int i=0;i<inputgrid.GetLength(0);i++)
		{
			for (int j=0;j<inputgrid.GetLength(1);j++)
			{
				grid[i+1,j+1]=inputgrid[i,j];
			}
		}
		
		
		
		List<Pair<int>> allcorners = new List<Pair<int>>();
		List<Pair<int>> convexcorners = new List<Pair<int>>();
		int origarea=0;
		
		for (int i=1;i<grid.GetLength(0);i++)
		{
			for (int j=1;j<grid.GetLength(1);j++)
			{
				origarea+=grid[i,j];
				int s = grid[i-1,j]+grid[i,j]+grid[i,j-1]+grid[i-1,j-1];
				
			
				if (s==1||s==3)
				{
					Pair<int> corner = new Pair<int>(i,j);
					allcorners.Add(corner);		
					if (s==3)
					{
						convexcorners.Add(corner);
					}
				}
			}
		}
		
		PrintGrid(grid);
		
		if (verbose) {Debug.Log("corner count " + allcorners.Count +"\nconvex corner count = " + convexcorners.Count);}		
		
		/// 1 construct HVertices (order by x, then y)
		/// 
		/// 2 find pairs of consecute edges (x1<x2<x3<x4, const y)
		/// 	check if the edge is internal
		/// 		1 - if x2,x3 concave
		/// 		2 - if no vertical line intersects x2x3
		/// 	if it fits, add to HorizCol
		/// 3 - generate VertCol similarly
		/// 4 - find max non-intersecting set of HorizCol U VertCol
		/// 5 - fill out other lines
		/// 6 - construct rects
		
		/// 1 construct HVertices (order by x, then y)
		List<HEdge> hedges = GenerateHEdges(grid);		
		List<VEdge> vedges = GenerateVEdges(grid);
				
		
		/// 2 find pairs of consecute edges (x1<x2<x3<x4, const y)
		/// 	check if the edge is internal
		/// 		1 - if x2,x3 concave
		/// 		2 - if no vertical line intersects x2x3
		/// 	if it fits, add to HorizCol
		/// 3 - generate VertCol similarly
		List<HEdge> horizCol = HorizCol(grid,hedges,vedges,convexcorners,allcorners);
		List<VEdge> vertCol = VertCol(grid,hedges,vedges,convexcorners,allcorners);
		
		if (verbose)
		{
			Debug.Log (
				"hedge count = " + hedges.Count+
				"\nvedge count = " + vedges.Count + 
				"\nhorizCol count = " + horizCol.Count + 
				"\nvertCol count = " + vertCol.Count);
		}
		
		/// 4 - find max non-intersecting set of HorizCol U VertCol
		List<List<int>> graph = new List<List<int>>();
		int hcount = horizCol.Count;
		int vcount = vertCol.Count;
		
		for (int i=0;i<hcount+vcount+1;i++)
		{
			graph.Add(new List<int>());			
		}
		
		for (int i=0;i<hcount;i++)
		{
			for (int j=0;j<vcount;j++)
			{			
				HEdge edgeh = horizCol[i];
				VEdge edgev = vertCol[j];
				if (Intersects(edgeh,edgev))
				{					
					graph[1+i].Add(1+hcount+j);
					graph[1+hcount+j].Add (1+i);
				}
			}
		}
						
		
		
		Bipartite bp = new Bipartite(graph,hcount,vcount);
		
		int matchingnum = bp.hopcroft_karp();
		bp.CalcCover();
		if (verbose)
		{
			string graphdat = "graph adj \n";
			for (int i=0;i<graph.Count;i++)
			{
				graphdat+=i+": ";
				foreach(int j in graph[i])
				{
					graphdat+=j+",";
				}
				graphdat+="\n";
			}
			Debug.Log (graphdat);
			string debug = "matching num" + matchingnum+"\n";
			foreach(int a in bp.match)
			{
				debug+=a+",";
			}
			Debug.Log (debug);
			
			
			string s = "Minimum Cover: ";
			foreach(int i in bp.MinimumCover)
			{
				s+=i+",";
			}
			s+= "Maximum Independent set: "; 
			foreach(int i in bp.MaximumIndependentSet)
			{
				s+=i+",";
			}
			Debug.Log (s);
		}
		
		List<HEdge> chosenInternalHEdges  = new List<HEdge>();
		List<VEdge> chosenInternalVEdges = new List<VEdge>();
		foreach(int i in bp.MaximumIndependentSet)
		{
			if (i<=hcount)
			{
				chosenInternalHEdges.Add(horizCol[i-1]) ;
			}
			else
			{
				chosenInternalVEdges.Add(vertCol[i-hcount-1]) ;	
			}
		}
		
		/// 5 - fill out other lines		
		List<HEdge> extraedges = new List<HEdge>();
		foreach(Pair<int> c in convexcorners)
		{
			if (chosenInternalHEdges.Any( hedge => ContainsCorner(hedge,c)) || chosenInternalVEdges.Any(vedge => ContainsCorner(vedge,c)))
			{
				continue;
			}
			
			extraedges.Add(ExtendHLineFrom(grid,c))	;					
		}
		
		
		//Debug.Log ("extra edges " + extraedges.Count);
		/// 6 - construct rects
		
		
		List<HEdge> hParts = hedges.Union(chosenInternalHEdges).Union(extraedges).ToList();
		List<VEdge> vParts = vedges.Union(chosenInternalVEdges).ToList();
		List<GridRect> result = new List<GridRect>();
		while (true)
		{
			Pair<int> tl = GetPoint(grid);
			if (tl.x<0)
				break;
			GridRect gr = new GridRect(tl.x,tl.y,1,1);
			//expand right
			while ( !hParts.Any( hpart => gr.bottombounds(hpart) ))
			{
				gr.h++;
			}
			while ( !vParts.Any( vpart => gr.rightbounds(vpart) ) )
			{
				gr.w++;
			}
			
			if(gr.Points().Count!=gr.area())
			{
				Debug.LogError ("eep");
			}
			foreach(Pair<int> point in gr.Points())
			{
				grid[point.x,point.y]=0;
			}
			
			gr.x--;
			gr.y--;
			result.Add(gr);
		}
		
		int areacount=result.Sum( r => r.area());
		if (areacount!=origarea)
		{
			Debug.LogError("area mismatch "+origarea +"!="+areacount);
		}
		if (verbose)
		{
			Debug.Log ("resultant rectangles = " + result.Count);
		}
		return result;
	}	
	
	private static Pair<int> GetPoint(int[,] grid)
	{
		for (int i=0;i<grid.GetLength(0);i++)
		{
			for (int j=0;j<grid.GetLength(1);j++)
			{
				if (grid[i,j]>0)
				{
					return new Pair<int>(i,j);
				}
			}
		}
		return new Pair<int>(-1,-1);
	}
	private static HEdge ExtendHLineFrom(int[,] grid, Pair<int> c)
	{
		int dir;
		if (grid[c.x-1,c.y-1]==1 && grid[c.x-1,c.y]==1)
		{
			dir=-1;
		}
		else
		{
			dir=1;
		}
		int x2 = c.x;
		while(true)
		{
			x2+=dir;
			if (grid[x2,c.y-1]==0 || grid[x2,c.y]==0)
			{
				int l = System.Math.Min (x2,c.x);
				int w = System.Math.Abs (x2-c.x);
				return new HEdge(l,c.y,w);
			}
			if (x2>1000)
			{
				Debug.LogError ("eep overflow");
				break;
			}
		}
		Debug.LogError("EEP invalid hedge");
		return new HEdge(0,0,0);
	}
	
	private static List<HEdge> HorizCol(int[,] grid,List<HEdge> hedges,List<VEdge> vedges,List<Pair<int>> convexcorners, List<Pair<int>> allcorners)
	{
		List<HEdge> result = new List<HEdge>();
		System.Comparison<Pair<int>> cornersort = (a,b) =>
			{
				if (a.y!=b.y)
					return a.y.CompareTo(b.y);
				else
					return a.x.CompareTo(b.x);
			};
		
		allcorners.Sort( cornersort );
		
		for (int i=0;i<allcorners.Count-4;i+=2)
		{
			var a = allcorners[i+0];
			var b = allcorners[i+1];
			var c = allcorners[i+2];
			var d = allcorners[i+3];
			if ( (a.y != b.y) || (a.y != c.y) || (a.y != d.y) )
			{
				continue;
			}
			if (!convexcorners.Contains(b)  || !convexcorners.Contains(c))
			{
				continue;
			}
			
			HEdge hedge = new HEdge(b.x,b.y,c.x-b.x);
			if (vedges.Any ( vedge => IntersectsStrict(hedge,vedge) ) )
			{
				continue;
			}
			
			result.Add(hedge);
		}
		
		return result;
	}
	
	private static List<VEdge> VertCol(int[,] grid,List<HEdge> hedges,List<VEdge> vedges,List<Pair<int>> convexcorners, List<Pair<int>> allcorners)
	{
		List<VEdge> result = new List<VEdge>();
		System.Comparison<Pair<int>> cornersort = (a,b) =>
			{
				if (a.x!=b.x)
					return a.x.CompareTo(b.x);
				else
					return a.y.CompareTo(b.y);
			};
		
		allcorners.Sort( cornersort );
		
		for (int i=0;i<allcorners.Count-4;i+=2)
		{
			var a = allcorners[i+0];
			var b = allcorners[i+1];
			var c = allcorners[i+2];
			var d = allcorners[i+3];
			if ( (a.x != b.x) || (a.x != c.x) || (a.x != d.x) )
			{
				continue;
			}
			if (!convexcorners.Contains(b)  || !convexcorners.Contains(c))
			{
				continue;
			}
			
			VEdge vedge = new VEdge(b.x,b.y,c.y-b.y);
			if (hedges.Any ( hedge => IntersectsStrict(hedge,vedge) ) )
			{
				continue;
			}
			
			result.Add(vedge);
		}
		
		return result;
	}
	
	private static void PrintTable(List<List<int>> correspondencetable)
	{
		string sdat="correspondencetable:\n";
		foreach(var r in correspondencetable)
		{
			foreach(var i in r)
			{
				sdat+=i+",";
			}
			sdat+="\n";
		}
		if (verbose) { 
			Debug.Log(sdat);
		}
	}	
	
	
	private static List<List<int>> CopyTable(List<List<int>> table)
	{
		List<List<int>> newtable = new List<List<int>>();
		foreach(List<int> row in table)
		{
			List<int> newrow = new List<int>(row);
			newtable.Add(newrow);
		}
		return newtable;
	}		
	
	//removes colums where it's 1 also
	//pass the index, not the name of the row
	private static int RemoveRow(List<List<int>> table, int r)
	{
		var row = table[r];
		
		for (int i=1;i<row.Count;i++)
		{
			if (row[i]==1)
			{
				RemoveCol(table,i);
				i--;
			}
		}
		table.RemoveAt(r);

		return row[0];
	}
	
	private static void RemoveCol(List<List<int>> table, int c)
	{
		for (int i=0;i<table.Count;i++)
		{
			table[i].RemoveAt(c);
		}
	}
	
	// Use this for initialization
	void Start () {

		int[,] grid = new int[,]{
			{1,0,1},
			{1,1,1},
			{1,0,1},
			{1,1,1},
			{0,1,1},
			{1,1,0},
			
		};
	/*
		
		int[,] grid = new int[,]{
			{0,0,0,0,0,0},
			{0,0,1,0,0,0},
			{0,1,1,1,0,0},
			{0,0,1,1,1,0},
			{0,0,0,1,0,0},
			{0,0,0,0,0,0},
			
		};
	*/
		ProcessGrid(grid);
	}
	
	// Update is called once per frame
	void Update () {
	
	}
}