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

Laravel

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

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

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

这里面的 xy是每一个矩阵点的坐标

然后组成图片这样的排列

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

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

里面的 xy是每一个区域块的起始坐标,例如最大的区域块需要的结果是 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
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
张闯Json
最佳答案
<?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

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

4年前 评论
leo

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

4年前 评论
leo
<?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年前 评论

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

4年前 评论
lmaster

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

4年前 评论
张闯Json
<?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
<?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年前 评论

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