Math genius (sarcasm) is treading water

Hi, sometimes my school days catch up with me and I realize that I had weaknesses in mathematics :wink:

I have an array of Xojo.Rect. Each rect has a different height. The width does not matter!

Furthermore I have x-columns, which are defined by a width. The goal is to divide all the rects from the array into the columns. I thought it would be “smart” to take the total height of the array for all calculations, divide it by the number of columns to get the height of a single column, and then fill all columns.

So what I’m failing at the moment is probably a pretty simple loop, namely how I fill the columns. Here is a scheme.

Can someone please give me some math lessons? :wink:

Thanks

I don’t even get why this would be smart. The height of a single column relates to how many and how big (high) the rectangles are that expect to live in the column. As I understand your drawing, the left shows the height of a column that contains all members. Then there are three columns that contain subsets of those rectangles. But they are not each 1/3 the height of the left column. Nor would you expect them to be.

So somehow I do not understand what you are asking.

Maybe @Kem Tekinay can solve it using regex?
Or @Norman Palardy can solve it using classes?
Just kidding…

How do you want the result to be? I as in the left image?

You don’t need pure math, you need to write a distributive algorithm trying to fit more or less the same sum of heights into n columns, IF possible AND in sequence.

seems you need to solve for

  1. the minimum height of each column that can contain all the items
  2. the distribution of the items is that achieves that minimum

that is assuming I understand the question correctly ?

I have updated the schematic above. Maybe it wasn’t very clear.

So please understand the area on the left (before the black arrow) as my data. These should be “translated” into the area on the right - graphically converted.
Thereby we have the blue frame, which contains the defined columns. Each column has the same height, namely that of the blue frame. I calculate this height from the height of all (data) rects divided by the number of columns. So the columns inherit their height from the blue frame. Each (graphical) column has a property Rects() As Xojo.Rect, which stores the Rects. I just want to translate all data Rects graphically, making sure that the height of the rect of a column is always <= the height of the blue frame.

The algorithm I think, you should look at the current height of each column. And the AppendNewRow(label, height) will put that “box” into the next available empty column, and once all those are occupied, only will put in the last column, but firstly, will inspect if the current column height will be higher than last column height, and if so, append the first “box” of the last column to the previous column, before appending this new box to the last column, and when appending it to the previous column, do the same, flowing the differences towards the first column.

The max height of the columns we find this way will be your max (blue) that can’t be found previously using a simplistic math average that can give us an impossible unsuitable value (like lower than a huge box).

this may not always be possible
for instance if you have 3 rects
one has height 100
one has height 10
one has height 10

120 / 3 = 40 but you cannot fit the first 100 into a column that is only 40 tall

obviously other scenarios exist that break your constraint

True, if there are less than 3 entries, the total height must be that of the entry with the highest height. In addition, the rect in the last column (in the case of two total rects, only two columns can be filled) must not be higher than that of the previous column. If this is the case, this rect must be added to the previous column.

I’ve created a small sample project to go on.

[quote=485189:@Martin Trippensee]True, if there are less than 3 entries, the total height must be that of the entry with the highest height. In addition, the rect in the last column (in the case of two total rects, only two columns can be filled) must not be higher than that of the previous column. If this is the case, this rect must be added to the previous column.

I’ve created a small sample project to go on.[/quote]

This was just an example that was easy to come up with that demonstrated a problem
But you can extend this so just about any number of rects and columns and there will always be setups where simply dividing the total height by the number of columns will result is situations where that division results in a height that is too small regardless of how you arrange the rects

it seems what you end up needing to find is the arrangement that results in the overall minimum height - even though this may be larger than the blue square you initially calculated

That blue square is the “ideal” - but it may not always be achievable

pseudocode at best


blueFrameSize = totalHeight / columnCount

// in the case of a 3 column list we want to move things from 
// column 0 to column 1 and then 
// column 1 to column 2 but not from column 2 to column 3

for current column = 0 to column count - 2 

         while total height ( current column ) > blue frame size

                  if count of items in current column > 1 then
                          move last item in this column to next column
                 else
                     // this column only has 1 item and its still larger ?
                     blue framesize = max(current column total height, blue frame size)
                     exit while
                end if

         wend

next

something along these lines will shuffle items from left to roight and try to keep the size of each column to as close to the calculated the blue frame size as it can

the last column though may spill way over

you’d have to retry with a larger blue frame size and rerun the redistribution until you get to a size that finally stabilizes with the number of columns you want

Thanks for the input.

I’ve made some progress and it looks pretty good with the division. But there is still the mistake that not all rows are drawn. Probably a margin value must be added to the AreasHeight.
I have updated the sample project. Any suggestions?

you mean besides “please dont make me open 2019r3.1 yet again” ? :stuck_out_tongue:

I’ll look but I supect its the problem I stated before where you can just divide by columns and fit everything AND draw them all

I don’t think I understand you, Norman. I’ve made another change to add a little leeway to the AreasHeight. I have not considered your suggestions yet. I need to see where to put them in my code first.

ok i’ve revised it and put in a hard coded test set of data that is much simpler to try & visualize than the random set thats there
and then made it so you can insert random data as you had

so far it seems to handle things as desired BUT it does sometimes have to make the “blue rect” larger when it cannot fit the data
again if you assume the first row is 100 tall and then additional rows are 10, 20, 20
the total height is 150 but when you divide by 4 the calculated optimal size would be about 42,5
But that is definitely not tall enough for the first row

http://great-white-software.com/miscellaneous/Forum%2059686.xojo_binary_project.zip

the hard coded sample data is easiest to follow whats going on

Thanks Norman.

Suggestion: Replace following code in Window1.Open:

' Calculate areas height. AreaHeight = (TotalHeight / ColumnWidths.Count) + Rows(Rows.LastRowIndex).Size.Height

you’ll se that in the loop where the rows that go in each column I make a condition that there be at least 1 row and if that row is taller than the blue rect then the blue rect is made taller to accommodate it

otherwise you have to clip that rect and move part of the rect to the next column

If you need to put ALL the content inside, you need to let the distribution algorithm do its job freely and ask what’s the CurrentHeight() when necessary. It’s done just “reading” a Columns.MaxHeight() // that gets the Column.height value of the highest column.

You don’t set your blue “limit”, you read it at end.