logo标签列表

寻找矩形的算法

c#algorithm
5

I have the following code:

int width = 10;
int height = 7;
bool[,] array1 = new bool[width, height];


string values = 
    "1100000000" +
    "1100000011" +
    "0001100011" +
    "0001100000" +
    "0001110000" +
    "0000000110" +
    "0000000110";

for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)
    {
        array1[x, y] = (values[x + y * width] == '1');
    }
}

我正在寻找一种算法，可以提取出存在1的范围。通过这个数据，我们可以得到四边形：(0,0,2,2), (8,1,2,2), (3,2,3,3), (7,5,2,2)，四边形的顺序无关紧要！但我不知道如何实现，请问有什么指导吗？在阅读了Rusty Weber的回答后，我想到了以下解决方案：
private static List<Rectangle> GetRectangles(bool[,] array)
{
    List<Rectangle> rectangles = new List<Rectangle>();
    for (int x = 0; x < array.GetLength(0); x++)
    {
        for (int y = 0; y < array.GetLength(1); y++)
        {
            if (array[x, y])
            {
                rectangles.Add(GetRectangle(array, new Point(x, y)));
            }
        }
    }
    return rectangles;
}



static Rectangle GetRectangle(bool[,] array, Point startLocation)
{
    int maxX = int.MinValue;
    int minX = int.MaxValue;
    int maxY = int.MinValue;
    int minY = int.MaxValue;
    HashSet<Point> visitedLocations = new HashSet<Point>();
    Stack<Point> pointsToGo = new Stack<Point>();
    Point location;
    pointsToGo.Push(startLocation);
    while (pointsToGo.Count > 0)
    {
        location = pointsToGo.Pop();

        if (!location.X.IsBetween(0, array.GetLength(0) - 1))
            continue;
        if (!location.Y.IsBetween(0, array.GetLength(1) - 1))
            continue;
        if (!array[location.X, location.Y])
            continue;
        if (visitedLocations.Contains(location))
            continue;
        visitedLocations.Add(location);

        pointsToGo.Push(new Point(location.X + 1, location.Y));
        pointsToGo.Push(new Point(location.X, location.Y + 1));
        pointsToGo.Push(new Point(location.X - 1, location.Y));
        pointsToGo.Push(new Point(location.X, location.Y - 1));
    }

    foreach (Point location2 in visitedLocations)
    {
        array[location2.X, location2.Y] = false;
        if (location2.X > maxX)
            maxX = location2.X;
        if (location2.X < minX)
            minX = location2.X;
        if (location2.Y > maxY)
            maxY = location2.Y;
        if (location2.Y < minY)
            minY = location2.Y;
    }

    return new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1);
}

public static bool IsBetween<T>(this T item, T start, T end)
{
    return Comparer<T>.Default.Compare(item, start) >= 0
        && Comparer<T>.Default.Compare(item, end) <= 0;
}
1
你的数值看起来有点不对。为了得到3,2,3,3，我认为你需要在5,2和5,3处放置1。我会尝试设计一个算法。 - itsme86
@itsme86 和 Kenny，这是故意的，我想在矩形中包含那两个零... - Peter
（x，y，宽度，高度），数组从0开始！ - Peter
没有任何限制。 - Peter
@Petoj 好的，那么每个1就输出一个1x1的矩形。或者你可以稍微改进一下，通过贪心地扩展每个尝试放置的矩形来实现。这非常不优化，但如果你没有任何限制的话... - harold
显示剩余8条评论
3个回答
2

留言 :: 如果您更好地定义了坐标，可能会有助于我回答您的问题。(0,0,2,2) 不完全是笛卡尔坐标系，可能需要一些解释。这是左上角，然后是宽度吗？

好的。在我看来，从图形中提取所有可能的矩形最容易编程的方式是使用一个递归定义的方法，按特定方向搜索对称矩形模式。但这可能会变得非常慢，所以希望速度不是您的约束条件。看代码的风格，我会说这是递归或动态规划的学校作业。

以下是类似于下面伪代码的内容：

` 

for i in width  
{  
for j in height  
{  
if(point[i,j] == 1)  
{  
       potentials = searh_in_direction(i,j,graph,width,height,RIGHT,[[i,j]] )  
     listOfAllRects.append(potentials)  
}  
}  
}
list_of_rectangle searh_in_direction(i,j,graph,width,height,direction, listofpoints )  
{  
  nextdirection = direction.nextdirection; //Right -> down -> left-> up 


  //DEVELOP METHOD FOR RECURSION HERE THAT RETURNS ALL SETS OF 4 POINTS THAT
  for every point in the direction of travel
  if the point is the origional point and we have 4 points including the point we are looking at, we have a rectangle and we need to return
  if point on direction of travel is a one travel on the next direction
  posiblerects.append(searh_in_direction(i,j,graph,width,height,nextdirection , listofpoints.append(currentpoint)))

//after all points in direction have bee searched
return posiblerects.
}

我知道这段代码可能会让人很困惑，但这就是你作为递归元素所需要的要点。我还要注意的是，我已经看到了这段代码中的几个错误，但我已经用完了我说过的15分钟，所以你可能需要自己找出它们。

抱歉，(x，y，width，height) 和数组是从0开始的！ - Peter
4
我已经将您的回答变成了主要问题的评论，您可能希望在收到许多负投票之前删除此答案。 - hatchet - done with SOverflow
2
这将为您提供您所寻找的相同结果：
static void Main(string[] args)
{
    string values =
        "1100000000" +
        "1100000011" +
        "0001100011" +
        "0001100000" +
        "0001110000" +
        "0000000110" +
        "0000000110";

    int width = 10;
    int height = 7;
    bool[,] array = new bool[width, height];

    for (int x = 0; x < width; x++)
        for (int y = 0; y < height; y++)
            array[x, y] = (values[x + y * width] == '1');

    List<Rectangle> rectangles = new List<Rectangle>();

    for (int x = 0; x < width; ++x)
    {
        for (int y = 0; y < height; ++y)
        {
            if (array[x, y] && !Used(rectangles, x, y))
            {
                int rHeight = 1;
                for (int rX = x + 1; rX < width && array[rX, y] && !Used(rectangles, rX, y); ++rX)
                    for (int rY = y + 1; rY < height && array[rX, rY] && !Used(rectangles, rX, rY); ++rY)
                        if (rY - y >= rHeight)
                            rHeight = rY - y + 1;

                int rWidth = 1;
                for (int rY = y + 1; rY < height && rY - y <= rHeight && array[x, rY] && !Used(rectangles, x, rY); ++rY)
                    for (int rX = x + 1; rX < width && array[rX, rY] && !Used(rectangles, rX, rY); ++rX)
                        if (rX - x >= rWidth)
                            rWidth = rX - x + 1;

                rectangles.Add(new Rectangle(x, y, rWidth, rHeight));
            }
        }
    }

    foreach (Rectangle rect in rectangles)
        Console.WriteLine(rect);
}

private static bool Used(IEnumerable<Rectangle> rectangles, int x, int y)
{
    return rectangles.Any(r => r.Contains(x, y));
}

我创建了一个特定的矩形结构体，因为我没有引用System.Drawing，但是你可以将System.Drawing.Point传递给System.Drawing.Rectangle.Contains()，并获得相同的结果。

此外，请注意您的数组宽度实际上应为10，而您的索引计算有误。您应该将y乘以宽度，而不是高度。

谢谢你的工作，但我已经找到了那些漏洞，并且我也成功地解决了问题，非常感谢！！！ - Peter
1

从问题中并不清楚您是否真的想要完全覆盖1的矩形，还是想要包含零但用相对较少的矩形完全覆盖所有1的边界体积。

假设您想要矩形覆盖1，并且您不需要完美的解决方案：

  1. 创建一个数组的临时副本。
  2. 遍历临时副本以查找1
  3. 当您遇到1时，开始一个新的矩形，它从该位置开始为1x1，偏移（例如仅覆盖该1）
  4. 只要下一个单元格中有1，就向右扩展该矩形
  5. 只要下面的行与当前矩形的宽度匹配的1，就向下扩展该矩形。
  6. 一旦无法再向下扩展，就发出该矩形，并清除临时副本中由该矩形覆盖的所有1
  7. 继续扫描1，从当前矩形的右上角直接开始的单元格开始。

这将产生一个不错的覆盖-但绝不是理想的。如果您需要完美的覆盖-例如保证最小数量的矩形，则更难。

我认为，如果你逐步迭代步骤4和5，而不是尽可能一次性完成所有步骤，你可能会得到稍微更好的结果。 - harold
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接