PDA

View Full Version : For you math pros out there..




mrl72
Jan 22, 2011, 02:59 PM
Not neccessarily Objective-C related, although the end goal is to have that, this is more of a brain teaser if you like! A virtual pint goes to the person who solves it! :)

I'm working on an app that displays "tiles" (basically images on buttons 190x190 pixels) in a grid that is 4 tiles wide by infinite deep, on a UIScrollView with vertical scrolling only. Each tile needs to be created at runtime and added in a sequential order, ie row 0 1 thru 4, row 2 1 thru 4 etc. I have everything working great, no problems. Saying that, I now want to include tiles that are 2x2 tiles in size added in the same sequential order, but I need to calculate the correct x & y positions of the smaller tiles that are added around it so they don't overlap. So if the 2x2 tile lands at column 3 & 4 on row 1, then the next two tiles should be added to rows 2, column 1 & 2 then the next 9 thru 12. In some cases a large tile might only appear once, or not at all. And the large tiles can only appear starting in columns 1 or columns 3, not in the middle and they can appear side by side (as in example below).

So I've been racking my brain on this for the past two days and have not come up with anything substantial without creating messy if..then logic, so ideally this needs to go into a method that I would call and it would just give me the x and y coordinates back of where to put the next small tile if a larger tile is occupying the space next to it. I was thinking by giving each tile a sequential number I can determine what numbers the larger ones take up and use that in an array or something. That way I can figure out what tile space is not occupied, but from there..... staring at ceiling....emptiness. I'm not a math expert so suspect there's some easy formula I can use, at least that's what I hope! :)

http://loughers.smugmug.com/photos/1164538831_AyJsM-XL.jpg

Cheers.



bweberapps
Jan 22, 2011, 04:17 PM
I don't have a complete answer, but more of a suggestion. After you add a new square add it to an array of added squares. Then when you add another square to the next position loop through each square in the array and check if the new square overlaps one of the existings squares. If it does then go to the next position and check again until it finds an open spot. It could be done using a recursive function call. Also there is a function rectcontainsrect (I think that's what it's called) that should help you find out if squares are overlapping. Hope that helps.

mrl72
Jan 22, 2011, 05:18 PM
I don't have a complete answer, but more of a suggestion. After you add a new square add it to an array of added squares. Then when you add another square to the next position loop through each square in the array and check if the new square overlaps one of the existings squares. If it does then go to the next position and check again until it finds an open spot. It could be done using a recursive function call. Also there is a function rectcontainsrect (I think that's what it's called) that should help you find out if squares are overlapping. Hope that helps.

And the virtual pint is awarded!

http://www.ndmobiles.co.uk/files/blogpages-thumbnail-60.jpg

Thanks mate, that was exactly what I was looking for.CGRecotconstrainsrect led me to CGRectIntersectsRect which works great. With just a few lines of code I was able to quickly check if the tile fell on top of the larger one and if so just move it down the chain until it didn't intersect with anything.

Cheers again!

holmesf
Feb 3, 2011, 01:21 AM
I don't have a complete answer, but more of a suggestion. After you add a new square add it to an array of added squares. Then when you add another square to the next position loop through each square in the array and check if the new square overlaps one of the existings squares. If it does then go to the next position and check again until it finds an open spot. It could be done using a recursive function call. Also there is a function rectcontainsrect (I think that's what it's called) that should help you find out if squares are overlapping. Hope that helps.

You could do this, but what you are proposing is highly inefficient. You need only compare the square with the previous 4 added. A square could not intersect anything added before that due to the limited size of squares. What you're proposing would make construction of the array a O(n^2) operation which could perform badly once you get into the realm of hundreds of squares.

mrl72
Feb 3, 2011, 07:33 AM
Hey holmesf, yeah you are right and I did think of that. So I have a counter in there that after 4 counts resets and no longer checks the intersection until another larger square pops up. Thanks for that though.