how to find non intersecting bounding rectangles in the simple matrix in java?

Question

I have a 2D matrix which looks like

matr=([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]])

I need to write Java code which will find the non intersecting bounding rectangles for value 1

a similar problem was posted here: Fill Bounding Boxes in 2D array

But solution is on Python using some special libraries, i need to implement this in Java, plus i need to find non intersecting boxes in this case

So lets say we can store the points and rectangles as

class Point{
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Rectangle{
    Point topLeft, bottomRight;

    public Rectangle(Point topLeft, Point bottomRight) {
        this.topLeft = topLeft;
        this.bottomRight = bottomRight;
    }
}

In the provided example above the answer should be Rectangle(Point(2,2), Point(5,4)) the other rectangles intersect that is why don't need to count them

Answer 1

You can use BFS (Breadth-first search) algorithm to do this.

Steps are given below:

1. Iterate over all points (all values in Matrix) and check if a point has value 1
2. Start with a non visited point which contains 1
3. Run BFS to find all connected points from that point.
4. Mark/flag all visited points.
5. Calculate Top Left point and Bottom Right point among connected points.
6. start from 2.