import java.io.File;
import java.io.FileReader;
import java.io.BufferedReader;
import uk.me.jstott.jcoord.LatLng;
import uk.me.jstott.jcoord.UTMRef;


public class PolyTest {

    /**
       Adapted from "winding number inclusion" algorithm, C++ 
       implementation at http://geomalgorithms.com/a03-_inclusion.html 

       inPoly(): winding number test for a point in a polygon
       Input:   P = a point,
       vertices[] = vertex points of a polygon V[n+1] with V[n]=V[0]
       Return:  false if 'winding number' is 0, else true.
     */
    static boolean inPolygon( Point p, Point[] vertices) {
	int    wn = 0;    // the  winding number counter
	int nVertices = vertices.length;
	// System.out.println("nVertices: " + nVertices);

	// loop through all edges of the polygon

	// edge from vertices[i] to  vertices[i+1]
	for (int i = 0; i < nVertices; i++) { 
	    int next = i + 1;
	    if (next == nVertices) {
		// Wrap around to first vertex
		next = 0;
	    }
	    // System.out.println("i: " + i + ", next: " + next);

	    if (vertices[i]._y <= p._y) {          // start y <= P._y
		if (vertices[next]._y  > p._y)  {
		    // an upward crossing
		    if (isLeft( vertices[i], vertices[i+1], p) > 0) {
			// p left of edge, have  a valid up intersect
			++wn;           
		    }
		}
	    }
	    else {                        // start y > P.y (no test needed)
		if (vertices[next]._y  <= p._y) {    // a downward crossing
		    if (isLeft( vertices[i], vertices[next], p) < 0) {
			// P right of edge
			--wn;            // have  a valid down intersect
		    }
		}
	    }
	}
	if (wn == 0) {
	    // Point is outside polygon
	    return false;
	}
	else {
	    // Point is inside polygon
	    return true;
	}
    }

    /** 
	isLeft(): tests if a point is Left|On|Right of an infinite line.
	Input:  three points P0, P1, and P2
	Return: 
	> 0 for P2 left of the line through P0 and P1 
	= 0 for P2 on the line
	< 0 for P2  right of the line

	See: Algorithm 1 "Area of Triangles and Polygons" 
	(http://geomalgorithms.com/a01-_area.html)
    */
    static double isLeft( Point p0, Point p1, Point p2 ) {
	return ( (p1._x - p0._x) * (p2._y - p0._y)
		 - (p2._x -  p0._x) * (p1._y - p0._y) );
    }



    /** 
	Get distance of point from nearest polygon edge. Based on C++ code at 
	https://gist.github.com/atduskgreg/1325002
    */
    static double distanceFromPolygon(Point p, Point[] poly) {

	double result = Double.MAX_VALUE;
    
	// check each line
	for (int i = 0; i < poly.length; i++){
	    int prevIndex = i - 1;
	    if (prevIndex < 0){
		prevIndex = poly.length - 1;
	    }
        
	    Point currPoint = poly[i];
	    Point prevPoint = poly[prevIndex];
        
	    double segmentDistance = 
		distanceFromLine(new Point(p._x,p._y), prevPoint, currPoint);
        
	    // Find minimum distance
	    if (segmentDistance < result){
		result = segmentDistance;
	    }
	}
    
	return result;
    }



    /**
       Get distance of point from specified line. Based on C++ code from 
       	https://gist.github.com/atduskgreg/1325002
     */
    static double distanceFromLine(Point p, Point end1, Point end2) {
	double xDelta = end2._x - end1._x;
	double yDelta = end2._y - end1._y;
 
	double u = 
	    ((p._x - end1._x) * xDelta + (p._y - end1._y) * yDelta) / 
	    (xDelta * xDelta + yDelta * yDelta);
    
	Point closestPointOnLine;
	if (u < 0) {
	    closestPointOnLine = end1;
	} 
	else if (u > 1) {
	    closestPointOnLine = end2;
	} 
	else {
	    closestPointOnLine = 
		new Point(end1._x + u * xDelta, end1._y + u * yDelta);
	}
    
	Point d = 
	    new Point(p._x - closestPointOnLine._x, p._y - 
		      closestPointOnLine._y);

	return Math.sqrt(d._x * d._x + d._y * d._y); // distance
    }
 

    /** Return true if line segment crosses a polygon edge */
    static boolean crossesPolygonEdge(Point end1, Point end2, 
				      Point[] vertices) {

	// Ignore last vertex, as it is copy of first
	int nVertices = vertices.length - 1;
	int lastIndex = vertices.length - 2;

	for (int i = 0; i < nVertices; i++) {

	    int prevIndex = i - 1;
	    if (prevIndex < 0) {
		// prevIndex = vertices.length - 1;
		prevIndex = lastIndex;
	    }
	    Point vertex = vertices[i];
	    Point prevVertex = vertices[prevIndex];

	    if (segmentsIntersect(end1, end2, vertex, prevVertex)) {
		/* ***
		System.out.println("Crosses polygon edge (index " + i + ": " + 
				   vertex.printLatLon() + ") (index: " + 
				   prevIndex + " " +  
				   prevVertex.printLatLon() + ")");
				   **** */
		return true;
	    }
	}

	// No intersections
	return false;
    }


    /** Return true if p1 and p2 are on either size of xvalue, false if both are on the same side. */
    static boolean straddlesX(Point p1, Point p2, double xvalue) {
	double m = (p1._x - xvalue) * (p2._x - xvalue);
	if (m > 0) {
	    // Both offsets are negative or both are positive from xvalue - they're on the same side
	    return false;
	}
	else {
	    return true;
	}
    }


    /** Return true if two line segments intersect, else return false */
    static boolean segmentsIntersect(Point seg1_1, Point seg1_2, 
			      Point seg2_1, Point seg2_2) {

	if (Math.max(seg1_1._x, seg1_2._x) < Math.min(seg2_1._x, seg2_2._x)) {
	    // No mutual absciscca 
	    return false;
	}

	if (seg1_1._x == seg1_2._x && seg2_1._x == seg2_2._x) {
	    // Two vertical segments; no intersection
	    return false;
	}

	if (seg1_1._x == seg1_2._x) {
	    // Vertical segment
	    return straddlesX(seg2_1, seg2_2, seg1_1._x);
	}

	if (seg2_1._x == seg2_2._x) {
	    // Vertical segment
	    return straddlesX(seg1_1, seg1_2, seg2_1._x);
	}

	// If any endpoints touch each other, then return true
	if ((seg1_1._x == seg2_1._x && seg1_1._y == seg2_1._y) ||
	    (seg1_2._x == seg2_1._x && seg1_2._y == seg2_1._y) ||
	    (seg1_1._x == seg2_2._x && seg1_1._y == seg2_2._y) ||
	    (seg1_2._x == seg2_2._x && seg1_2._y == seg2_2._y)) {
 
	    return true;
	}


	// Compute segment slopes
	double m1 = (seg1_1._y - seg1_2._y) / (seg1_1._x - seg1_2._x);
	double m2 = (seg2_1._y - seg2_2._y) / (seg2_1._x - seg2_2._x);
	if (m1 == m2) {
	    // Parallel - no intersection
	    return false;
	}

	// Compute segment y-intercepts
	double b1 = seg1_1._y - m1 * seg1_1._x;
	double b2 = seg2_1._y - m2 * seg2_1._x;

	// Compute abscissa of intersection
	double xInt = (b2 - b1) / (m1 - m2);

	if (xInt < Math.max(Math.min(seg1_1._x, seg1_2._x), 
			    Math.min(seg2_1._x, seg2_2._x)) ||

	    xInt > Math.min(Math.max(seg1_1._x, seg1_2._x),
			    Math.max(seg2_1._x, seg2_2._x))) {
	    return false;
	}
	else {
	    return true;
	}
    }



    /** Read polygon UTM coordinates from KML file that contains exactly one
	polygon */
    static Point[] readPolygonKMLtoUTM(String filename) throws Exception {

	Point[] vertices = null;
	    
	BufferedReader reader = null;
	try {
	    reader = 
		new BufferedReader(new FileReader(new File(filename)));
	}
	catch (Exception e) {
	    throw new Exception("Couldn't open file " + filename + 
				": " + e);
	}
	    
	boolean readingCoordinates = false;

	while (true) {
	    String line = reader.readLine();
	    if (line == null) {
		break;
	    }
	    line = line.trim();

	    if (line.equals("</coordinates>")) {
		break;
	    }

	    if (line.equals("<coordinates>")) {
		readingCoordinates = true;
		continue;
	    }

	    if (readingCoordinates) {
		// Coordinates consist of comma-separated "triplets" containing
		// longitude, latitude, elevation. 
		String[] tokens = line.split("[\\s,;\\n\\t]+");
		if (tokens.length %3 != 0) {
		    System.err.println("Unexpected number of coordinate tokens (" + 
				       tokens.length + ") in " + line);
		    continue;
		}


		// Don't include last polygon vertex which is normally a copy of the first
		// vertex.
		System.out.println("Reading " + (tokens.length/3) + " points");
		vertices = new Point[(tokens.length/3)];
		
		int nVertex = 0;
		for (int i = 0; i < tokens.length; i += 3) {
		    /* ***
		    System.out.println("point " + i/3 + ": " + 
				       tokens[i] + ", " + tokens[i+1] + ", " +
				       tokens[i+2]);
				       *** */
		    vertices[nVertex++] = new Point(tokens[i+1], tokens[i]);
		}

		break;
	    }

	}

	reader.close();
	return vertices;
    }


    

    public static void main(String[] args) {

	boolean error = false;
	Point startPoint = null;
	Point destPoint = null;

	if (args.length != 5) {
	    error = true;
	}
	else {
	    
	    // Starting coordinates
	    try {
		startPoint = new Point(args[0], args[1]);
	    }
	    catch (Exception e) {
		System.err.println("Invalid start point: " + e.getMessage());
		error = true;
	    }

	    // Destination coordinates
	    try {
		destPoint = new Point(args[2], args[3]);
	    }
	    catch (Exception e) {
		System.err.println("Invalid destination point: " + 
				   e.getMessage());
		error = true;
	    }

	}
	if (error) {
	    System.err.println("usage: startLat startLon destLat destLon polygonKMLFile");
	    return;
	}

	String filename = args[4];

	Point[] polygon = null;
	// Read polygon from file
	try {
	    polygon = readPolygonKMLtoUTM(filename);
	}
	catch (Exception e) {
	    System.err.println("Error reading polygon: " + e);
	    return;
	}


	if (inPolygon(startPoint, polygon)) {
	    System.out.println("start point (" + startPoint.printLatLon() + 
			       ") is inside the polygon");
	}
	else {
	    System.out.println("start point (" + startPoint.printLatLon() + 
			       ") is OUTSIDE the polygon");
	}

	if (inPolygon(destPoint, polygon)) {
	    System.out.println("dest point (" + destPoint.printLatLon() + 
			       ") is inside the polygon");
	}
	else {
	    System.out.println("dest point (" + destPoint.printLatLon() + 
			       ") is OUTSIDE the polygon");
	}

	if (crossesPolygonEdge(startPoint, destPoint, polygon)) {
	    System.out.println("start-dest crosses polygon edge");
	}
	else {
	    System.out.println("start-dest does NOT cross polygon edge");
	}


	System.out.println("\n");

	// Safety check
	boolean safe = false;
	if (inPolygon(destPoint, polygon)) {

	    if (inPolygon(startPoint, polygon)) {

		if (!crossesPolygonEdge(startPoint, destPoint, polygon)) {
		    // Transect never leaves polygon
		    System.out.println("Transect never leaves safe polygon");
		    safe = true;
		}
		else {
		    System.out.println("Transect exits safe polygon");
		}
	    }
	    else {
		// Transect enters and ends in polygon
		System.out.println("Transect ends in safe polygon");
		safe = true;
	    }
	}
	else {
	    System.out.println("Destination not in safe polygon");
	}
	
	// If safe, exit with code 0. Else exit with code 1
	if (safe) {
	    System.out.println("SAFE");
	    System.exit(0);
	}
	else {
	    System.out.println("NOT SAFE");
	    System.exit(1);
	}
    }


    static class Point {

	Point(double x, double y) {
	    _x = x;
	    _y = y;
	    
	    // How to convert to lat/lon? Need UTM zone!
	}

	double _x;
	double _y;
	double _latitude;
	double _longitude;

	Point(String latStr, String lonStr) throws Exception {

	    // Destination coordinates
	    try {
		_latitude = Double.parseDouble(latStr);
		if (_latitude > 90. || _latitude < -90.) {
		    throw new Exception("Invalid latitude");
		}
	    }
	    catch (Exception e) {
		throw new Exception("Invalid latitude: " + latStr);
	    }

	    try {
		_longitude = Double.parseDouble(lonStr);
		if (_longitude > 360. || _longitude < -360.) {
		    throw new Exception("Invalid longitude");
		}
	    }
	    catch (Exception e) {
		throw new Exception("Invalid longitude: " + lonStr);
	    }

	    UTMRef utm = (new LatLng(_latitude, _longitude)).toUTMRef();
	    _x = utm.getEasting();
	    _y = utm.getNorthing();
	}

	public String printUTM() {
	    return "east: " + _x + " north: " + _y;
	}


	public String printLatLon() {
	    return "lat: " + _latitude + " lon: " + _longitude;
	}

    }
}