Point in a Polygon

I just though I might share a function that I found in the course of trying to capture accurate mouse events in a grid Map editor for my isometric game. The function can be used to find out if a given coordinate falls within a polygon, defined by it’s bounding points.

This is a function by Jonas Raoni Soares Silva, taken from here:

function isPointInPoly(poly, pt){
    for(var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)
        ((poly[i].y <= pt.y && pt.y < poly[j].y) || (poly[j].y <= pt.y && pt.y < poly[i].y))
        && (pt.x < (poly[j].x - poly[i].x) * (pt.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x)
        && (c = !c);
    return c;
}

The function takes an object containing a property x, and property y, as well as an array, containing the bounding points of the polygon.

If you’re interested in how this applied to my isometric grid space, I’ll go over the basic concept below:

The grid space is made up of 400 (20×20 grid) images, layered and spaced in the DOM at a ratio of 2:1 W:H, making it look like a squashed diamond.

If we know the top and left value of each image, these can be used to construct an array of polygon coordinates for each tile.

Imagine a diamond in a rectangle shaped image. The left value will correspond to the x value of the first point, going from left to right, clockwise around the diamond polygon, the top value will correspond to the y value of the second point.

So going around the diamond, it would look like this;

var polyPoints=new Array(); // put this in global
 
// values known: topVal, leftVal, tileHeight and tileWidth (W/H of diamond in each tile image)
 
//for each tile(tileX,tileY):
polyPoints[tileX+"_"+tileY]=[
{x:leftVal,y:topVal+(tileHeight/2)},
{x:leftVal+(tileWidth/2),y:topVal},
{x:leftVal+tileWidth,y:topVal+(tileHeight/2)},
{x:leftVal+(tileWidth/2),y:topVal+tileHeight},
//don't forget to repeat the very first point to complete the polygon
{x:leftVal,y:topVal+(tileHeight/2)}
];

Now to determine if an event such as click or mousemove is within one of the polygons, an event listener must be added to the entire surrounding element, and on each event trigger, the entire array contained in polyPoints must be checked with the function isPointInPoly;

So when you have cursorX, cursorY, load them into an object and pass it to the following function:

var gridSize=20; //global declaration
 
function isPosInTiles(cursorPos){
var isFound=false;
var foundCoord;
for (var x=1;x<=gridSize;x++){
	for (var y=1;y<=gridSize;y++){
		if (isPointInPoly(cursorPos,polyPoints[x+"_"+y])){
			isFound=true;
			foundCoord={x:x,y:y};
		}
	}
}
if (isFound==true)
	return foundCoord;
} else {
	return false;
}
}

If the function returns anything other than false, then the event has taken place within one of the tiles, and the tile’s x and y values within the grid will be returned and can subsequently be used.

All in all, a very handy function, which I’m sure will be used many more times in the course of my work.

Leave a comment





Subscribe without commenting