Point-in-polygon: Jordan Curve Theorem (JS)

point_in_polygon.js

/**
 * Point-in-polygon based on Jordan Curve Theorem
 * 
 * Checks whether a point with a specific lat, long coordinates is inside 
 * a polygon defined by a given set of points. You can find more information
 * about the Jordan Curve Theorem to: 
 * http://en.wikipedia.org/wiki/Jordan_curve_theorem
 * 
 * The algorithm, originally implemented in c/c++ and can be found to   
 * http://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem.
 *  
 * Implemented to Javascript by: Apostolos Kritikos <akritiko@gmail.com> 
 * Version: 1.0, July 2012
 * 
 * Parameters:
 * 	targetX - latitude (lat) of our point of interest
 * 	targetY - longtitude (long) of our point of interest 
 *
 */
function pointInPolygon(targetX, targetY) {

	var tempX;
	var tempY;

	/* How many times the ray crosses a line-segment */
	var crossings = 0;

	/* Coordinates of the points */
	
	var polygonX = [ /* LATITUDE COORDINATES GO HERE (e.g. 11.111111, 12.121212, 13.131313, ...) */ ];
	var polygonY = [ /* LONGTITUDE COORDINATES GO HERE (e.g. 11.111111, 12.121212, 13.131313, ...) */ ];

	/* Iterate through each line */
	for ( var i = 0; i < polygonX.length; i++) {
		//This is done to ensure that we get the same result when the line goes from left to right and right to left
		if( polygonX[i] < polygonX[(i + 1) % polygonX.length]) {
			tempX = polygonX[i];
			tempY = polygonX[(i + 1) % polygonX.length];
		} else {
			tempX = polygonX[(i + 1) % polygonX.length];
			tempY = polygonX[i];
		}

		//First check if the ray is possible to cross the line
		if (targetX > tempX && targetX <= tempY && (targetY < polygonY[i] || targetY <= polygonY[(i + 1) % polygonX.length])) {
			var eps = 0.000001;
			//Calculate the equation of the line
			var dx = polygonX[(i + 1) % polygonX.length] - polygonX[i];
			var dy = polygonY[(i + 1) % polygonX.length] - polygonY[i];
			var k;

			if (Math.abs(dx) < eps) {
				k = 999999999999999999999999999;
			} else {
				k = dy / dx;
			}

			var m = polygonY[i] - k * polygonX[i];
			//Find if the ray crosses the line
			var y2 = k * targetX + m;
			if (targetY <= y2) {
				crossings++;
			}
		}
	}

	if (crossings % 2 == 1) {
		return true;
	} else {
		return false;
	}
}