代码之家  ›  专栏  ›  技术社区  ›  JustAMartin

如何找到在较小矩形的两侧留有最多可用空间的矩形?

  •  0
  • JustAMartin  · 技术社区  · 4 年前

    我试图为我的软件找出一个合适的算法,但我找不到任何相关的“教科书解决方案”。我将任务简化为以下核心问题。

    给定矩形区域的选择,我需要找到一个已知适合所有区域的较小矩形的所有边上同时留下最大空间的区域。

    鉴于: 矩形: 长度=100,宽度=200

    区域(将始终预选为大于矩形):

    1. 长度=100,宽度=200
    2. 长度=101,宽度=201
    3. 长度=200,宽度=1000

    找到最合适的选择的算法应该是什么?

    对于伪代码或任何类似C语言或Python的代码,或者指向某个著名算法的指针,我们都会心存感激。

    这些数字是为这个测试示例挑选的。在现实生活中,所有数字都可以是用户输入的任何数字。

    0 回复  |  直到 4 年前
        1
  •  1
  •   user12069894 user12069894    4 年前

    如果我正确理解您的问题,这将是一个解决方案(c++),但我没有测试它:

    struct Rectangle
    {
        size_t x, y;
    };
    
    //returns first index which fits your condition
    int alg(Rectangle a, Rectangle *others, size_t othersLen)
    {
        unsigned int biggestIndex = 0;
        size_t biggest = 0;
        for (int i = 0; i < othersLen; i++)
        {
            size_t diffX = others[i].x - a.x;
            size_t diffY = others[i].y - a.y;
            size_t size = diffX > diffY ? diffY : diffX;
            if (size > biggest)
            {
                biggest = size;
                biggestIndex = i;
            }
        }
        return biggestIndex;
    }
    

    编辑:仅当其他矩形大于给定矩形时才起作用,因为它不会产生负差异。