多边形像素坐标转网格参考：替代GD库的高效优化方案

需求与痛点 #

需要将大量680x680像素坐标系下的多边形顶点线段，转换为该多边形覆盖的68x68网格编号（网格编号按行排列：1,2,3,4；5,6,7,8…）。原方案采用GD库绘制多边形后检测像素亮度完成转换，但每分钟需处理数千组多边形，性能无法满足需求，需寻找更高效的实现方式。

运行示例及输出 #

$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
    ...
    [163] => 4229
)

原有GD库实现 #

/**
 * 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);
}

优化方案（基于inpoly算法） #

将inpoly点-in-多边形检测算法移植到PHP后，性能比GD库版本提升168倍，且输出结果完全一致。

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;
}

性能测试结果 #

对两个版本各运行100次的耗时统计：

• GD库版本：[segments_to_grid] => 0.0027089119 seconds
• inpoly版本：[segments_to_grid2] => 0.0001449585 seconds

inpoly版本性能提升168倍，完全满足高并发处理需求。

内容的提问来源于stack exchange，提问作者Andy Gee