5

次のコードがあります。

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

3 に答える 3

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 を参照しなかったのでアドホックな Rectangle 構造体を作成しましたが、System.Drawing.Point を System.Drawing.Rectangle.Contains() に渡して同じ結果を得ることができます。

また、配列の幅は実際には 10 である必要があり、インデックスの計算が間違っていることに注意してください。y に高さではなく幅を掛ける必要があります。

于 2012-06-26T20:15:31.503 に答える
2

コメント :: より適切な座標があれば、質問に答えるのに役立つかもしれません。(0,0,2,2) は正確にはデカルトではなく、説明が必要な場合があります。これは左上隅の後に幅がありますか?

Ok。少なくとも私の意見では、グラフから可能なすべての四角形を抽出する最も簡単なプログラム方法は、対称的な四角形パターンを特定の方向で検索する再帰的に定義されたメソッドを持つことです。ただし、これは非常に遅くなる可能性があるため、速度が制約にならないことを願っています. コードのスタイルを見ると、これは再帰または動的プログラミングの学校の課題であると言えます。

次の疑似コードの行に沿ったもの

` 

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 分を使い果たしたので、自分でそれらを選択する必要があるかもしれません.

于 2012-06-26T17:06:30.133 に答える
1

1 を正確にカバーする長方形が本当に必要なのか、それともゼロを含むことができるバウンディング ボリュームが必要なのか、合理的に少数の長方形ですべての 1 をカバーするのかは、質問からは明らかではありません。

四角形で 1 をカバーする必要があり、完全な解決策は必要ないとします。

  1. 配列の一時コピーを作成します。
  2. 1 を探して一時的に繰り返します
  3. 1 をヒットしたら、1x1 で始まる新しい四角形を開始し、その位置にオフセットします (たとえば、その 1 だけをカバーします)。
  4. 次のセルに 1 がある限り、その長方形を右に拡張します
  5. 下の行に現在の四角形の幅に一致する 1 がある限り、その四角形を下に展開します。
  6. これ以上下に展開できなくなったら、その四角形を放出し、その四角形で覆われているすべての 1 を一時的にクリアします。
  7. 現在の長方形の右上隅の直後のセルから 1 のスキャンを続けます。

これにより、まともなカバーが作成されますが、決して理想的ではありません. 完璧なカバーが必要な場合、たとえば保証された最小数の長方形が必要な場合は、さらに難しくなります。

于 2012-06-26T18:01:44.157 に答える