package net.beadsproject.touch;
import java.awt.Color;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import math.geom2d.AffineTransform2D;
import math.geom2d.Box2D;
import math.geom2d.Point2D;
import math.geom2d.line.LineSegment2D;
import math.geom2d.polygon.SimplePolygon2D;
import math.geom2d.polygon.convhull.GrahamScan2D;
import megamu.mesh.MPolygon;
import megamu.mesh.Voronoi;
import net.beadsproject.touch.perform.PerformNode;
import processing.core.PApplet;

/**
 * Hierarchical Voronoi Surface Layout Engine.
 * 
 * Given a PerformTree, this class will generate a layout of the leaves
 * that preserves closeness of node within the tree. Each point in the layout also has an associated
 * size which was used in the layout. Additionally the voronoi region information for each laid out
 * point is also available.
 * 
 * @author ben
 *
 */
public class HVLayout {

	public static class HVPoint extends Point2D
	{
		public PerformNode pn;
		public double radius;
		public SimplePolygon2D region;
		
		public HVPoint(Point2D p, double r)
		{
			super(p);
			radius = r;
			region = null;
		}
		
		/**
		 * Draw this point into a processing context.
		 * @param app
		 */
		public void pDraw(PApplet app)
		{	
			app.noStroke();
			Color c = new Color(Color.HSBtoRGB(pn.uniqueValue(),.8f,1f));			
			app.fill(c.getRed(),c.getGreen(),c.getBlue(),150);
			
			if (region!=null && !region.isEmpty())
			{
				app.beginShape();
				for(Point2D v: region.getVertices())
					app.vertex((float)v.x,(float)v.y);
				app.endShape();
			}
		}
	}
	
	private static final double width = 1;
	private static final double height = 1;
	private static Map<PerformNode,HVPointExt> pnToHVPointExtMap = null;
	
	private static class HVPointExt extends HVPoint
	{
		public HVPointExt parent;
		public int depth; // depth down the hierarchy		
		public ArrayList<HVPointExt> children;
		
		public HVPointExt(Point2D p, double r)
		{
			super(p,r);
		}
	}
	
	public static List<HVPoint> layout(PerformNode pt) 
	{
		// Do layout
		List<HVPointExt> allPoints = loadTree(pt);
		if (allPoints==null) return null;
		
		// Then extract just the leaf nodes and also set everything to have the same initial size.
		List<HVPoint> leafPoints = new LinkedList<HVPoint>();
		for(HVPointExt p: allPoints)
		{
			if (p.children==null)
			{
				leafPoints.add(p);
			}
		}
		double recommendedRadius = 0.5/Math.sqrt(1.0*leafPoints.size());
		for(HVPoint h: leafPoints)
		{
			h.radius = recommendedRadius;
		}
		
		return leafPoints;
	}
	
	private static List<HVPointExt> loadTree(PerformNode pt)
	{
		List<HVPointExt> points = new LinkedList<HVPointExt>();
		pnToHVPointExtMap = new HashMap<PerformNode, HVPointExt>();
		
		PerformNode root = pt.getRoot();
		if (root==null) return null;
		HVPointExt rootHVPointExt = new HVPointExt(new Point2D(width/2,height/2),width/2);
		rootHVPointExt.pn = root;	
		rootHVPointExt.parent = null;
		points.add(rootHVPointExt);
		pnToHVPointExtMap.put(root,rootHVPointExt);
		
		// recursively generate all particles
		loadNode(rootHVPointExt,points);
		
		// and then recursively subdivide the space
		if (rootHVPointExt!=null)
		{
			Box2D window = new Box2D(0,width,0,height);
			GrahamScan2D jm = new GrahamScan2D();
			rootHVPointExt.region = (SimplePolygon2D)(jm.convexHull(window.getVertices()));
			layoutNode(points, rootHVPointExt);
		}
		
		return points;
	}
	
	static private void loadNode(HVPointExt p, List<HVPointExt> points)
	{
		for (PerformNode pn: p.pn.getChildren())
		{
			HVPointExt ch = new HVPointExt(new Point2D(0,0),0);
			ch.pn = pn;
			ch.parent = p;
			ch.depth = p.depth + 1;
			if (p.children==null)
			{
				p.children = new ArrayList<HVPointExt>();
			}
			p.children.add(ch);
			points.add(ch);
			pnToHVPointExtMap.put(ch.pn,ch);
			loadNode(ch,points);
		}
	}
	
	private static void layoutNode(List<HVPointExt> pts, HVPointExt p)
	{
		if (p==null || p.children==null || p.children.isEmpty() || p.region==null || p.region.isEmpty())
		{
			if (!(p.children==null || p.children.isEmpty() || p.children.size()<3) && (p.region==null || p.region.isEmpty()))
			{
				System.err.println("Argh!");
			}
			return;
		}
		
		// special cases, 1 child
		if (p.children.size()==1) 
		{
			HVPointExt child = p.children.get(0);
			child.x = p.x;
			child.y = p.y;
			child.radius = p.radius;
			child.region = p.region;
			layoutNode(pts,child);
			return;
		}		
		
		// bad voronoi region case
		if (p.region.getVertexNumber()<=2)
		{
			System.out.println("Encountered bad voronoi region. Ignoring.");
			
			for(HVPointExt child: p.children)
			{
				child.x = p.x;
				child.y = p.y;
				child.radius = p.radius;
				child.region = p.region;
				layoutNode(pts,child);
			}
			return;
		}
		
		// first layout the particles within the particle region
		// we do this by finding the centroid of the region and applying a small perturbation to each particle
		SimplePolygon2D sp2d = p.region;
		Point2D centroid = sp2d.getCentroid();
		
		// compute the equal radius given to each child
		float area = (float) sp2d.getArea();
		float areaPerChild = area/p.children.size();
		float radiusPerChild = (float) Math.sqrt(areaPerChild/Math.PI);
		
		if (centroid==null)
		{
			centroid = new Point2D(0,0);
			for(Point2D v: p.region.getVertices())
			{
				centroid = centroid.plus(v);
			}
			centroid = centroid.scale(1./p.region.getVertexNumber());
		}
		Box2D b2d = p.region.getBoundingBox();
		float dr = (float) (Math.min(b2d.getWidth(),b2d.getHeight())/5f);
		//System.err.println(dr);
		
		// lay children on a circle
		Point2D r = new Point2D(dr,0);
		double dtheta = Math.PI*2 / p.children.size(); 
		
		for(HVPointExt c: p.children)
		{
			c.setLocation(centroid.plus(r).plus(new Point2D(Math.random()*dr*0.1,Math.random()*dr*0.1)));
			r = r.transform(AffineTransform2D.createRotation(dtheta));
			c.radius = radiusPerChild;
			
			//assert (b2d.contains(c));
		}
		
		buildVoronoi(p.children);
		for(HVPointExt c: p.children)
		{
			layoutNode(pts,c);
		}
	}
	
	static private SimplePolygon2D p2dFromMply(MPolygon m)
	{
		List<Point2D> soup = new LinkedList<Point2D>();
		for(float[] f: m.getCoords())
			soup.add(new Point2D(f[0],f[1]));
		GrahamScan2D jm = new GrahamScan2D();
		return (SimplePolygon2D)(jm.convexHull(soup));
	}
	
	static private SimplePolygon2D intersect(SimplePolygon2D a, SimplePolygon2D b)
	{
		//System.out.printf("Intersecting %s with %s\n",a,b);
		
		// Let P = A union B union L
		// where A is the set of points in polygon a which are contained in polygon b
		// and B is the set of points in poly b which are contained in poly a
		// and L is the set of all intersection points of all lines of a and b
		List<Point2D> points = new LinkedList<Point2D>();
		for(Point2D pa: a.getVertices())
		{
			//System.out.printf("%s ",pa);
			if (b.contains(pa)) points.add(pa);
		}
		//System.out.println();
		for(Point2D pb: b.getVertices())
		{
			//System.out.printf("%s is contained in a? %s\n",pb,a.contains(pb));
			if (a.contains(pb)) points.add(pb);
		}
		for(LineSegment2D la: a.getEdges())
		{
			for(LineSegment2D lb: b.getEdges())
			{
				Point2D p = la.getIntersection(lb);
				if (p!=null)
					points.add(p);
			}
		}
		
		if (points.isEmpty()) return null;
		
		GrahamScan2D jm = new GrahamScan2D();
		return (SimplePolygon2D)(jm.convexHull(points));
	}
	
	static private void buildVoronoi(ArrayList<HVPointExt> ps)
	{
		if (ps.size()<2)
		{
			return;
		}
		
		float[][] pts = new float[ps.size()][2];
		int index = 0;
		
		//System.err.printf("voronoi: ");
		for(HVPointExt p: ps)
		{
			pts[ps.size()-1-index][0] = (float) p.x;
			pts[ps.size()-1-index][1] = (float) p.y;
			index++;			
			//System.err.printf("(%.2f,%.2f) ",p.x,p.y);			
		}
		//System.err.println();
		
		Voronoi v = new Voronoi(pts);		
		
		SimplePolygon2D motherPoly = ps.get(0).parent.region;
		
		MPolygon[] polys = v.getRegions();
		for(int i=0;i<ps.size();i++)
		{
			// convert MPolygon into Polygon2D
			// then clip it against the mother polygon
			SimplePolygon2D p = p2dFromMply(polys[i]);
			SimplePolygon2D q = intersect(p,motherPoly);
			if (q==null)
			{
				System.out.printf("Error intersecting %s with %s. Continuing...\n",p,motherPoly);
				q = p;
			}
			ps.get(i).region = q;			
		}
	}
}