7

以下は、今日遭遇した視覚的な問題です。ここでの問題は単純に、絵の中に正方形がいくつあるかということです。

コードを使用してこのような問題を解決するにはどうすればよいですか? さらに、実際の写真が加工されていない場合、どのようにモデリングしますか?

正方形のパズル

PS: 実際の解像度では、正方形と見なすことができるものを定義するルールが必要になると思います。辺の長さが等しく、囲んでいる正方形内に収まる限り、任意の数のセグメントで構成できるということです。ただし、どのように位置を表すことができるかわかりません。

4

4 に答える 4

1

最も簡単な方法は、すべての頂点をループして、幅1、次に幅2、3などの正方形の左上の頂点になり得るかどうかを確認することです。

于 2012-07-25T03:41:17.253 に答える
1

エンコーディング: あなたが持っているのはネットワークです。これを、離散的な 2 次元空間に位置するノードを接続するネットワークとしてエンコードします。

この質問は、次のプロパティを満たすパスの数を数えることを実際に求めています。

  1. 3ターンあります
  2. そのような各ターンの間の長さは等しい
  3. パスの開始と終了は同じです。

この場合のターンは、(a) 前の移動によって y 座標が変化した場合、この移動によって x 座標が変化する場合。または (b) 前の移動によって x 座標が変更された場合、この移動によって y 座標が変更されます。

プロセスの追跡について: このページで私が見た最良の提案は、単純に各ノードを反復処理し、そのようなノードごとに正方形のすべての可能なサイズをチェックすることです。これにより、これ以上追跡する必要がなくなります。

よりスマートな方法がある場合、パスが常に左手または常に右手である限り、各正方形は開始頂点と辺の長さによって一意に識別されます。

于 2012-07-25T01:17:04.950 に答える
1

これを行列としてモデル化できる場合、必要な情報は頂点の位置だけです。次に、頂点ごとに同じ行のすべての頂点をチェックし、見つかった頂点ごとにそれらの列をチェックします。次に、処理された頂点を削除します。列ごとに同じことを行います。最悪の場合の複雑さは n! (?)

明確にするためにコードを追加しました。 

public class SqFinder {
        int calculateSquares(int[][] vertices, int n) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (vertices[i][j] == 1) {
                        for (int k = 1; k < n-j; k++) {
                            if (i + k < n && vertices[i][j+k] == 1 && vertices[i + k][j] == 1 && vertices[i + k][j + k] == 1)
                                count++;
                        }
                    }
                    vertices[i][j] =0;
                }
            }
            return count;
        }

        public static void main(String[] args) {
            SqFinder a = new SqFinder();
    //      int [][] test = {{1,1,1,1},{1,1,1,1},{1,1,1,1},{1,1,1,1}};
            int [][] test = {{1,1,1},{1,1,1},{1,1,1}};
            System.out.println(a.calculateSquares(test, 3));
        }
    }
于 2012-07-25T02:10:53.487 に答える
0

このようなものはそれを行うべきです:

int line_width = 1; //the width of the square line
int squares = 0;
for (int x = 0; x < width; ++x)
{
    for (int y = 0; y < height; ++y)
    {
        for (int size = line_width; x + size < width && y + size < height; ++x)
        {
            if (valid_square_at(x, y, x + size, y + size, line_width))
            {
                ++squares;
            }
        }
    }
}
return squares;

bool valid_square_at(x_0, y_0, x_1, y_1, width) 
{
    return valid_line(x_0, y_0, x_0_ x_1, width)
        && valid_line(x_0, y_0, x_1_ x_0, width)
        && valid_line(x_0, y_1, x_1_ x_1, width)
        && valid_line(x_1, y_0, x_1_ x_1, width);
}

bool valid_line(x_0, y_0, x_1, y_1, width) 
{
    //check that all pixel in that line are black...
}

基本的に、画像内のすべての点について、そのサイズの正方形がそのピクセルから始まるかどうか、可能なすべての正方形のサイズをチェックします。正方形はすべて境界線に「整列」しているため、これは非常に簡単です...問題は、そうでない場合です...

于 2012-07-25T02:05:34.427 に答える