phpalgorithmgeometrypolygonpoint-in-polygon

Convert polygon coordinates without creating an image and testing pixel color

I need to convert a lot of x/y pixel coordinates from polygon segments (680x680) to the grid references (68x68) the polygon contains.

e.g grid references

 1, 2, 3, 4
 5, 6, 7, 8
 9,10,11,12 etc

Performance is the ultimate goal. My working script does the job however with thousands of sets of polygon segments each minute I'm looking to improve speed further. Currently I'm using the GD library to draw a polygon, then with help of a bounding box, testing the brightness of each polygon pixel to get x/y coordinates, then finally converting those to a grid reference.

While the overhead of generating an image in memory isn't huge, there must be a better (or faster) way to do this.

Working example with output

$p = [];
$r = [];
$p['segments'] = [[144, 637], [225, 516], [85, 460], [30, 482]];
$r = segments_to_grid($p, $r);
print_r($r['grid']);

Array
(
    [0] => 3133
    [1] => 3134
    [2] => 3135
    [3] => 3136
    [4] => 3137
    [5] => 3138
    [6] => 3199
    [7] => 3200
    ...
    ...
    [157] => 4092
    [158] => 4093
    [159] => 4094
    [160] => 4095
    [161] => 4161
    [162] => 4162
    [163] => 4229
)

Supporting functions

/**
 * Convert a list of x/y coordinates to grid references
 *
 * @param array $p
 * @param array $r
 *
 * @return array augmented $r
 */
function segments_to_grid($p, $r) {
  $p['segments'] = isset($p['segments']) ? $p['segments'] : [];
  // e.g, [[144,637],[225,516],[85,460],[30,482]]

  // Return array
  $r['grid'] = [];


  // Define base dimensions
  $w = 680;
  $h = 680;
  $poly_coords = [];
  $min_x = $min_y = 680;
  $max_x = $max_y = 0;

  // Build an imagefilledpolygon compatible array and extract minimum and maximum for bounding box
  foreach ($p['segments'] as $segment) {
    $poly_coords[] = $segment[0];
    $poly_coords[] = $segment[1];
    $min_x = min($min_x, $segment[0]);
    $min_y = min($min_y, $segment[1]);
    $max_x = max($max_x, $segment[0]);
    $max_y = max($max_y, $segment[1]);
  }

  // check we have something useful
  if (!empty($poly_coords)) {
    $r['code'] = 40;

    // create image
    $img = imagecreatetruecolor($w, $h);

    // allocate colors (white background, black polygon)
    $bg   = imagecolorallocate($img, 255, 255, 255);
    $black = imagecolorallocate($img, 0, 0, 0);

    // fill the background
    imagefilledrectangle($img, 0, 0, $w, $h, $bg);

    // draw a polygon
    if (imagefilledpolygon($img, $poly_coords, count($p['segments']), $black)) {
      $r['code'] = 0;

      // loop through the image and find the points that are black
      for ($y = $min_y; $y < $max_y; $y = $y + 10) {
        for ($x = $min_x; $x < $max_x; $x = $x + 10) {
          $rgb = imagecolorat($img, $x, $y);
          if (intval($rgb) < 16777215) {
            $r['grid'][] = xy6802g68($x, $y);
          }
        }
      }
    } else {
      $r['error'] = 'poly fail';
      $r['code'] = 10;
    }
    imagedestroy($img);
  } else {
    $r['error'] = 'no coordinates';
    $r['code'] = 20;
  }
  return ($r);
}


/**
 * Converts X/Y 680x680 to 68x68 grid reference number.
 *
 * @param int $cX pixel x positon
 * @param int $cY pixel y positon
 * @return int grid reference number
 */

function xy6802g68($cX, $cY) {
  $calcX = ceil($cX / 10) - 1;
  $calcY = ceil($cY / 10) - 1;
  $grid68 = $calcX + ($calcY * 68);
  return ($grid68);
}

Solution thanks to @Oliver's comments.

Porting inpoly to PHP was 168 times faster than using GD image lib.

function segments_to_grid2($p, $r) {

  // Define base dimensions
  $vertx = $verty = [];
  $min_x = $min_y = 680;
  $max_x = $max_y = 0;

  foreach ($p['segments'] as $segment) {
    $vertx[] = $segment[0];
    $verty[] = $segment[1];
    $min_x = min($min_x, $segment[0]);
    $min_y = min($min_y, $segment[1]);
    $max_x = max($max_x, $segment[0]);
    $max_y = max($max_y, $segment[1]);
  }

  if (!empty($vertx)) {
    $nvert = count($vertx);
    for ($y = $min_y; $y < $max_y; $y = $y + 10) {
      for ($x = $min_x; $x < $max_x; $x = $x + 10) {
        if (inpoly($nvert, $vertx, $verty, $x, $y)) {
          $r['grid'][] = xy6802g68($x, $y);
        }
      }
    }
  }
  return $r;
}

function inpoly($nvert, $vertx, $verty, $testx, $testy) {
  $i = $j = $c = 0;
  for ($i = 0, $j = $nvert - 1; $i < $nvert; $j = $i++) {
    if ((($verty[$i] > $testy) != ($verty[$j] > $testy)) && ($testx < ($vertx[$j] - $vertx[$i]) * ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) + $vertx[$i])) {
      $c = !$c;
    }
  }
  return $c;
}

Running this 100 times

GD library version: [segments_to_grid] => 0.0027089119 seconds

inpoly version [segments_to_grid2] => 0.0001449585 seconds

168 times faster and equivalent output

Thanks Oliver!

Solution

  • Testing if a point lies inside a polygon is a well-known problem. The classical solution is an algorithm called "ray casting":

    A C implementation of the algorithm is given here:

    int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) &&
     (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
       c = !c;
  }
  return c;
}

    A possible PHP version is:

    function pnpoly($nvert, $vertx, $verty, $testx, $testy) {
  $c = false;
  for ($i = 0, $j = $nvert - 1; $i < $nvert; $j = $i++) {
    if ((($verty[$i] > $testy) != ($verty[$j] > $testy))
      && ($testx < ($vertx[$j] - $vertx[$i]) * ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) + $vertx[$i])) {
        $c = !$c;
    }
  }
  return $c;
}