It uses ray casting algorithm to check whether a point is inside a polygon
$(function () {
var coordinates = "20,20,30,10,20,0,10,10";
var x = 15;
var y = 15;
var lines = convertCoordinateArraysToLineSegments(coordinates);
console.log(pointInsidePolygon(x,y, lines));
});
/**
* Check if a point (x,y) is inside a polygon
* It uses ray casting algorithm
* https://rosettacode.org/wiki/Ray-casting_algorithm
* @param x x coordinate of the point
* @param y y coordinate of the point
* @param lines an array of line segments, each line segment consists of 2 pair of coordinates, representing
* two end points of the line segment. e.g. {x1=20, y1=20, x2=30, y2=10}
*/
function pointInsidePolygon(x, y, lines){
var count = 0;
$.each(lines, function( index, value ) {
if (rayIntersectLineSegment(x, y, value)){
count++;
}
});
//If count is even number, the point is outside of polygon
//If count is odd number, the point is inside polygon
return count % 2 == 1;
}
/**
* Checks if a ray (endpoint at (x,y) going off to the right direction) intersects a line segment
* If the ray coincides with the line segment (i.e. the line segment is horizontal), it returns false (not intersecting)
* If the ray intersects the end point of the line segment,
* a. If the ray intersects the higher end point (i.e. the line segment is below the ray), it returns false
* b. If the ray intersects the lower end point (i.e. the line segment is above the ray), it returns true
* @param x x coordinate of the endpoint of the ray
* @param y y coordinate of the endpoint of the ray
* @param line the line segment, containing 2 pair of coordinates, representing two end points of the line segment
*/
function rayIntersectLineSegment(x, y, line){
if (y >= Math.max(line.y1, line.y2)){
return false;
}
if (y < Math.min(line.y1, line.y2)){
return false;
}
// We want the line in linear equation standard form: a*x + b*y + c = 0
// See: http://en.wikipedia.org/wiki/Linear_equation
// Calculate a,b,c
var a = line.y2 - line.y1;
var b = line.x1 - line.x2;
var c = line.x2 * line.y1 - line.x1 * line.y2;
//For horizontal line, always return false
if (a == 0){
return false;
}
//Calculate the x coordinate given the same y coordinate as the ray's endpoint on the line segment
var x0 = (-c-b*y)/a; //transformed from a*x + b*y + c = 0
//Compare the x coordinate on the line segment with the x coordinate of the ray's endpoint
return x0 >= x;
}
/**
* Convert an array of coordinates into an array of line segments
* A line segment is represented by 2 pair of coordinates, e.g. {x1=20, y1=20, x2=30, y2=10}, each pair representing an
* end point of the line segment
* @param coordinates, a string of coordinates delimited by comma, with even index (starting 0) representing x coordinate, odd index representing y coordinate,
* e.g. (20,20,30,10,20,0,10,10)
*/
function convertCoordinateArraysToLineSegments(coordinates){
var coords = coordinates.split(',');
var points = [];
var i;
for (i = 0; i < coords.length; i+=2){
points.push({x:parseInt(coords[i]), y:parseInt(coords[i+1])});
}
var lines = [];
//Assume points.length always >= 3
for (i = 0; i < points.length - 1; i++) {
lines.push({x1:points[i].x, y1:points[i].y, x2:points[i+1].x, y2:points[i+1].y});
}
lines.push({x1:points[points.length - 1].x, y1:points[points.length - 1].y, x2:points[0].x, y2:points[0].y});
return lines;
}
