<?php
/**
 * Determine if coordinate pair (coords) is inside polygon (points).  If radius
 * is specified, The point may fall outside the actual polygon, may still be within $radius
 * units and still be considered inside or touching the polygon.
 *
 * @param array $coords Associative array with 2 keys (x,y) for coordinate to check
 * @param array $points Array of verticies of CONVEX polygon.  Verticies must be listed in clockwise order, and the array can not be associative.
 * @param int $coord_radius Integer defining the distance from any size of the polygon the point can be to still be considered inside
 * @return boolean True signifies the point is inside the polygon, False signifies point is outside the polygon.
 */
function point_in_polygon ($coords,$points,$coord_radius = 0)
{
	foreach ($points as $point)
	{
		$allx[] = $point['x'];
		$ally[] = $point['y'];
	}
	//determine the max and minimium x values
	$maxx = max($allx);
	$minx = min($allx);
	
	//determine the max and minimum y values
	$maxy = max($ally);
	$miny = min($ally);
	//calculate where the center of the polygon is - we will use these values to add the radius of
	//the star to the polygon.
	$xoffset = ceil((($maxx-$minx)/2)+$minx);
	$yoffset = ceil((($maxy-$miny)/2)+$miny);

	//offset the verticies on the polygon by the radius, in reference to where the center of the polygon is
	//this will let us check to see if a point is outside the polygon yet the star image overlaps an edge of the polygon.
	for ($i=0;$i<sizeof($points);$i++)
	{
		if ($points[$i]['x']>$xoffset)
			$points[$i]['x']+=$radius;
		elseif ($points[$i]['x']<$xoffset)
			$points[$i]['x']-=$radius;
		
		if ($points[$i]['y']>$yoffset)
			$points[$i]['y']+=$radius;
		elseif ($points[$i]['y']<$yoffset)
			$points[$i]['y']-=$radius;
	}
	
	/** loop through each set of coordinates - create a 2d normal for the polygon so we
	 ** can determine which side of the line segment the point falls on.
	 ** if all calculations return a negative number, the point is inside the polygon.
	 ** if there are is 1 positive result, the polygon is outside and we return false.
	*/
	for ($i=0;$i<sizeof($points);$i++)
	{
		//Determine if we're on the last coordinate, if so - we need to use the first coordinate to complete our line segment.
		$nxti = $i + 1 < sizeof($points) ? $i+1 : 0;
		
		//these 2 lines translate the line segment to where it would be if the center of the polygon were (0,0).
		$nx = $points[$nxti]['y'] - $points[$i]['y'];
		$ny = $points[$i]['x'] - $points[$nxti]['x'];

		//these 2 lines transfer the coordinates of the point to their location if the center of the polygon were (0,0).
		$x = $coords['x'] - $points[$i]['x'];
		$y = $coords['y'] - $points[$i]['y'];
		
		//determine sidedness of the point in relation to the line (positive = outside, negative = inside, = 0 on)
		$res = ($x * $nx) + ($y * $ny);
		if ($res>0)
			return false;
	}
	//all must be negative, return true its inside!	
	return true;
}

/** Points for our polygon.
 ** This is an octagon - code will work for any convex polygon.  Point coordinate pairs must be listed in clockwise order.
*/
$points = array (
		array(
			'x' => 275,
			'y' => 233
		),
		array(
			'x' => 325,
			'y' => 233
		),
		array(
			'x' => 363,
			'y' => 268
		),
		array(
			'x' => 363,
			'y' => 320
		),
		array(
			'x' => 325,
			'y' => 360
		),
		array(
			'x' => 275,
			'y' => 360
		),
		array(
			'x' => 240,
			'y' => 320
		),
		array(
			'x' => 240,
			'y' => 265
		)
	);

/* This array is a set of coordinate pairs. */
$coordset = array (
		array ('x' => 361, 'y' => 296, 'where' => 'in (between 3 and 4)'), //in
		array ('x' => 243, 'y' => 247, 'where' => 'out'), //out
		array ('x' => 240, 'y' => 265, 'where' => 'on (vertex 8)'), //on (8)
		array ('x' => 301, 'y' => 297, 'where' => 'in (the middle)'), //in (middle)
		array ('x' => 280, 'y' => 230, 'where' => 'outside but in after raduis test)') //outside but in after radius test
		);
foreach ($coordset as $coords)
	echo 'Coordinate Pair ('.$coords['x'].','.$coords['y'].') <b>'.(point_in_polygon($coords,$points)?'IS':'IS NOT').'</b> inside the polygon.<br>';
?>