如何遍历二维坐标中的邻居？
How to iterate through neighbours in 2D coordinates?
在二维平面中，我想检查相邻点直到满足条件。例如，在此图像中取一个红色像素 (x,y)。我想迭代以找到最接近所选红色像素的白色像素。
提供的更新图片
我原来的代码现在已经无关紧要了。
一个可能的解决方案是创建一个按距离排序的数组（在图像上给出）。然后，通过遍历这个数组，检查何时满足条件（例如，点是白色的）。但是，这个数组将是不确定的，而且有点矫枉过正。
// $x,$y is a given point
$array = array(
'0,0'=>0,
'-1,0'=>1,
'-1,-1'=>1.4
);
asort($array)
foreach($array as $a=>$b){
$c=explode(',',$a);
$x2=$c[0]; // x-axis distance from the given point
$y2=$c[1]; // y-axis distance from the given point
$x3=$x+$x2;
$y3=$y+$y2;
if( $x3,$y3 point is white) { break;}
}
$closest_distance=$b;
因此，我们需要在没有预定义的情况下构建循环 $array。
您可以创建一个坐标偏移列表，这些坐标偏移按它们到基点的距离排序。那么你的搜索函数写起来就简单多了：
maxRows,maxCols = 16,16
offsets = (offset for dx in range(maxRows) for dy in range(maxCols)
for offset in [(dx,dy),(dx,-dy),(-dx,dy),(-dx,-dy)])
offsets = sorted(offsets,key=lambda xy:xy[0]**2+xy[1]**2)[1:]
def closestPoint(pixels,row,col,value):
for dx,dy in offsets:
r,c = row+dy,col+dx
if r not in range(len(pixels)): continue
if c not in range(len(pixels[0])): continue
if pixels[r][c] == value: return r,c
return None,None
输出：
bitmap = [
[4, 2, 1, 2, 7, 3, 7, 2, 8, 7, 7, 8, 1, 7, 7, 6],
[6, 8, 3, 7, 1, 7, 8, 8, 8, 2, 4, 5, 8, 2, 5, 4],
[3, 2, 1, 6, 2, 7, 2, 2, 2, 2, 8, 2, 3, 5, 2, 7],
[8, 4, 4, 5, 2, 6, 7, 2, 6, 5, 6, 4, 5, 6, 7, 8],
[2, 6, 7, 2, 8, 6, 6, 8, 7, 6, 8, 6, 2, 8, 2, 8],
[6, 1, 7, 3, 7, 8, 8, 3, 0, 5, 6, 8, 4, 4, 5, 2],
[1, 5, 1, 7, 4, 5, 2, 2, 3, 7, 3, 3, 4, 2, 5, 4],
[1, 8, 5, 8, 1, 8, 2, 5, 4, 5, 4, 7, 2, 5, 7, 5],
[6, 6, 8, 6, 2, 6, 4, 1, 3, 4, 3, 6, 3, 6, 3, 7],
[6, 6, 5, 7, 3, 7, 3, 8, 1, 8, 2, 6, 3, 8, 2, 3],
[7, 5, 3, 1, 4, 3, 4, 3, 3, 5, 8, 5, 4, 4, 3, 3],
[2, 2, 1, 5, 1, 6, 6, 3, 8, 4, 1, 5, 2, 2, 1, 6],
[6, 2, 7, 1, 7, 4, 3, 5, 8, 6, 6, 3, 1, 2, 8, 5],
[1, 5, 1, 2, 2, 6, 3, 2, 3, 7, 4, 5, 6, 1, 8, 1],
[7, 6, 5, 2, 7, 2, 4, 8, 5, 1, 1, 4, 6, 1, 7, 7],
[2, 7, 3, 2, 1, 8, 6, 1, 6, 7, 4, 6, 7, 6, 2, 4]]
for p in range(1,9):
print(p,closestPoint(bitmap,5,8,p))
1 (8, 7)
2 (6, 7)
3 (6, 8)
4 (7, 8)
5 (5, 9)
6 (4, 9)
7 (4, 8)
8 (4, 7)
请注意，如果您要检查矩阵中的每个位置，使用邻近细化算法创建距离矩阵会更有效。
通过偏移达到最大距离将跳过 75% 的结果位置。如果您事先不知道最大大小，或者如果您想避免在偏移循环中无用的位置跳过，您可以保留一个大小位置字典，它映射到给定基数的有效位置：
posByDist = dict()
def getPositionsByDistance(height,width,r,c):
positions = posByDist.get((height,width,r,c),[])
if not positions:
offsets = ((dr*dr+dc*dc,dr,dc) for dx in range(height)
for dy in range(width)
for dr,dc in [(dx,dy),(dx,-dy),(-dx,dy),(-dx,-dy)]
if r+dr in range(height) and c+dc in range(width) )
positions = [(r+dr,c+dc) for _,dr,dc in sorted(offsets)]
posByDist[height,width,r,c] = positions
return positions
def closestPoint(pixels,row,col,value):
h,w = len(pixels),len(pixels[0])
return next(((r,c) for r,c in getPositionsByDistance(h,w,row,col)
if pixels[r][c] == value),(None,None))
这将只循环遍历有效位置，并将根据您实际遇到的尺寸和基本位置的需要动态创建和重复使用位置图。
即使这个问题已经有了一个可接受的答案，我还是想添加我的两个位（和一个 PHP 实现）和一个算法来满足 return 所有的额外请求最近的像素。
算法的描述（不知道这个有没有名字，我只是想了一个东西）：扩展到起点周围的外缘，并在这些像素之间寻找匹配项。如果找到 none，则移动到下一个边缘，依此类推，直到找到匹配项或者您已经触及所有边的边界（整个图像中没有匹配项）。可视化可能有助于理解；假设0为起点，那么1是第一个rim，2是第二个，3是第三个：
+---+---+---+---+---+---+---+---+---+
| | | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 2 | 2 | 2 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 2 | 2 | 2 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
为了避免在到达远处边缘时必须处理大量元素，而不是扩展到所有边缘元素，我们首先扩展到最近的像素，然后是下一个最接近的像素，依此类推上，遵循这些规则：
- 任何边缘中最接近的像素是一个坐标保持不变而另一个坐标偏移边缘距离的像素。例如，在 rim 2 中，最接近的是
dx = 0 && dy = +/-2 和 dx = +/-2 && dy = 0. 的那些
- 任何边缘中下一个最接近的像素是之前未更改的坐标现在偏移 1 的像素，因此在我们的示例中
dx = +/-1 && dy = +/-2 和 dx = +/-2 && dy = +/-1。
- 我们不断将此变量偏移量增加 1，直到它等于固定偏移量（边缘距离，在我们的示例中为 2）。
这个逐渐扩展的视觉帮助（S 是起点，o 标记我们在给定步骤中获取的像素，- 标记我们已经检查过的像素） :
Step 1:
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
| | o | S | o | |
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Step 2:
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
| | - | S | - | |
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Step 3:
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
| | - | - | - | |
+---+---+---+---+---+
| o | - | S | - | o |
+---+---+---+---+---+
| | - | - | - | |
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
Step 4:
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
| - | - | S | - | - |
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
Step 5:
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
| - | - | - | - | - |
+---+---+---+---+---+
| - | - | S | - | - |
+---+---+---+---+---+
| - | - | - | - | - |
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
这个算法的优点是它实际上不需要任何距离计算，而且无论我们离起点有多远，一次处理的像素都不会超过 8 个。缺点是它的迭代量很大。它有利于找到接近的匹配项。
PHP实现（以左上角为根[0, 0]）：
/**
* Finds pixels with the lowest geometrical distance from given point (x, y) that match the criteria.
*/
function findGeometricallyClosestPixels(array $grid, int $x, int $y, string $criteria): array
{
// if grid is empty or we're out of bounds
if (empty($grid) || !isset($grid[$y]) || !isset($grid[0][$x])) {
return [];
}
if ($grid[$y][$x] === $criteria) {
return [[$x, $y]];
}
$result = [];
for ($offset = 1; $offset < calculateMaximumOffset($grid, $x, $y); $offset++) {
$result = array_merge($result, getClosestPixels($grid, $x, $y, $offset, $criteria));
if (!empty($result)) {
return $result;
}
for ($d = 1; $d <= $offset; $d++) {
$result = array_merge($result, getPixelsForNegativeYOffsets($grid, $x, $y, $offset, $d, $criteria));
$result = array_merge($result, getPixelsForPositiveYOffsets($grid, $x, $y, $offset, $d, $criteria));
if (!empty($result)) {
return $result;
}
}
}
return $result;
}
function getClosestPixels(array $grid, int $x, int $y, int $offset, string $criteria): array
{
$result = [];
if (isset($grid[$y][$x - $offset]) && $grid[$y][$x - $offset] === $criteria) {
$result[] = [$x - $offset, $y];
}
if (isset($grid[$y][$x + $offset]) && $grid[$y][$x + $offset] === $criteria) {
$result[] = [$x + $offset, $y];
}
if (isset($grid[$y - $offset][$x]) && $grid[$y - $offset][$x] === $criteria) {
$result[] = [$x, $y - $offset];
}
if (isset($grid[$y + $offset][$x]) && $grid[$y + $offset][$x] === $criteria) {
$result[] = [$x, $y + $offset];
}
return $result;
}
function getPixelsForNegativeYOffsets(array $grid, int $x, int $y, int $offset, int $d, string $criteria): array
{
if (!isset($grid[$y - $d])) {
return [];
}
$result = [];
if (isset($grid[$y - $d][$x - $offset]) && $grid[$y - $d][$x - $offset] === $criteria) {
$result[] = [$x - $offset, $y - $d];
}
if (isset($grid[$y - $d][$x + $offset]) && $grid[$y - $d][$x + $offset] === $criteria) {
$result[] = [$x + $offset, $y - $d];
}
if (!isset($grid[$y - $offset])) {
return $result;
}
if (isset($grid[$y - $offset][$x - $d]) && $grid[$y - $offset][$x - $d] === $criteria) {
$result[] = [$x - $d, $y - $offset];
}
if (isset($grid[$y - $offset][$x + $d]) && $grid[$y - $offset][$x + $d] === $criteria) {
$result[] = [$x + $d, $y - $offset];
}
return $result;
}
function getPixelsForPositiveYOffsets(array $grid, int $x, int $y, int $offset, int $d, string $criteria): array
{
if (!isset($grid[$y + $d])) {
return [];
}
$result = [];
if (isset($grid[$y + $d][$x + $offset]) && $grid[$y + $d][$x + $offset] === $criteria) {
$result[] = [$x + $offset, $y + $d];
}
if (isset($grid[$y + $d][$x - $offset]) && $grid[$y + $d][$x - $offset] === $criteria) {
$result[] = [$x - $offset, $y + $d];
}
if (!isset($grid[$y + $offset])) {
return $result;
}
if (isset($grid[$y + $offset][$x - $d]) && $grid[$y + $offset][$x - $d] === $criteria) {
$result[] = [$x - $d, $y + $offset];
}
if (isset($grid[$y + $offset][$x + $d]) && $grid[$y + $offset][$x + $d] === $criteria) {
$result[] = [$x + $d, $y + $offset];
}
return $result;
}
/**
* Calculates maximum offset needed to reach the edge of given grid for given starting point.
*
* Lowest possible offset is right in the middle of the greater grid dimension (width or height). Since grid starts
* at zero, if the point is positioned past the middle, then offset will equal its position. Otherwise, it will equal
* greater dimension minus its position increased by one (to compensate for the fact that dimensions are measured
* starting at 1, but positions start at 0).
*/
function calculateMaximumOffset(array $grid, int $x, int $y): int
{
$gridHeight = count($grid);
$gridWidth = count($grid[0]);
if ($gridHeight >= $gridWidth) {
$relevantDimensionValue = $gridHeight;
$relevantCoordinateValue = $y;
} else {
$relevantDimensionValue = $gridWidth;
$relevantCoordinateValue = $x;
}
$half = floor($relevantDimensionValue / 2);
if ($relevantCoordinateValue >= $half) {
return $relevantCoordinateValue;
}
return $relevantDimensionValue - ($relevantCoordinateValue + 1);
}
这里的条件很简单（我们要匹配的一个简单字符串），实际上它可能最适合作为回调，因此可以在每个网格元素上使用任何自定义逻辑。
这个实现可能会被优化，但我会在以后解决它。我只做了一些非常基本的优化。
整个东西都可以在线测试here。我使用了问题中心脏图像的数组表示，其中 w 和 r 代表白色和红色像素。
在二维平面中，我想检查相邻点直到满足条件。例如，在此图像中取一个红色像素 (x,y)。我想迭代以找到最接近所选红色像素的白色像素。
我原来的代码现在已经无关紧要了。
一个可能的解决方案是创建一个按距离排序的数组（在图像上给出）。然后，通过遍历这个数组，检查何时满足条件（例如，点是白色的）。但是，这个数组将是不确定的，而且有点矫枉过正。
// $x,$y is a given point
$array = array(
'0,0'=>0,
'-1,0'=>1,
'-1,-1'=>1.4
);
asort($array)
foreach($array as $a=>$b){
$c=explode(',',$a);
$x2=$c[0]; // x-axis distance from the given point
$y2=$c[1]; // y-axis distance from the given point
$x3=$x+$x2;
$y3=$y+$y2;
if( $x3,$y3 point is white) { break;}
}
$closest_distance=$b;
因此，我们需要在没有预定义的情况下构建循环 $array。
您可以创建一个坐标偏移列表，这些坐标偏移按它们到基点的距离排序。那么你的搜索函数写起来就简单多了：
maxRows,maxCols = 16,16
offsets = (offset for dx in range(maxRows) for dy in range(maxCols)
for offset in [(dx,dy),(dx,-dy),(-dx,dy),(-dx,-dy)])
offsets = sorted(offsets,key=lambda xy:xy[0]**2+xy[1]**2)[1:]
def closestPoint(pixels,row,col,value):
for dx,dy in offsets:
r,c = row+dy,col+dx
if r not in range(len(pixels)): continue
if c not in range(len(pixels[0])): continue
if pixels[r][c] == value: return r,c
return None,None
输出：
bitmap = [
[4, 2, 1, 2, 7, 3, 7, 2, 8, 7, 7, 8, 1, 7, 7, 6],
[6, 8, 3, 7, 1, 7, 8, 8, 8, 2, 4, 5, 8, 2, 5, 4],
[3, 2, 1, 6, 2, 7, 2, 2, 2, 2, 8, 2, 3, 5, 2, 7],
[8, 4, 4, 5, 2, 6, 7, 2, 6, 5, 6, 4, 5, 6, 7, 8],
[2, 6, 7, 2, 8, 6, 6, 8, 7, 6, 8, 6, 2, 8, 2, 8],
[6, 1, 7, 3, 7, 8, 8, 3, 0, 5, 6, 8, 4, 4, 5, 2],
[1, 5, 1, 7, 4, 5, 2, 2, 3, 7, 3, 3, 4, 2, 5, 4],
[1, 8, 5, 8, 1, 8, 2, 5, 4, 5, 4, 7, 2, 5, 7, 5],
[6, 6, 8, 6, 2, 6, 4, 1, 3, 4, 3, 6, 3, 6, 3, 7],
[6, 6, 5, 7, 3, 7, 3, 8, 1, 8, 2, 6, 3, 8, 2, 3],
[7, 5, 3, 1, 4, 3, 4, 3, 3, 5, 8, 5, 4, 4, 3, 3],
[2, 2, 1, 5, 1, 6, 6, 3, 8, 4, 1, 5, 2, 2, 1, 6],
[6, 2, 7, 1, 7, 4, 3, 5, 8, 6, 6, 3, 1, 2, 8, 5],
[1, 5, 1, 2, 2, 6, 3, 2, 3, 7, 4, 5, 6, 1, 8, 1],
[7, 6, 5, 2, 7, 2, 4, 8, 5, 1, 1, 4, 6, 1, 7, 7],
[2, 7, 3, 2, 1, 8, 6, 1, 6, 7, 4, 6, 7, 6, 2, 4]]
for p in range(1,9):
print(p,closestPoint(bitmap,5,8,p))
1 (8, 7)
2 (6, 7)
3 (6, 8)
4 (7, 8)
5 (5, 9)
6 (4, 9)
7 (4, 8)
8 (4, 7)
请注意，如果您要检查矩阵中的每个位置，使用邻近细化算法创建距离矩阵会更有效。
通过偏移达到最大距离将跳过 75% 的结果位置。如果您事先不知道最大大小，或者如果您想避免在偏移循环中无用的位置跳过，您可以保留一个大小位置字典，它映射到给定基数的有效位置：
posByDist = dict()
def getPositionsByDistance(height,width,r,c):
positions = posByDist.get((height,width,r,c),[])
if not positions:
offsets = ((dr*dr+dc*dc,dr,dc) for dx in range(height)
for dy in range(width)
for dr,dc in [(dx,dy),(dx,-dy),(-dx,dy),(-dx,-dy)]
if r+dr in range(height) and c+dc in range(width) )
positions = [(r+dr,c+dc) for _,dr,dc in sorted(offsets)]
posByDist[height,width,r,c] = positions
return positions
def closestPoint(pixels,row,col,value):
h,w = len(pixels),len(pixels[0])
return next(((r,c) for r,c in getPositionsByDistance(h,w,row,col)
if pixels[r][c] == value),(None,None))
这将只循环遍历有效位置，并将根据您实际遇到的尺寸和基本位置的需要动态创建和重复使用位置图。
即使这个问题已经有了一个可接受的答案，我还是想添加我的两个位（和一个 PHP 实现）和一个算法来满足 return 所有的额外请求最近的像素。
算法的描述（不知道这个有没有名字，我只是想了一个东西）：扩展到起点周围的外缘，并在这些像素之间寻找匹配项。如果找到 none，则移动到下一个边缘，依此类推，直到找到匹配项或者您已经触及所有边的边界（整个图像中没有匹配项）。可视化可能有助于理解；假设0为起点，那么1是第一个rim，2是第二个，3是第三个：
+---+---+---+---+---+---+---+---+---+
| | | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 2 | 2 | 2 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 1 | 1 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
| | | 3 | 2 | 2 | 2 | 2 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+
为了避免在到达远处边缘时必须处理大量元素，而不是扩展到所有边缘元素，我们首先扩展到最近的像素，然后是下一个最接近的像素，依此类推上，遵循这些规则：
- 任何边缘中最接近的像素是一个坐标保持不变而另一个坐标偏移边缘距离的像素。例如，在 rim 2 中，最接近的是
dx = 0 && dy = +/-2和dx = +/-2 && dy = 0. 的那些
- 任何边缘中下一个最接近的像素是之前未更改的坐标现在偏移 1 的像素，因此在我们的示例中
dx = +/-1 && dy = +/-2和dx = +/-2 && dy = +/-1。 - 我们不断将此变量偏移量增加 1，直到它等于固定偏移量（边缘距离，在我们的示例中为 2）。
这个逐渐扩展的视觉帮助（S 是起点，o 标记我们在给定步骤中获取的像素，- 标记我们已经检查过的像素） :
Step 1:
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
| | o | S | o | |
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Step 2:
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
| | - | S | - | |
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Step 3:
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
| | - | - | - | |
+---+---+---+---+---+
| o | - | S | - | o |
+---+---+---+---+---+
| | - | - | - | |
+---+---+---+---+---+
| | | o | | |
+---+---+---+---+---+
Step 4:
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
| - | - | S | - | - |
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
| | o | - | o | |
+---+---+---+---+---+
Step 5:
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
| - | - | - | - | - |
+---+---+---+---+---+
| - | - | S | - | - |
+---+---+---+---+---+
| - | - | - | - | - |
+---+---+---+---+---+
| o | - | - | - | o |
+---+---+---+---+---+
这个算法的优点是它实际上不需要任何距离计算，而且无论我们离起点有多远，一次处理的像素都不会超过 8 个。缺点是它的迭代量很大。它有利于找到接近的匹配项。
PHP实现（以左上角为根[0, 0]）：
/**
* Finds pixels with the lowest geometrical distance from given point (x, y) that match the criteria.
*/
function findGeometricallyClosestPixels(array $grid, int $x, int $y, string $criteria): array
{
// if grid is empty or we're out of bounds
if (empty($grid) || !isset($grid[$y]) || !isset($grid[0][$x])) {
return [];
}
if ($grid[$y][$x] === $criteria) {
return [[$x, $y]];
}
$result = [];
for ($offset = 1; $offset < calculateMaximumOffset($grid, $x, $y); $offset++) {
$result = array_merge($result, getClosestPixels($grid, $x, $y, $offset, $criteria));
if (!empty($result)) {
return $result;
}
for ($d = 1; $d <= $offset; $d++) {
$result = array_merge($result, getPixelsForNegativeYOffsets($grid, $x, $y, $offset, $d, $criteria));
$result = array_merge($result, getPixelsForPositiveYOffsets($grid, $x, $y, $offset, $d, $criteria));
if (!empty($result)) {
return $result;
}
}
}
return $result;
}
function getClosestPixels(array $grid, int $x, int $y, int $offset, string $criteria): array
{
$result = [];
if (isset($grid[$y][$x - $offset]) && $grid[$y][$x - $offset] === $criteria) {
$result[] = [$x - $offset, $y];
}
if (isset($grid[$y][$x + $offset]) && $grid[$y][$x + $offset] === $criteria) {
$result[] = [$x + $offset, $y];
}
if (isset($grid[$y - $offset][$x]) && $grid[$y - $offset][$x] === $criteria) {
$result[] = [$x, $y - $offset];
}
if (isset($grid[$y + $offset][$x]) && $grid[$y + $offset][$x] === $criteria) {
$result[] = [$x, $y + $offset];
}
return $result;
}
function getPixelsForNegativeYOffsets(array $grid, int $x, int $y, int $offset, int $d, string $criteria): array
{
if (!isset($grid[$y - $d])) {
return [];
}
$result = [];
if (isset($grid[$y - $d][$x - $offset]) && $grid[$y - $d][$x - $offset] === $criteria) {
$result[] = [$x - $offset, $y - $d];
}
if (isset($grid[$y - $d][$x + $offset]) && $grid[$y - $d][$x + $offset] === $criteria) {
$result[] = [$x + $offset, $y - $d];
}
if (!isset($grid[$y - $offset])) {
return $result;
}
if (isset($grid[$y - $offset][$x - $d]) && $grid[$y - $offset][$x - $d] === $criteria) {
$result[] = [$x - $d, $y - $offset];
}
if (isset($grid[$y - $offset][$x + $d]) && $grid[$y - $offset][$x + $d] === $criteria) {
$result[] = [$x + $d, $y - $offset];
}
return $result;
}
function getPixelsForPositiveYOffsets(array $grid, int $x, int $y, int $offset, int $d, string $criteria): array
{
if (!isset($grid[$y + $d])) {
return [];
}
$result = [];
if (isset($grid[$y + $d][$x + $offset]) && $grid[$y + $d][$x + $offset] === $criteria) {
$result[] = [$x + $offset, $y + $d];
}
if (isset($grid[$y + $d][$x - $offset]) && $grid[$y + $d][$x - $offset] === $criteria) {
$result[] = [$x - $offset, $y + $d];
}
if (!isset($grid[$y + $offset])) {
return $result;
}
if (isset($grid[$y + $offset][$x - $d]) && $grid[$y + $offset][$x - $d] === $criteria) {
$result[] = [$x - $d, $y + $offset];
}
if (isset($grid[$y + $offset][$x + $d]) && $grid[$y + $offset][$x + $d] === $criteria) {
$result[] = [$x + $d, $y + $offset];
}
return $result;
}
/**
* Calculates maximum offset needed to reach the edge of given grid for given starting point.
*
* Lowest possible offset is right in the middle of the greater grid dimension (width or height). Since grid starts
* at zero, if the point is positioned past the middle, then offset will equal its position. Otherwise, it will equal
* greater dimension minus its position increased by one (to compensate for the fact that dimensions are measured
* starting at 1, but positions start at 0).
*/
function calculateMaximumOffset(array $grid, int $x, int $y): int
{
$gridHeight = count($grid);
$gridWidth = count($grid[0]);
if ($gridHeight >= $gridWidth) {
$relevantDimensionValue = $gridHeight;
$relevantCoordinateValue = $y;
} else {
$relevantDimensionValue = $gridWidth;
$relevantCoordinateValue = $x;
}
$half = floor($relevantDimensionValue / 2);
if ($relevantCoordinateValue >= $half) {
return $relevantCoordinateValue;
}
return $relevantDimensionValue - ($relevantCoordinateValue + 1);
}
这里的条件很简单（我们要匹配的一个简单字符串），实际上它可能最适合作为回调，因此可以在每个网格元素上使用任何自定义逻辑。
这个实现可能会被优化，但我会在以后解决它。我只做了一些非常基本的优化。
整个东西都可以在线测试here。我使用了问题中心脏图像的数组表示，其中 w 和 r 代表白色和红色像素。