Find Random Coordinates Within a Boundary

When testing a location-enabled app or site, you’re going to need various locations for testing. One way to find these points is to pop open Google Maps and clicking around, copying these points, and pasting them into your site/app.

This is what I did. For about 5 minutes. Before I remember I was a developer.

Scenario

I need to find random points throughout the U.S. with as little effort on my part as possible.

Architecture

  • Feed it known bounds
  • Find a point within those bounds

Execution

First, we need some points. I opened up Google Maps, and grabbed 4 points which roughly outlined the continental U.S.:

Four points that give us a rough outline of the continental U.S.

Take these four points and add them to an array:

// define bounding points
// "cardinal" key not required, but useful for
// keeping track of the points
// note these need to be listed in order
// either clockwise or counter-clockwise
$points = [
	[
		"cardinal" => "NW",
		"Y" => 48.098490,
		"X" => -124.420681
	],
	[
		"cardinal" => "SW",
		"Y" => 32.469436,
		"X" => -117.482643
	],
	[
		"cardinal" => "SE",
		"Y" => 25.121507,
		"X" => -81.038997
	],
	[
		"cardinal" => "NE",
		"Y" => 47.162174,
		"X" => -68.432636
	]
];

Now we need to find the minimum X, maximum X, minimum Y and maximum Y within our points.

// find the minimum and maximum X and Y points
// across all given points
for ($i = 0; $i < count($points); $i++) {
	if ($points[$i]["X"] > $maxx) {
		$maxx = $points[$i]["X"];
	}
	if ($points[$i]["X"] < $minx) {
		$minx = $points[$i]["X"];
	}
	if ($points[$i]["Y"] > $maxy) {
		$maxy = $points[$i]["Y"];
	}
	if ($points[$i]["Y"] < $minx) {
		$miny = $points[$i]["Y"];
	}
}

Then we can get a random point within our min/max bounds. Because we want number that look like coordinates (a float rounded to 6 places), we’ll do some math.

// create a random point within our minX/maxX and minY/maxY bounds
$randomPoint = [
	"Y" => round($miny + ($maxy - $miny) * (mt_rand() / mt_getrandmax()), 6),
	"X" => round($minx + ($maxx - $minx) * (mt_rand() / mt_getrandmax()), 6)
];

This will get a random percentage (mt_rand() / mt_getrandmax()), multiply it by the difference of our min/max points ($maxy – $miny) and then add back the minimum point to ensure that we never go below that. Do this for each of the X and Y coordinates.

Now let’s create a function to check if our random coordinate is within our bounds. We’ll need to do two things:

  • Loop over each given point and the given point before it in the list
  • Check if our random point is within the bounds of each of those two points
// get the point at the end of the array
$j = count($points) - 1;
$output = false;

for ($i = 0; $i < count($points); $i++)
{
	if ($points[$i]["X"] < $point["X"]
		&& $points[$j]["X"] >= $point["X"] 
		|| $points[$j]["X"] < $point["X"]
		&& $points[$i]["X"] >= $point["X"]
		) {

This will loop over our points array and do a simple check to make sure our point is within the min/maxes of the two given points. The next check is a little more messy.

if ($points[$i]["Y"]
	+ ($point["X"] - $points[$i]["X"])
	/ ($points[$j]["X"] - $points[$i]["X"])
	* ($points[$j]["Y"] - $points[$i]["Y"])
	< $point["Y"]
	) {

This post from StackOverflow explains the math for this one better than I ever could. The above is adapted from there. If it passes both of these test, we’ve found our lucky point. If not, reset the testing points and try again.

            $output = true;
            break;
        }
    }
    $j = $i;
}

Putting it all together

Now that we have the basic idea, we can put it all together.

// define bounding points
// "cardinal" key not required, but useful for
// keeping track of the points
$points = [
	[
		"cardinal" => "NW",
		"Y" => 48.098490,
		"X" => -124.420681
	],
	[
		"cardinal" => "SW",
		"Y" => 32.469436,
		"X" => -117.482643
	],
	[
		"cardinal" => "SE",
		"Y" => 25.121507,
		"X" => -81.038997
	],
	[
		"cardinal" => "NE",
		"Y" => 47.162174,
		"X" => -68.432636
	]
];

$randomPosition = getRandomCoordinateWithinBounds($points);

var_dump($randomPosition);

/**
 * Find the bounds of all given points and return a point within
 * those bounds
 * @param  array $points an array of X/Y points
 * @return array         an array containing a random point
 *                       within the given bounds
 */
function getRandomCoordinateWithinBounds($points)
{
	$minx = 0;
	$maxx = 0;
	$miny = 0;
	$maxy = 0;

	// find the minimum and maximum X and Y points
	// across all given points
	for ($i = 0; $i < count($points); $i++) {
		if ($points[$i]["X"] > $maxx) {
			$maxx = $points[$i]["X"];
		}
		if ($points[$i]["X"] < $minx) {
			$minx = $points[$i]["X"];
		}
		if ($points[$i]["Y"] > $maxy) {
			$maxy = $points[$i]["Y"];
		}
		if ($points[$i]["Y"] < $minx) {
			$miny = $points[$i]["Y"];
		}
	}

	// create a random point within our minX/maxX and minY/maxY bounds
	$randomPoint = [
		"Y" => round($miny + ($maxy - $miny) * (mt_rand() / mt_getrandmax()), 6),
		"X" => round($minx + ($maxx - $minx) * (mt_rand() / mt_getrandmax()), 6)
	];

	// check if the random point is within our bounds
	// if not, create a new random point and try again
	while(!pointIsInCoordinates($points, $randomPoint)) {
		$randomPoint = [
			"Y" => round($miny + ($maxy - $miny) * (mt_rand() / mt_getrandmax()), 6),
			"X" => round($minx + ($maxx - $minx) * (mt_rand() / mt_getrandmax()), 6)
		];
	}

	return $randomPoint;
}

function pointIsInCoordinates($points, $point)
{
	// get the point at the end of the array
	$j = count($points) - 1;
	$output = false;

	for ($i = 0; $i < count($points); $i++)
	{
	    if ($points[$i]["X"] < $point["X"] && $points[$j]["X"] >= $point["X"] || $points[$j]["X"] < $point["X"] && $points[$i]["X"] >= $point["X"])
	    {
	        if ($points[$i]["Y"] + ($point["X"] - $points[$i]["X"]) / ($points[$j]["X"] - $points[$i]["X"]) * ($points[$j]["Y"] - $points[$i]["Y"]) < $point["Y"])
	        {
	            return true;
	        }
	    }
	    $j = $i;
	}
	return $output;
}

And here are a few sample runs:

array(2) {
  ["Y"]=>
  float(40.677512)
  ["X"]=>
  float(-117.252285)
}
array(2) {
  ["Y"]=>
  float(35.417051)
  ["X"]=>
  float(-108.168416)
}
array(2) {
  ["Y"]=>
  float(41.935556)
  ["X"]=>
  float(-91.457633)
}
array(2) {
  ["Y"]=>
  float(41.043278)
  ["X"]=>
  float(-101.268073)
}
The four random points

Leave a Reply

Your email address will not be published.