0

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!

Andy Gee
  • 3,149
  • 2
  • 29
  • 44
  • Are you looking for [scanline algorithm](http://www.sunshine2k.de/coding/java/Polygon/Filling/FillPolygon.htm)? – shingo Jul 30 '22 at 07:32
  • @shingo Possibly, I do need to determine the center of each 10px x 10px coordinate within the polygon. As the number of coordinates are limited to under 5000 (nominally 100-300 cordinates), possibly an algorithm to determine if each posisble bounding box coordinate ocurrs within the polygon would be preferable. – Andy Gee Jul 30 '22 at 12:55
  • It's a bit hard to understand what you're trying to do exactly. What is your real goal? Determine if a given point is inside or outside the polygon? – Olivier Aug 04 '22 at 19:28
  • Hi @oliver, In the most basic form, I need a list of all coordinates (10px spacing) within polygon coordinates. e.g. triangle [xy, xy, xy] > xy, xy, xy, xy, xy, xy, xy, xy... ... ... etc. Right now I'm using image library to fill a polygon then testing each pixel color. I'd like a faster solution that doesn't need the image library. – Andy Gee Aug 04 '22 at 23:31
  • https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon – Olivier Aug 05 '22 at 07:07
  • By the way, `xy6802g68(0, 0)` returns `-69`. Is this intended behavior? – Olivier Aug 05 '22 at 07:37
  • @Olivier Please post an answer relaitng to https://wrfranklin.org/Research/Short_Notes/pnpoly.html - the bounty is yours, very much appreciated. I updated my question with the working code based on that. also xy6802g68(0, 0) would be out of bounds for pixels but I appreciate you mentioning it. – Andy Gee Aug 05 '22 at 17:21

1 Answers1

1

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

  • Start from the point
  • Cast a ray in some arbitrary direction and count the number of times it crosses a polygon segment
  • The parity of the number gives the result (odd: inside; even: outside)

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;
}
Olivier
  • 13,283
  • 1
  • 8
  • 24