title: Convert polygon coordinates without creating an image and testing pixel color
body: <p>I need to convert a lot of x/y pixel coordinates from polygon segments (680x680) to the grid references (68x68) the polygon contains.</p>
  <p>e.g grid references</p>
  <pre><code> 1, 2, 3, 4
   5, 6, 7, 8
   9,10,11,12 etc
  </code></pre>
  <p>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.</p>
  <p>While the overhead of generating an image in memory isn't huge, there must be a better (or faster) way to do this.</p>
  <h3>Working example with output</h3>
  <pre><code>$p = [];
  $r = [];
  $p['segments'] = [[144, 637], [225, 516], [85, 460], [30, 482]];
  $r = segments_to_grid($p, $r);
  print_r($r['grid']);
  
  Array
  (
      [0] =&gt; 3133
      [1] =&gt; 3134
      [2] =&gt; 3135
      [3] =&gt; 3136
      [4] =&gt; 3137
      [5] =&gt; 3138
      [6] =&gt; 3199
      [7] =&gt; 3200
      ...
      ...
      [157] =&gt; 4092
      [158] =&gt; 4093
      [159] =&gt; 4094
      [160] =&gt; 4095
      [161] =&gt; 4161
      [162] =&gt; 4162
      [163] =&gt; 4229
  )
  </code></pre>
  <h3>Supporting functions</h3>
  <pre><code>/**
   * 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 &lt; $max_y; $y = $y + 10) {
          for ($x = $min_x; $x &lt; $max_x; $x = $x + 10) {
            $rgb = imagecolorat($img, $x, $y);
            if (intval($rgb) &lt; 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);
  }
  </code></pre>
  <h2>Solution thanks to @Oliver's comments.</h2>
  <p>Porting <code>inpoly</code> to PHP was 168 times faster than using GD image lib.</p>
  <pre><code>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 &lt; $max_y; $y = $y + 10) {
        for ($x = $min_x; $x &lt; $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 &lt; $nvert; $j = $i++) {
      if ((($verty[$i] &gt; $testy) != ($verty[$j] &gt; $testy)) &amp;&amp; ($testx &lt; ($vertx[$j] - $vertx[$i]) * ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) + $vertx[$i])) {
        $c = !$c;
      }
    }
    return $c;
  }
  
  </code></pre>
  <p>Running this 100 times</p>
  <p>GD library version:
  <code>[segments_to_grid] =&gt; 0.0027089119 seconds</code></p>
  <p>inpoly version
  <code>[segments_to_grid2] =&gt; 0.0001449585 seconds</code></p>
  <p>168 times faster and equivalent output</p>
  <p>Thanks Oliver!</p>