Bounding boxes areas

[querypk]

I am a python programmer and not very familier with c++ ...
If I have
x is a 2D array of 0's and 1's
ex: x = array([1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,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])
what I want is a boundingbox over the region where we find clusters of
1's.So for instance in the above list first 3 roes and colums have 1's
so the area of that box is 3x3
so my final array should have an array of approx areas of clusters of
1's like
area = [ 9,4 ....]
Hope I am clear with my question.

[[0, 0, 0, 0, 0],
+-----+
[0,|1, 1,|0, 0],
| |
[0,|0, 1,|0, 0],
+-----+
[0, 0, 0, 0, 0]]

something like above. The resultant array should have the area of the
each such box.

 

[Howard]

I am a python programmer and not very familier with c++ ...
If I have
x is a 2D array of 0's and 1's
ex: x = array([1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,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])
what I want is a boundingbox over the region where we find clusters of
1's.So for instance in the above list first 3 roes and colums have 1's
so the area of that box is 3x3
so my final array should have an array of approx areas of clusters of
1's like
area = [ 9,4 ....]
Hope I am clear with my question.

[[0, 0, 0, 0, 0],
+-----+
[0,|1, 1,|0, 0],
| |
[0,|0, 1,|0, 0],
+-----+
[0, 0, 0, 0, 0]]

something like above. The resultant array should have the area of the
each such box.

There is nothing in your post that suggests what problem you're having with
C++. I can only assume you'd like us to simply do your homework for you.
That's not going to help you become a good programmer now, is it?

-Howard

 

[superprad]

I dont want you to code it. I can do my coding. I want you to give me
some ideas as to how to approach. Thats all.

 

[querypk]

Howard,
Sorry that you miss understood my question. In my post I never asked
you to code. If you read it correctly. All I am looking for is some
ideas such as are there any algorithms avalilble or what best approach
I should take.
I can comfortablly do my c++ coding . I thought its a discussion forum
and I was not expecting you to do my work.
If u can help please give some suggestions thats all.

 

[Howard]

Howard,
Sorry that you miss understood my question. In my post I never asked
you to code. If you read it correctly. All I am looking for is some
ideas such as are there any algorithms avalilble or what best approach
I should take.
I can comfortablly do my c++ coding . I thought its a discussion forum
and I was not expecting you to do my work.
If u can help please give some suggestions thats all.

You might want to ask in a more general-purpose newsgroup. This forum is
for discussion of C++ language issues, and what you're asking about appears
to be just an algorithm, which might just as well be implemented in any
common programming language.

Also, you might try using Google to search for solutions. That's a great
resource for existing algorithms.

If you ask in another newsgroup, you might also want to clarify the
specifications a little. I'm not sure I understand exactly what the
output(s) from your program would be, given a specific set of intputs. For
example, do you want ALL rectangles reported, or just first one you come
across (using whatever search method you choose). And does a valid
rectangle have to be ALL 1s, or just MOSTLY 1s? And what's the minimum size
of such a rectangle... 1x1? 2x2? Or do you want the BIGGEST such
rectangle? Those are questions you need to specify answers to before
someone could provide possible algorithms to handle the problem.

On the other hand, if you've got an algorithm already in mind, and just need
help writing the C++ code for it, then you could post your pseudo-code ideas
here, along with questions about the parts you're unsure of, and you're
certain to get help implementing the problem parts.

-Howard

 

[superprad]

Thanks you very much! If you Could refer any groups which deal with
algorithms specifically rather than language that would be great.

 

[Howard]

Thanks you very much! If you Could refer any groups which deal with
algorithms specifically rather than language that would be great.

comp.graphics.algorithms comes to mind (and a Google search for "bounding
rectangle" will show you plenty of posts there related to your question).

-Howard

 

[Thomas Matthews]

I am a python programmer and not very familier with c++ ...
If I have
x is a 2D array of 0's and 1's
ex: x = array([1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,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])
what I want is a boundingbox over the region where we find clusters of
1's.So for instance in the above list first 3 roes and colums have 1's
so the area of that box is 3x3
so my final array should have an array of approx areas of clusters of
1's like
area = [ 9,4 ....]
Hope I am clear with my question.

[[0, 0, 0, 0, 0],
+-----+
[0,|1, 1,|0, 0],
| |
[0,|0, 1,|0, 0],
+-----+
[0, 0, 0, 0, 0]]

something like above. The resultant array should have the area of the
each such box.

Since this issue is not about the C++ language,
a better place to ask would be You are seeking an algorithm, which is what they like
to discuss there.

My first guess at an algorithm is to:
1. Find the top bounding row.
2. Find the bottom bounding row.
3. Find the left bounding column.
4. Find the right bounding column.

I would write a simple program that finds the first
bounding box and get it working. Next task is to
enable it to find others (if that is a requirement).

Some issues to think about:

Do you want more than one bounding box?

How are you representing a bounding box?

How does the function return a container of
bounding boxes?

If this is a graphics issue, perhaps the people
in the graphics newsgroup can help.

C++ issues:

Is the 2d array an area of contiguous values?

Is the 2d array an array of arrays?

Can the dimensions change at run-time?

Is this an array of integers or bits?


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.comeaucomputing.com/learn/faq/
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library