Least value grouping algorithm
Author
Given an array of values, I need an algorithm that can group like values (in a rect shape) so as to end up with the smallest number of groups. eg
If we have a 4x4 grid like so
1 1 1 0
1 1 1 0
0 1 1 0
0 0 0 0
Zero''s are blank space and one''s represent polygons. This grid can be broken down two ways:
Three groups - 3 vertical or horizontal lines
Two groups - a group of 3x2 and 1x2 which is the desired result.
The grid represents a game level which is generated into polygons at runtime. Instead of having 8 individual polygons (represented by the ones in the grid above), I want to break it down to two.
Anyone know an algorithm to accomplish this?
Thanks,
Jules.
I don''t know if this has any relevance to your question, but I if you view your array as a table for a boolean relation, there are ways to reduce it to the simplest (simplest == smallest? )equational representation. Ah, boolean algebra, the only thing fun I ever learned in my basic digital systems courses.
Can two rectangular groups overlap each other? (If they can, then there''s a fairly simple solution, otherwise the problem is more complex.)
Author
No, rectangles can''t overlap Eric. They are converted into 4 sided polygons. Any number other than zero in the multidimensional array gets converted into polygons.
So a simple multidimensional array of:
1 1 1
1 1 1
can be converted into 1 3x2 polygon instead of 6 1x1 polygons. I need to work out how to calculate the least number of polygons needed.
So a simple multidimensional array of:
1 1 1
1 1 1
can be converted into 1 3x2 polygon instead of 6 1x1 polygons. I need to work out how to calculate the least number of polygons needed.
Start off with one 1x1 polygon for each 1.
Then join them if the joined construct is rectangluar
Once no more joins are possible, you''re done
e.g
---------------------------
I may be getting older, but I refuse to grow up
Then join them if the joined construct is rectangluar
Once no more joins are possible, you''re done
e.g
1 1 1 01 1 1 00 1 1 00 0 0 0-> each his own1 2 3 0 4 5 6 00 7 8 00 0 0 0-> only with higher numberjoin(1+2) = 1'' join(1''+3) = 1'' join(4+5) = 4'' join(4''+6) = 4''join(7+8) = 7''1 1 1 04 4 4 00 7 7 00 0 0 0-> againjoin(1+4) = 1''1 1 1 01 1 1 00 7 7 00 0 0 0-> nothing more to do -> done ---------------------------
I may be getting older, but I refuse to grow up
Start off with one 1x1 polygon for each 1.
Then join them if the joined construct is rectangluar
Once no more joins are possible, you''re done
e.g
want to do it in c++?
---------------------------
I may be getting older, but I refuse to grow up
Then join them if the joined construct is rectangluar
Once no more joins are possible, you''re done
e.g
1 1 1 01 1 1 00 1 1 00 0 0 0-> each his own1 2 3 0 4 5 6 00 7 8 00 0 0 0-> only with higher numberjoin(1+2) = 1'' join(1''+3) = 1'' join(4+5) = 4'' join(4''+6) = 4''join(7+8) = 7''1 1 1 04 4 4 00 7 7 00 0 0 0-> againjoin(1+4) = 1''1 1 1 01 1 1 00 7 7 00 0 0 0-> nothing more to do -> done want to do it in c++?
---------------------------
I may be getting older, but I refuse to grow up
Author
I''m not sure if I''m missing something in your answer Dreamforger. It appears you''re just connecting poly''s that are next to each other and that doesn''t always produce the least number of groups? In this situation
1 1 1 1
1 1 1
1
it can be broken down into either 3 groups or 4 groups. How do you know which one to pick. This is a very basic situation. You can end up with things like
1 1 1 1 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1
and then how do you work out the least number of groups? The maps can be huge. I think the only way it can be done is to work out every possible combination first and to then narrow it down. Possibly A* could be used. eg. The above can be broken down into ~19 different groups not including individual blocks. Then I could convert these into nodes and somehow use A* to work out the least number of groups needed. Maybe. I might post this into AI and see if anyone knows how that could be achieved. A mathematical formula would be much easier though.
Jules.
1 1 1 1
1 1 1
1
it can be broken down into either 3 groups or 4 groups. How do you know which one to pick. This is a very basic situation. You can end up with things like
1 1 1 1 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1
and then how do you work out the least number of groups? The maps can be huge. I think the only way it can be done is to work out every possible combination first and to then narrow it down. Possibly A* could be used. eg. The above can be broken down into ~19 different groups not including individual blocks. Then I could convert these into nodes and somehow use A* to work out the least number of groups needed. Maybe. I might post this into AI and see if anyone knows how that could be achieved. A mathematical formula would be much easier though.
Jules.
Do it in the fairly simple solution (make them overlap) and then find those who are overlapped (not too hard) and shrink one of the 2 overlapping so they stop overlapping.
Oh, and is your map a torus?
Like, both sides are connected horizontally (and the other 2 vertically), as in :
110001
110001
110001
The smallest solution being the 3x3 square you get if you connect that as a torus?
If your map isnt like that, then the simple solution I know (tabular method, table method, dunno how it is called in english) cant be applied. But I guess you can add a dummy zeroed column in the beginning (colum "A") and in the end (column "H" in this case), and a zeroed line in the top and on the bottom, and apply the table method (based on Karnaugh map) and then do that shrinking thing to not have overlapping rectangles.
----
Edit :
Damn I feel dumb
.
You can only add 1 zeroed column and 1 zeroed line and it should work... No need to add 2 zeroed lines :>. That was dumb... heh
---
Cya,
-RoTTer
[edited by - RoTTer on June 24, 2002 2:59:37 AM]
Oh, and is your map a torus?
Like, both sides are connected horizontally (and the other 2 vertically), as in :
110001
110001
110001
The smallest solution being the 3x3 square you get if you connect that as a torus?
If your map isnt like that, then the simple solution I know (tabular method, table method, dunno how it is called in english) cant be applied. But I guess you can add a dummy zeroed column in the beginning (colum "A") and in the end (column "H" in this case), and a zeroed line in the top and on the bottom, and apply the table method (based on Karnaugh map) and then do that shrinking thing to not have overlapping rectangles.
----
Edit :
Damn I feel dumb
.You can only add 1 zeroed column and 1 zeroed line and it should work... No need to add 2 zeroed lines :>. That was dumb... heh
---
Cya,
-RoTTer
[edited by - RoTTer on June 24, 2002 2:59:37 AM]
I had a longer answer which also highlighted the drawbacks of my proposal, but the server 500ed it and I didn''t want to type it all again.
I know that my proposal does not produce a perfect solution. Which is maily due to the fact that THE perfect solution needs not exist, but A perfect solution may exist
take your example
can be optimized as
which are perfectly equivalent
You said that your program wants to calculate the polys at runtime. Therefore my proposal was aimed at what I consider a good compromise between speed and quality of the result.
The problem you stated seems pretty NP-ish to me.
You can list all possibilities of building polygons and then apply a heuristic to judge the quality of each construct. In the end you''ll still have to select one of the many equally worthy possiblities.
I haven''t stopped thinking about your problem. Maybe I''ll still cook something up.
Think about the following:
do you really want it grouped like
which would be least groups, or like
which would allow for some spatial locality
In the first case group 2 would have to be drawn always, but possibly never completely (depending on the scale of the map, and I assume that only 3x3 are displayed at the same time)
In the second case some groups can allways be culled and the not displayed tranformations are reduced.
Just a thought from my side
---------------------------
I may be getting older, but I refuse to grow up
I know that my proposal does not produce a perfect solution. Which is maily due to the fact that THE perfect solution needs not exist, but A perfect solution may exist
take your example
1 1 1 01 1 1 00 1 1 00 0 0 0 can be optimized as
1 1 1 01 1 1 00 2 2 00 0 0 0or1 2 2 01 2 2 00 2 2 00 0 0 0 which are perfectly equivalent
You said that your program wants to calculate the polys at runtime. Therefore my proposal was aimed at what I consider a good compromise between speed and quality of the result.
The problem you stated seems pretty NP-ish to me.
You can list all possibilities of building polygons and then apply a heuristic to judge the quality of each construct. In the end you''ll still have to select one of the many equally worthy possiblities.
I haven''t stopped thinking about your problem. Maybe I''ll still cook something up.
Think about the following:
0 1 0 0 0 01 1 1 1 1 10 0 0 0 1 0 do you really want it grouped like
0 1 0 0 0 02 2 2 2 2 20 0 0 0 3 0 which would be least groups, or like
0 2 0 0 0 01 2 3 3 4 50 0 0 0 4 0 which would allow for some spatial locality
In the first case group 2 would have to be drawn always, but possibly never completely (depending on the scale of the map, and I assume that only 3x3 are displayed at the same time)
In the second case some groups can allways be culled and the not displayed tranformations are reduced.
Just a thought from my side
---------------------------
I may be getting older, but I refuse to grow up
Dreamforger there''s no guarantee your solution will produce anything even resembling a good solution, let alone an ideal one. You haven''t specified how your algorithm decides which joins to make. Why 1+2, 1+3, 4+5, and 4+6? Why not 1+2, 3+6, and 5+7?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
