c# - 查找矩形的算法

我有以下代码:

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;
}

最佳答案

评论::如果您定义的坐标更好，这可能会帮助我回答您的问题。 (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分钟用完了，所以您可能必须自己挑选出来。

关于c# - 查找矩形的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11212309/