package ie.dcu.image;

import ie.dcu.matrix.*;

import java.awt.Polygon;
import java.util.*;

import org.eclipse.swt.graphics.Point;

/**
 * Trace contours of objects in images.
 * 
 * TODO: This class uses SWT points and AWT polygons...
 * 
 * @author Kevin McGuinness
 */
public class ContourTracer {

	private final IntMatrix labels;
	private final int nobjects;
	
	// Inversion table
	private static final int[] INVERT = { 4,5,6,7,0,1,2,3 };
	
	// Neighbor count
	private static final int NEIGHBORS = 8;

	public ContourTracer(ByteMatrix mask, byte foregroundValue) {
		ObjectLabeler mapper = new ObjectLabeler();
		mapper.setForegroundValue(foregroundValue);
		nobjects = mapper.label(mask);
		labels = mapper.getLabelMap();
	}
	
	public List<Polygon> trace() {
		List<Polygon> polygons = new ArrayList<Polygon>();
		if (labels != null) {
			doTrace(polygons);
		}
		return polygons;
	}

	private void doTrace(List<Polygon> polygons) {
		for (int i = 1; i <= nobjects; i++) {
			Polygon polygon = trace(i);
			if (polygon != null) {
				polygons.add(polygon);
			}
			//break;
		}
	}
	
	
	private Polygon trace(int object) {
		Point e1 = findFirstObjectPixel(object);
		
		if (e1 != null) {
			// First external border pixel is to the left
			e1 = new Point(e1.x-1, e1.y);
			
			List<Point> pts = new ArrayList<Point>();
			pts.add(e1);
			
			// Find the second pixel
			Candidate c = findFirstCandidate(e1, object);
			
			if (c != null) {
				
				Candidate next = new Candidate(c.pt, c.direction);
				
				do {
					next = findNext(next.pt, next.direction, object);
					pts.add(next.pt);
				} while (!next.pt.equals(e1));
			}
			
			return toPolygon(pts);
		}
		
		return null;
	}
	
	private final Candidate findNext(Point pc, int dpc, int object) {
		Candidate next = null;
		
		int dcp = INVERT[dpc];
		for (int r = 0; r < 7; r++) {
			int de = (dcp + r) % NEIGHBORS;
			int di = (dcp + r + 1) % NEIGHBORS;
			Point pe = neighbour(pc, de);
			Point pi = neighbour(pc, di);
			if (isBackground(pe, object) && isObject(pi, object)) {
				next = new Candidate(pe, de);
			}
		}
		
		return next;
	}
	
	private final Point findFirstObjectPixel(int object) {
		for (int y = 0; y < labels.rows; y++) {
			for (int x = 0; x < labels.cols; x++) {
				int label = labels.intAt(y, x); 
				if (label == object) {
					return new Point(x, y);
				}
			}
		}
		
		return null;
	}
	
	static final class Candidate {
		final Point pt;
		final int direction;
		
		Candidate(Point pt, int direction) {
			this.pt = new Point(pt.x, pt.y);
			this.direction = direction;
		}
	}
	
	private final Candidate findFirstCandidate(Point p0, int object) {

		// Find the next pixel
		for (int i = 4; i < NEIGHBORS; i++) {
			Point p1 = neighbour(p0, i);
			Point p2 = neighbour(p0, (i+1) % NEIGHBORS);
			if (isBackground(p1, object) && isObject(p2, object)) {
				return new Candidate(p1, i);
			}
		}
		return null;
	}
	
	
	private final boolean isBackground(Point pt, int object) {
		return !labels.hasIndex(pt.y, pt.x) || labels.intAt(pt.y, pt.x) != object;
	}
	
	private final boolean isObject(Point pt, int label) {
		return labels.hasIndex(pt.y, pt.x) && labels.intAt(pt.y, pt.x) == label;
	}
	
	private final Point neighbour(Point pt, int n) {
		Point np = new Point(pt.x, pt.y);
		switch (n) {
		case 0:
			np.x++;
			break;
		case 1:
			np.x++;
			np.y--;
			break;
		case 2:
			np.y--;
			break;
		case 3:
			np.x--;
			np.y--;
			break;
		case 4:
			np.x--;
			break;
		case 5:
			np.x--;
			np.y++;
			break;
		case 6:
			np.y++;
			break;
		case 7:
			np.x++;
			np.y++;
		default:
			assert (false);
		}
		return np;
	}

	
	private static Polygon toPolygon(List<Point> pts) {
		Polygon poly = new Polygon();
		poly.npoints = pts.size();
		poly.xpoints = new int[pts.size()];
		poly.ypoints = new int[pts.size()];
		
		int i = 0;
		for (Point p : pts) {
			poly.xpoints[i] = p.x;
			poly.ypoints[i] = p.y;
			i++;
		}
		return poly;
	}
}