package com.exh.bevel.algo;

import java.util.List;

import com.exh.math.primitive.Geo;
import com.exh.math.primitive.Point3;
import com.exh.math.primitive.Polygon;

/* EXTRUDE
 * The initial extrusion:  Convert an input polygon into 3d by generating
 * tris for each line segment.  The tris are generated by determining the
 * direction of the segment, then extending them along the perpendicular.
 * This will create gaps between segments that have a high enough difference
 * in angle, so I need to fill those in.
 */
public final class Extrude {
	private final Point3			mMid = new Point3(),
									mGap0 = new Point3(),
									mGap1 = new Point3();
	private final Point3.Order		mOrder = new Point3.Order();
	
	public Extrude() {
	}
	
	// Given a list of points, a depth (how far to extrude the
	// points) and a height (the z value of the extruded points),
	// answer a list of extruded quads.  Direction is 0 for unknown,
	// otherwise -1 for CCW and 1 for CW.
	public boolean on(	final List<Point3> src, final int direction,
						final double depth, final List<Polygon> out) {
		final boolean	isClosed = isClosed(src);

		final int		min = 0, max = src.size()-1 + (isClosed ? -1 : 0);
		int				i = 0, stop = max + 1, inc = 1;
		if (stop <= i) return false;
		boolean			cw = isClockWise(src);
		// This is actually backwards, something got a little messed up somewhere.
		if (direction != 0) cw = (direction < 0);
		// If the points are ordered clockwise, iterate backwards.
		if (cw) {
			i = max;
			stop = -1;
			inc = -1;
		}
		int				pi = i - inc,
						ni = i + inc;
		Point3			p1 = new Point3(),
						p3 = new Point3(),
						prvP3 = new Point3(),
						prv = new Point3(0, 0, 0),
						cur = new Point3(0, 0, 0),
						nxt = new Point3(0, 0, 0);
		final int		start = i;
	
		while (i != stop) {
			// Constrain the indexes to valid values
			if (pi > max) pi = 0;
			else if (pi < min) pi = max;
			if (ni > max) ni = 0;
			else if (ni < min) ni = max;
	
			prv.set(src.get(pi));
			cur.set(src.get(i));
			nxt.set(src.get(ni));

			// Every 2 points are extruded into a new quad, by generating
			// a new point for each.
			extrudePoints(cur, nxt, depth, p1, p3);
			p1.z = depth;
			p3.z = depth;
	
			if (i != start) fillGaps(prv, cur, nxt, prvP3, p1, depth, out);
	
			add(cur, p1, p3, nxt, out);
			
			prvP3.set(p3);
	
			// Increment
			pi = i;
			i += inc;
			ni += inc;
		}
		return true;
	}

	// Given two ordered points (b, c) and a depth, find
	// a new point representing the bevel at the given depth.
	private void extrudePoints(	final Point3 b, final Point3 c, final double depth,
								Point3 out1, Point3 out2) {
		final double		m_bc = Geo.perpendicularSlope(b.x, b.y, c.x, c.y);

		// Use the segment direction to decide which direction
		// to extend the new point in.
		final double		dist_bc = directionedDist(b.x, b.y, c.x, c.y, depth);
	
		// Get two new line segments, perpendicular to the supplied points.
		Geo.newPtOnLine(b.x, b.y, m_bc, dist_bc, out1);
		Geo.newPtOnLine(c.x, c.y, m_bc, dist_bc, out2);
	}

	private void fillGaps(	final Point3 prv, final Point3 cur, final Point3 nxt,
							final Point3 prvP3, final Point3 p1,
							double depth,
							final List<Polygon> out) {
		// Using my current point as the center, find the degree change
		// between the previous and next points.  If it's too high (since
		// we evaluate points clockwise, we reverse the degree evaluation),
		// then the extruded polygons overlap.
		final double		prvDeg = Geo.degree(prv.x-cur.x, prv.y-cur.y),
							nxtDeg = Geo.degree(nxt.x-cur.x, nxt.y-cur.y);
		double				check = nxtDeg - prvDeg;
		if (check < 0) check += 360;
		if (check >= 180) return;
		
		// Get the midpoint, use its slope to determine the line on
		// which the gap point resides.
		mMid.add(prvP3, p1);
		mMid.div(2);
		final double		m = Geo.slope(cur.x, cur.y, mMid.x, mMid.y);
		// Brute-force it:  Make two new gap points, going in opposite directions.
		// The one closest to the extruded points is the winner.
		Geo.newPtOnLine(cur.x, cur.y, m, depth, mGap0);
		Geo.newPtOnLine(cur.x, cur.y, m, -depth, mGap1);
		mGap0.z = depth;
		mGap1.z = depth;
		Point3				gap = mGap0;
		if (prvP3.dist3Squared(mGap1) < prvP3.dist3Squared(mGap0)) gap = mGap1;
		add(cur, prvP3, gap, null, out);
		add(cur, gap, p1, null, out);
	}
	
	private	void add(	final Point3 a, final Point3 b, final Point3 c, final Point3 d,
						final List<Polygon> out) {
		Polygon		p = new Polygon();
		if (a != null) p.add(a);
		if (b != null) p.add(b);
		if (c != null) p.add(c);
		if (d != null) p.add(d);
		mOrder.makeCcw(p.mPt, p.mSize);
		out.add(p);
	}

	private double directionedDist(	final double ax, final double ay,
									final double bx, final double by,
									final double dist) {
		double				deg = Geo.degree(bx-ax, by-ay);
		// My getDegree func doesn't correspond exactly to the
		// angles that determine direction.
		deg -= 90;
		if (deg < 0) deg += 360;
		if (deg >= 0 && deg < 180) return -dist;
		return dist;
	}
	
	// Answer true if the polygon is ordered clockwise, false
	// if it's counter.  First and last point can't repeat.
	// Original function by Paul Bourke
	// http://debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm
	private final static boolean isClockWise(final List<Point3> p)
	{
		if (p.size() < 2) return false;
		final boolean		isClosed = isClosed(p);
		final int			size = p.size() + (isClosed ? -1 : 0);
		if (size < 3) return false;
	
		int					count = 0;
		for (int i=0;i<size;i++) {
			final int		j = (i + 1) % size;
			final int		k = (i + 2) % size;
			final Point3	pi = p.get(i), pj = p.get(j), pk = p.get(k);
			double			z  = (pj.x - pi.x) * (pk.y - pj.y);
			z -= (pj.y - pi.y) * (pk.x - pj.x);
			if (z < 0) count--;
			else if (z > 0) count++;
		}
		if (count > 0) return false;
		else if (count < 0) return true;
		else return true;		// technically undetermined
	}

	private final static boolean isClosed(final List<Point3> p)
	{
		if (p.size() < 2) return false;
		return p.get(0).sameAs(p.get(p.size()-1), 0.1);
	}
}