Re^2: Tricky math problem ...

Given space (x,y) and a bunch of points (x_i,y_j) starting from (1,1) partition the space into squared such that each square starts from (1,1) or (x_i,y_j) filling the space to (x_i+,y_j+1) (in ither words filling the space between it) and no square overlaps with any other. Example: if the (x_i,y_j) is at (3,4) than the area between (1,1) and (3,4) can be filled with square o=(1,1,3):


0  1  2  3   
1  o  o  o
2  o  o  o   
3  o  o  o   
4        x
[download]

and a=(1,4,1) b=(2,4,1) x = (3,4,1)


0  1  2  3   
1  o  o  o
2  o  o  o   
3  o  o  o   
4  a  b  x
[download]

so the result is :

(1,1,3)
(1,4,1)
(2,4,1)
(3,4,1)
[download]

and of course this repeats for all other points in the initial chart (marked with "X") until the entire area (12,12) is filled

Comment on Re^2: Tricky math problem ... Select or Download Code

Replies are listed 'Best First'.
Re^3: Tricky math problem ... by LanX (Saint) on May 04, 2019 at 11:09 UTC
You want to fill the gaps between your x points with disjoint squares? > I need to know how many of these squares are in the space and all their coordinates (tuples). You are implying there is only one solution, that's wrong because you exclude overlaps. Maybe you have an "optimal" solution in mind, but you didn't tell us the criteria. Like smallest number of covering squares or always starting from the left upper corner going right then down otherwise the solution is trivial, just take all "squares" with length 1. Give us your solution for your OP maybe we can guess what you really want. Smells like an XY problem to me. Rectangles instead of squares would be much easier. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]
Re^4: Tricky math problem ... by bliako (Monsignor) on May 04, 2019 at 14:57 UTC
otherwise the solution is trivial, just take all "squares" with length 1. and keep merging them till the cows come home...	[reply]
Re^4: Tricky math problem ... by baxy77bax (Deacon) on May 04, 2019 at 11:30 UTC
yes sorry I did don specify that so the condition is: "always starting from the left upper corner going right then down" I understand rectangles would be easier but i need squares as then i can mark the coordinate with one number only. I'll post the solution in te initial post so ppl do not need to read the conversation through ... And thnx!!	[reply]
Re^5: Tricky math problem ... by roboticus (Chancellor) on May 04, 2019 at 12:29 UTC
baxy77bax: You still haven't addressed the points LanX mentioned. ...roboticus When your only tool is a hammer, all problems look like your thumb.	[reply]
Re^3: Tricky math problem ... by holli (Abbot) on May 04, 2019 at 10:51 UTC
Example: if the (x_i,y_j) is at (3,4) than the area between (1,1) and (3,4) can be filled with square o=(1,1,3): Why? You're saying s is the lenght of the square starting at 1,1. With length 3 the resulting corner would be 4,4. Not 3,4. Or in other words, there can't be a square between (1,1) and (3,4) since a squares' sides are of equal length. (3,4) - (1,1) = (2,3) #NotASquare holli You can lead your users to water, but alas, you cannot drown them.	[reply]
Re^3: Tricky math problem ... by LanX (Saint) on May 04, 2019 at 11:24 UTC
https://en.m.wikipedia.org/wiki/Polygon_covering > the square covering problem is linear for hole-free polygons but NP-hard for general polygons Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]


Clear questions and runnable code get the best and fastest answer
	PerlMonks