如何在一个矩阵点图中计算一个区域内的宽高（这个标题真没有办法说清楚）

Laravel

图片是一个8*8的矩阵图

请求后台接口会返回一个二维数组，数组元素是

[
    [
        'id' => 1,
        'x' => 0,
        'y' => 0,
        'state' => 0
    ],
    [
        'id' => 2
        'x' => 1,
        'y' => 0,
        'state' => 1
    ],
]

这里面的 x ， y是每一个矩阵点的坐标

然后组成图片这样的排列

现在需要把请求的数据转换为

[
    [
        'x' => 0,
        'y' => 0,
        'size' => 4
        'state' => 1
    ],
    [
        'x' => 3
        'y' => 3
        'size' =>  3
        'state' => 2
    ],
]

里面的 x ， y是每一个区域块的起始坐标，例如最大的区域块需要的结果是 x = 0, y = 0, size = 4, state = 1
虽然 0-0不属于这个区域块的，但是这个区块的起点是0-0

而最长的那个区域块需要的结果是 x = 6 y = 0, size = 6 state = 1

size 其实就是 maxX - minX 和 maxY - minY 这 2 个值 谁大谁就是 size

所以求 size 前需要把 maxX minX 和 maxY minY 求出来

目前已经有思路，验证中

这个周末一直在研究这个
可惜在下实在是没有办法搞定这个需求
请求大家给一些思路

算法坐标

附言 1 · 4年前

如果1和2是贴在一起的，那么是2个区域块

附言 2 · 4年前

我尝试过的思路，计算每一个区块内元素可以延伸的最长宽度和高度，然后宽高最大的那个就是size，
结果我没有办法解决怎么区分每一个区域

附言 3 · 4年前

尝试使用递归来区分区域块，但是执行的效率太低了

附言 4 · 4年前

= =# 自问自答了，代码已经上传

附言 5 · 4年前

简单说一下我的解题逻辑。

坐标数组，key 的范围是 [0-63], 和 xy 的关系
key = x * 8 + y

直接循环坐标数组，找到第一个state != 0 的数组作为基点，然后从它上面的元素开始，顺时针判断这些元素块，但是不找到全部，只要找到一个元素块，就把之前的基点 state = 0 ，基点更改为新的元素块，然后就一直找下去，最后周围都没有一个元素块的时候，基点把自己的 state = 0

在寻找的过程中，minx miny maxx maxy 都在不断的进行对比，最终确定这个区域的四个坐标值，然后计算起点坐标宽度和高度

有这四个坐标值以后直接清空这个区域内的所有同区域元素块

递归重新寻找下一个区域的基点

目前这套逻辑基本满足需求

但是还是有很多需要优化的地方

张闯Json

24 声望

前端 @ 歌尔股份

小黄鸭编程法则

3 人点赞

你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程，JWT 概念及使用和 API 开发相关的进阶知识。

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

推荐文章：

更多推荐...

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 23 / 3 |

博客

PHP实现汉诺塔算法 21 / 9 |

博客

PHP使用动态规划实现最优红包组合 33 / 5 |

博客

PHP拆红包算法 12 / 8 |

博客

我的 LeetCode 15 / 5 |

博客

PHP 实现 HTTP 表单请求服务器 45 / 7 |

张闯Json

24 声望 / 前端 @ 歌尔股份

最佳答案

<?php

namespace App\Http\Controllers;

use Laravel\Lumen\Routing\Controller as BaseController;

class Controller extends BaseController
{
    public $minX = 0;
    public $minY = 0;
    public $maxX = 0;
    public $maxY = 0;
    // 基点
    public $basicPoint = [];
    public $state = 0;

    // 判断
    // 如果基点周围有相同区域的元素 则按照顺时针判断 并且返回第一个元素
    // 新的元素 x y 与 maxX maxY 进行对比 取大的那个值
    // 新的数组取代旧基点成为新的基点
    public function handleNextElement($coordinateArr)
    {
        $item = [];
        $result = null;

        foreach ($coordinateArr as $key => $value) {
            $result = $this->handleJudgeNextEleIsAlike($value);
            if ($result === 1) {
                // 把基点状态设置为0 防止递归时候出BUG
                $key = $this->basicPoint['x'] * 8 + $this->basicPoint['y'];
                $this->model[$key]['state'] = 0;

                $this->basicPoint = $value;

                $this->maxX < $value['x'] ? $this->maxX = $value['x'] : $this->maxX;
                $this->maxY < $value['y'] ? $this->maxY = $value['y'] : $this->maxY;
                $this->minX > $value['x'] ? $this->minX = $value['x'] : $this->minX;
                $this->minY > $value['y'] ? $this->minY = $value['y'] : $this->minY;

                $item = [
                    'maxX' => $this->maxX,
                    'minX' => $this->minX,
                    'maxY' => $this->maxY,
                    'minY' => $this->minY,
                    'result' => $result,
                    'basicPoint' => $this->basicPoint
                ];

                return $item;
            }
        }

        $item = [
            'maxX' => $this->maxX,
            'minX' => $this->minX,
            'maxY' => $this->maxY,
            'minY' => $this->minY,
            'result' => $result,
            'basicPoint' => $this->basicPoint
        ];

        return $item;
    }

    // $item 元素的相邻元素 判断是不是同一个区域
    // $item[x] 相邻元素的 x 坐标
    // $item[y] 相邻元素的 y 坐标
    // $item[state] 原元素的 state 值 用于判断相邻元素的 state 是否和原元素相同
    public function handleJudgeNextEleIsAlike($item) {
        // 如果坐标有小于 0 的值 直接返回 0
        if ($item['x'] < 0 || $item['y'] < 0) return 0;

        $key = $item['x'] * 8 + $item['y'];
        $result = $this->model[$key];
        if ($result['state'] === $item['state']) {
            return 1;
        } else {
            return 0;
        }
    }
}

4年前评论

讨论数量: 7

Wi1dcard

管理员 2.1k 声望

好久之前学的算法，现在忘的差不多了；不过这个问题「似乎」是「最小外接矩形」问题的一个简化版，可以 Google 相关资料。

4年前评论

leo

管理员 4.7k 声望 / Backend Manager @ RightCapital

这个问题的本质其实很简单，就是聚合 连在一起的格子，想象一下你图中左下角那一片值为 1 的格子，如果你有一个这些格子的数组，那么你需要的结果就是这批格子中 x、y 值分别最大和最小的值。

4年前评论

leo

管理员 4.7k 声望 / Backend Manager @ RightCapital

<?php
$src = [
    ['x' => 0, 'y' => 0, 'state' => 0],
    ['x' => 0, 'y' => 1, 'state' => 1],
    ['x' => 0, 'y' => 2, 'state' => 1],
    ['x' => 0, 'y' => 3, 'state' => 0],
    ['x' => 0, 'y' => 4, 'state' => 0],
    ['x' => 0, 'y' => 5, 'state' => 0],
    ['x' => 0, 'y' => 6, 'state' => 0],
    ['x' => 0, 'y' => 7, 'state' => 0],
    ['x' => 1, 'y' => 0, 'state' => 1],
    ['x' => 1, 'y' => 1, 'state' => 1],
    ['x' => 1, 'y' => 2, 'state' => 1],
    ['x' => 1, 'y' => 3, 'state' => 1],
    ['x' => 1, 'y' => 4, 'state' => 0],
    ['x' => 1, 'y' => 5, 'state' => 2],
    ['x' => 1, 'y' => 6, 'state' => 2],
    ['x' => 1, 'y' => 7, 'state' => 2],
    ['x' => 2, 'y' => 0, 'state' => 1],
    ['x' => 2, 'y' => 1, 'state' => 1],
    ['x' => 2, 'y' => 2, 'state' => 1],
    ['x' => 2, 'y' => 3, 'state' => 1],
    ['x' => 2, 'y' => 4, 'state' => 0],
    ['x' => 2, 'y' => 5, 'state' => 2],
    ['x' => 2, 'y' => 6, 'state' => 0],
    ['x' => 2, 'y' => 7, 'state' => 0],
    ['x' => 3, 'y' => 0, 'state' => 0],
    ['x' => 3, 'y' => 1, 'state' => 1],
    ['x' => 3, 'y' => 2, 'state' => 1],
    ['x' => 3, 'y' => 3, 'state' => 0],
    ['x' => 3, 'y' => 4, 'state' => 0],
    ['x' => 3, 'y' => 5, 'state' => 0],
    ['x' => 3, 'y' => 6, 'state' => 0],
    ['x' => 3, 'y' => 7, 'state' => 0],
    ['x' => 4, 'y' => 0, 'state' => 0],
    ['x' => 4, 'y' => 1, 'state' => 0],
    ['x' => 4, 'y' => 2, 'state' => 0],
    ['x' => 4, 'y' => 3, 'state' => 0],
    ['x' => 4, 'y' => 4, 'state' => 0],
    ['x' => 4, 'y' => 5, 'state' => 2],
    ['x' => 4, 'y' => 6, 'state' => 2],
    ['x' => 4, 'y' => 7, 'state' => 0],
    ['x' => 5, 'y' => 0, 'state' => 0],
    ['x' => 5, 'y' => 1, 'state' => 0],
    ['x' => 5, 'y' => 2, 'state' => 0],
    ['x' => 5, 'y' => 3, 'state' => 0],
    ['x' => 5, 'y' => 4, 'state' => 0],
    ['x' => 5, 'y' => 5, 'state' => 2],
    ['x' => 5, 'y' => 6, 'state' => 2],
    ['x' => 5, 'y' => 7, 'state' => 0],
    ['x' => 6, 'y' => 0, 'state' => 1],
    ['x' => 6, 'y' => 1, 'state' => 1],
    ['x' => 6, 'y' => 2, 'state' => 1],
    ['x' => 6, 'y' => 3, 'state' => 0],
    ['x' => 6, 'y' => 4, 'state' => 0],
    ['x' => 6, 'y' => 5, 'state' => 2],
    ['x' => 6, 'y' => 6, 'state' => 2],
    ['x' => 6, 'y' => 7, 'state' => 0],
    ['x' => 7, 'y' => 0, 'state' => 0],
    ['x' => 7, 'y' => 1, 'state' => 0],
    ['x' => 7, 'y' => 2, 'state' => 1],
    ['x' => 7, 'y' => 3, 'state' => 1],
    ['x' => 7, 'y' => 4, 'state' => 1],
    ['x' => 7, 'y' => 5, 'state' => 1],
    ['x' => 7, 'y' => 6, 'state' => 0],
    ['x' => 7, 'y' => 7, 'state' => 0],
];

$states  = [];
$visited = [];
$maxX    = 0;
$maxY    = 0;

foreach ($src as $block) {
    ['x' => $x, 'y' => $y, 'state' => $state] = $block;
    if (!isset($states[$x])) {
        $states[$x]  = [];
        $visited[$x] = [];
    }
    $states[$x][$y]  = $block['state'];
    $visited[$x][$y] = false;
    if ($x > $maxX) {
        $maxX = $x;
    }
    if ($y > $maxY) {
        $maxY = $y;
    }
}

function find_adjacent_blocks(int $x, int $y): array
{
    global $states, $maxX, $maxY, $visited;
    $state = $states[$x][$y];
    if ($state === 0) {
        return [];
    }
    $result         = [];
    $checkingBlocks = [];
    if ($x > 0) {
        $checkingBlocks[] = ['x' => $x - 1, 'y' => $y, 'state' => $states[$x - 1][$y]];
    }
    if ($x < $maxX) {
        $checkingBlocks[] = ['x' => $x + 1, 'y' => $y, 'state' => $states[$x + 1][$y]];
    }
    if ($y > 0) {
        $checkingBlocks[] = ['x' => $x, 'y' => $y - 1, 'state' => $states[$x][$y - 1]];
    }
    if ($y < $maxY) {
        $checkingBlocks[] = ['x' => $x, 'y' => $y + 1, 'state' => $states[$x][$y + 1]];
    }

    foreach ($checkingBlocks as $block) {
        ['x' => $checkingX, 'y' => $checkingY, 'state' => $checkingState] = $block;
        if ($checkingState !== $state || $visited[$checkingX][$checkingY] === true) {
            continue;
        }
        $visited[$checkingX][$checkingY] = true;
        $result[] = $block;
        $result += find_adjacent_blocks($checkingX, $checkingY);
    }

    return $result;
}

$groupedBlocks = [];

foreach ($src as $index => $block) {
    if ($visited[$block['x']][$block['y']] !== false) {
        continue;
    }
    $blocks = find_adjacent_blocks($block['x'], $block['y']);
    if (count($blocks) > 0) {
        $groupedBlocks[] = $blocks;
    }
}

var_dump(count($groupedBlocks));

4年前评论

易水

课程读者 203 声望

能否把题目描述得清楚一点，我还没理解size是指什么 :joy:

4年前评论

lmaster

课程读者 245 声望 / phper @ 泛爱之家

@张闯Json 个人觉得你应该修改下你的问题，把这个 size 加进去，我就奇怪这个 size 是什么，最后在回复里面才发现

4年前评论

张闯Json

24 声望 / 前端 @ 歌尔股份

<?php

namespace App\Http\Controllers;

use Illuminate\Support\Facades\DB;
use App\Place;

class WenduController extends Controller
{

    // 原始坐标数组
    public $model = null;

    // 构造函数 从数据库中获取初始数据
    public function __construct()
    {
        $this->model = Place::get()->toArray();
    }

    // 代码的起点
    public function index() {
        $item = $this->initFindStartPoint();
        return $item;
    }

    // 寻找矩阵内区域的起点坐标信息
    // 每一次执行都会重新寻找一个矩阵内的区块
    // 提供一个新的区块坐标起点给 下一步方法后 下一步方法需要把 state 设置为 0 已经对比过的区块
    public function initFindStartPoint() {
        foreach ($this->model as $index => $item) {
            if ($item['state'] !== 0) {
                $this->basicPoint = [
                    'x' => $item['x'],
                    'y' => $item['y'],
                    'state' => $item['state']
                ];
                $this->state = $item['state'];
                break;
            }
        }

        return $this->handleCalculationRegion($this->basicPoint);
    }

    // 参数是不停更换的基点坐标
    public function handleCalculationRegion($item) {
        $res = $this->handleCalculation($item);

        if ($res['result'] === 0) {
            $item = [
                'maxX' => $this->maxX,
                'minX' => $this->minX,
                'maxY' => $this->maxY,
                'minY' => $this->minY,
                'basicPoint' => $this->basicPoint
            ];
            return $item;
        }

        return $this->handleCalculationRegion($res['basicPoint']);
    }

    // 主要的判断体
    public function handleCalculation($item) {
        $x = $item['x'];
        $y = $item['y'];
        $stete = $item['state'];

        // 上 元素坐标
        $nextTop = [ 'x' => $x, 'y' => $y + 1, 'state' => $stete ];
        // 右上 元素坐标
        $nextTopRight = [ 'x' => $x + 1, 'y' => $y + 1, 'state' => $stete ];
        // 右 元素坐标
        $nextRight = [ 'x' => $x + 1, 'y' => $y, 'state' => $stete ];
        // 右下 元素坐标
        $nextBottomRight = [ 'x' => $x + 1, 'y' => $y - 1, 'state' => $stete ];
        // 下 元素坐标
        $nextBottom = [ 'x' => $x, 'y' => $y - 1, 'state' => $stete ];
        // 左下 元素坐标
        $nextLeftBottom = [ 'x' => $x - 1, 'y' => $y - 1, 'state' => $stete ];
        // 左 元素坐标
        $nextLeft = [ 'x' => $x - 1, 'y' => $y, 'state' => $stete ];
        // 左上 元素坐标
        $nextLeftTop = [ 'x' => $x - 1, 'y' => $y + 1, 'state' => $stete ];

        $coordinateArr = [
            $nextTop,
            $nextTopRight,
            $nextRight,
            $nextBottomRight,
            $nextBottom,
            $nextLeftBottom,
            $nextLeft,
            $nextLeftTop
        ];

        return $this->handleNextElement($coordinateArr);
    }
}

4年前评论

张闯Json

24 声望 / 前端 @ 歌尔股份

<?php

namespace App\Http\Controllers;

use Laravel\Lumen\Routing\Controller as BaseController;

class Controller extends BaseController
{
    public $minX = 0;
    public $minY = 0;
    public $maxX = 0;
    public $maxY = 0;
    // 基点
    public $basicPoint = [];
    public $state = 0;

    // 判断
    // 如果基点周围有相同区域的元素 则按照顺时针判断 并且返回第一个元素
    // 新的元素 x y 与 maxX maxY 进行对比 取大的那个值
    // 新的数组取代旧基点成为新的基点
    public function handleNextElement($coordinateArr)
    {
        $item = [];
        $result = null;

        foreach ($coordinateArr as $key => $value) {
            $result = $this->handleJudgeNextEleIsAlike($value);
            if ($result === 1) {
                // 把基点状态设置为0 防止递归时候出BUG
                $key = $this->basicPoint['x'] * 8 + $this->basicPoint['y'];
                $this->model[$key]['state'] = 0;

                $this->basicPoint = $value;

                $this->maxX < $value['x'] ? $this->maxX = $value['x'] : $this->maxX;
                $this->maxY < $value['y'] ? $this->maxY = $value['y'] : $this->maxY;
                $this->minX > $value['x'] ? $this->minX = $value['x'] : $this->minX;
                $this->minY > $value['y'] ? $this->minY = $value['y'] : $this->minY;

                $item = [
                    'maxX' => $this->maxX,
                    'minX' => $this->minX,
                    'maxY' => $this->maxY,
                    'minY' => $this->minY,
                    'result' => $result,
                    'basicPoint' => $this->basicPoint
                ];

                return $item;
            }
        }

        $item = [
            'maxX' => $this->maxX,
            'minX' => $this->minX,
            'maxY' => $this->maxY,
            'minY' => $this->minY,
            'result' => $result,
            'basicPoint' => $this->basicPoint
        ];

        return $item;
    }

    // $item 元素的相邻元素 判断是不是同一个区域
    // $item[x] 相邻元素的 x 坐标
    // $item[y] 相邻元素的 y 坐标
    // $item[state] 原元素的 state 值 用于判断相邻元素的 state 是否和原元素相同
    public function handleJudgeNextEleIsAlike($item) {
        // 如果坐标有小于 0 的值 直接返回 0
        if ($item['x'] < 0 || $item['y'] < 0) return 0;

        $key = $item['x'] * 8 + $item['y'];
        $result = $this->model[$key];
        if ($result['state'] === $item['state']) {
            return 1;
        } else {
            return 0;
        }
    }
}

4年前评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

如何在一个矩阵点图中计算一个区域内的宽高（这个标题真没有办法说清楚）

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

如何在一个矩阵点图中计算一个区域内的宽高（这个标题真没有办法说清楚）

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录