Search for the number of possible squares in this image

Question

Below is the visual problem I encountered today. The question here is how many squares are in the picture.

How would you decide to solve something like this though the code? In addition, if the actual image is not processed, how are you going to model it?

PS: I feel that actual resolution requires a rule to determine what can be considered a square. Something like that the sides are equal in length and can consist of any number of segments if they fit into a closed square. I'm not sure how you could position a position.

Answer 1

Coding: you have a network. Encode this as a network connecting nodes located in a discrete two-dimensional space.

The question really asks you to count the number of paths that meet the following properties:

• There are 3 lines
• The length between each such turn is equal to
• The beginning and end of the path are the same.

A turn in this case is ever (a), if the previous step led to a change in the y-coordinate, this movement leads to a change in the x-coordinate; or (b) if the previous step led to a change in the x-coordinate, this change leads to a change in the y-coordinate.

Regarding process tracking: the best suggestions I've seen on this page are simply to loop over all the node and for each such node to check all possible sizes of the square. This should eliminate the need for further tracking.

If you have a smarter method, if your paths are always left or always right, each square is uniquely identified by the starting vertex and side length.

Answer 2

If you can model this as a matrix, then the only necessary information is the position of the vertices. Then, for each vertex, check all the vertices in the same row, and for each vertex found, check their column. then delete the processed vertex. Do the same for the columns. In the worst case, there will be n! (?)

I have added code for clarification.

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

Answer 3

The simplest way would be to loop through each vertex and check if it can be the top left vertex of a square of width 1, then width 2, 3, etc.

Answer 4

Something like this should do this:

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

Basically, for each point in the picture, you check every possible square size if a square of that size starts with this pixel. This is pretty easy, since your squares are all “aligned” with the borders ... The problem would be if they were not ...