I'm having problems with coming up with a good algorithm for the
following:

Say you have a grid of squares (in this example 4x4 will do), then you
select the 4 squares in the center and merge these into one large
square. Then you select some new squares (which might or might not
include the new large square) how do you determine that the new
selection forms a rectangle?

Currently I'm representing each square/rectangle with the
X/Y-coordinates of the top-left corner and the width and height of the
square (so the top/left-most square in a 4x4-grid would be <0, 0, 1, 1>
and the merged center-squares would be <1, 1, 2, 2>), is there a better
way to represent this?

Anyone have experience of similar problems or links to sites that might
help?

--
Eriwik

<eriwik@student.chalmers.se> wrote in message 
news:1150379284.584794.263760@r2g2000cwb.googlegroups.com...
> I'm having problems with coming up with a good algorithm for the
> following:
>
> Say you have a grid of squares (in this example 4x4 will do), then you
> select the 4 squares in the center and merge these into one large
> square. Then you select some new squares (which might or might not
> include the new large square) how do you determine that the new
> selection forms a rectangle?
>
> Currently I'm representing each square/rectangle with the
> X/Y-coordinates of the top-left corner and the width and height of the
> square (so the top/left-most square in a 4x4-grid would be <0, 0, 1, 1>
> and the merged center-squares would be <1, 1, 2, 2>), is there a better
> way to represent this?
>
> Anyone have experience of similar problems or links to sites that might
> help?

    For simplicity, imagine that in your initial grid, every square is of 
the same unit size, and we call this size "1 pixel".

    Given a group of rectilinear rectangles, some of which may be multiple 
pixels in size, you can to determine whether this group would form a new 
rectilinear rectangle.

    Find the left most, top most, right most, and bottom most pixel 
coordinate. If the group forms a rectilinear rectangle, then all pixels 
within region should be part of the selected group. So check that.

    - Oliver 

Oliver Wong wrote:
> <eriwik@student.chalmers.se> wrote in message
> news:1150379284.584794.263760@r2g2000cwb.googlegroups.com...
> > I'm having problems with coming up with a good algorithm for the
> > following:
> >
> > Say you have a grid of squares (in this example 4x4 will do), then you
> > select the 4 squares in the center and merge these into one large
> > square. Then you select some new squares (which might or might not
> > include the new large square) how do you determine that the new
> > selection forms a rectangle?
> >
> > Currently I'm representing each square/rectangle with the
> > X/Y-coordinates of the top-left corner and the width and height of the
> > square (so the top/left-most square in a 4x4-grid would be <0, 0, 1, 1>
> > and the merged center-squares would be <1, 1, 2, 2>), is there a better
> > way to represent this?
> >
> > Anyone have experience of similar problems or links to sites that might
> > help?
>
>     For simplicity, imagine that in your initial grid, every square is of
> the same unit size, and we call this size "1 pixel".
>
>     Given a group of rectilinear rectangles, some of which may be multiple
> pixels in size, you can to determine whether this group would form a new
> rectilinear rectangle.
>
>     Find the left most, top most, right most, and bottom most pixel
> coordinate. If the group forms a rectilinear rectangle, then all pixels
> within region should be part of the selected group. So check that.

Yes, after reading your post and having a good night's sleep the
problem seems much less daunting. I'll use a variant of your solution,
instead of checking that every pixel in the region is selected I'll
calculate the total area of the selected pixels and compare this with
the area of the region. This will save me from iterating through some
data-structures more than neccessary. Thanks for your reply.

--
Eriwik

eriwik@student.chalmers.se wrote:
> I'm having problems with coming up with a good algorithm for the
> following:
> 
> Say you have a grid of squares (in this example 4x4 will do), then you
> select the 4 squares in the center and merge these into one large
> square. Then you select some new squares (which might or might not
> include the new large square) how do you determine that the new
> selection forms a rectangle?
> 
> Currently I'm representing each square/rectangle with the
> X/Y-coordinates of the top-left corner and the width and height of the
> square (so the top/left-most square in a 4x4-grid would be <0, 0, 1, 1>
> and the merged center-squares would be <1, 1, 2, 2>), is there a better
> way to represent this?

If you can make the assumption that the rectangles never overlap,
then it's fairly easy:

Just compute the sum of the areas of the rectangles.  Then take the
minimum and maximum X coordinates and the minimum and maximum Y
coordinates and compute (maxX-minX)*(maxY-minY).  In effect, you
are forming a new rectangle just exactly wide and tall enough to cover
every point in the set of rectangles when laid into the right position.

The individual rectangles fit together into a larger rectangle if and
only if the area of the larger rectangle equals the sum of the areas
of the smaller rectangles.  (If the smaller rectangles' areas' sum is
less than the large rectangle, this means they don't cover the whole
area.  If it's larger, then it would mean they overlap, which they
don't, by definition.)

   - Logan

eriwik@student.chalmers.se wrote:
> Oliver Wong wrote:
>> <eriwik@student.chalmers.se> wrote in message
>> news:1150379284.584794.263760@r2g2000cwb.googlegroups.com...
>>> I'm having problems with coming up with a good algorithm for the
>>> following:
>>>
>>> Say you have a grid of squares (in this example 4x4 will do), then you
>>> select the 4 squares in the center and merge these into one large
>>> square. Then you select some new squares (which might or might not
>>> include the new large square) how do you determine that the new
>>> selection forms a rectangle?
>>>
>>> Currently I'm representing each square/rectangle with the
>>> X/Y-coordinates of the top-left corner and the width and height of the
>>> square (so the top/left-most square in a 4x4-grid would be <0, 0, 1, 1>
>>> and the merged center-squares would be <1, 1, 2, 2>), is there a better
>>> way to represent this?
>>>
>>> Anyone have experience of similar problems or links to sites that might
>>> help?
>>     For simplicity, imagine that in your initial grid, every square is of
>> the same unit size, and we call this size "1 pixel".
>>
>>     Given a group of rectilinear rectangles, some of which may be multiple
>> pixels in size, you can to determine whether this group would form a new
>> rectilinear rectangle.
>>
>>     Find the left most, top most, right most, and bottom most pixel
>> coordinate. If the group forms a rectilinear rectangle, then all pixels
>> within region should be part of the selected group. So check that.
> 
> Yes, after reading your post and having a good night's sleep the
> problem seems much less daunting. I'll use a variant of your solution,
> instead of checking that every pixel in the region is selected I'll
> calculate the total area of the selected pixels and compare this with
> the area of the region. This will save me from iterating through some
> data-structures more than neccessary. Thanks for your reply.
> 

And how do you propose to calculate the total area of the selected 
pixels without checking each one of them?

"Mark P" <usenet@fall2005REMOVE.fastmailCAPS.fm> wrote in message 
news:iiukg.117049$dW3.34758@newssvr21.news.prodigy.com...
> eriwik@student.chalmers.se wrote:
>> Oliver Wong wrote:
>>> <eriwik@student.chalmers.se> wrote in message
>>> news:1150379284.584794.263760@r2g2000cwb.googlegroups.com...
>>>> I'm having problems with coming up with a good algorithm for the
>>>> following:
>>>>
>>>> Say you have a grid of squares (in this example 4x4 will do), then you
>>>> select the 4 squares in the center and merge these into one large
>>>> square. Then you select some new squares (which might or might not
>>>> include the new large square) how do you determine that the new
>>>> selection forms a rectangle?
>>>>
>>>> Currently I'm representing each square/rectangle with the
>>>> X/Y-coordinates of the top-left corner and the width and height of the
>>>> square (so the top/left-most square in a 4x4-grid would be <0, 0, 1, 1>
>>>> and the merged center-squares would be <1, 1, 2, 2>), is there a better
>>>> way to represent this?
>>>>
>>>> Anyone have experience of similar problems or links to sites that might
>>>> help?
>>>     For simplicity, imagine that in your initial grid, every square is 
>>> of
>>> the same unit size, and we call this size "1 pixel".
>>>
>>>     Given a group of rectilinear rectangles, some of which may be 
>>> multiple
>>> pixels in size, you can to determine whether this group would form a new
>>> rectilinear rectangle.
>>>
>>>     Find the left most, top most, right most, and bottom most pixel
>>> coordinate. If the group forms a rectilinear rectangle, then all pixels
>>> within region should be part of the selected group. So check that.
>>
>> Yes, after reading your post and having a good night's sleep the
>> problem seems much less daunting. I'll use a variant of your solution,
>> instead of checking that every pixel in the region is selected I'll
>> calculate the total area of the selected pixels and compare this with
>> the area of the region. This will save me from iterating through some
>> data-structures more than neccessary. Thanks for your reply.
>>
>
> And how do you propose to calculate the total area of the selected pixels 
> without checking each one of them?

    Given a set of rectangles, multiply their height and their widths, and 
sum these products together. In the worse case, every rectangle is exactly 1 
pixel in size, in which case it's asymptotically the same speed as checking 
each pixel (though the constant factor will probably be bigger)

    - Oliver 

Oliver Wong wrote:
> 
> "Mark P" <usenet@fall2005REMOVE.fastmailCAPS.fm> wrote in message 
> news:iiukg.117049$dW3.34758@newssvr21.news.prodigy.com...
>> eriwik@student.chalmers.se wrote:
>>> Oliver Wong wrote:
>>>> <eriwik@student.chalmers.se> wrote in message
>>>> news:1150379284.584794.263760@r2g2000cwb.googlegroups.com...
>>>>> I'm having problems with coming up with a good algorithm for the
>>>>> following:
>>>>>
>>>>> Say you have a grid of squares (in this example 4x4 will do), then you
>>>>> select the 4 squares in the center and merge these into one large
>>>>> square. Then you select some new squares (which might or might not
>>>>> include the new large square) how do you determine that the new
>>>>> selection forms a rectangle?
>>>>>
>>>>> Currently I'm representing each square/rectangle with the
>>>>> X/Y-coordinates of the top-left corner and the width and height of the
>>>>> square (so the top/left-most square in a 4x4-grid would be <0, 0, 
>>>>> 1, 1>
>>>>> and the merged center-squares would be <1, 1, 2, 2>), is there a 
>>>>> better
>>>>> way to represent this?
>>>>>
>>>>> Anyone have experience of similar problems or links to sites that 
>>>>> might
>>>>> help?
>>>>     For simplicity, imagine that in your initial grid, every square 
>>>> is of
>>>> the same unit size, and we call this size "1 pixel".
>>>>
>>>>     Given a group of rectilinear rectangles, some of which may be 
>>>> multiple
>>>> pixels in size, you can to determine whether this group would form a 
>>>> new
>>>> rectilinear rectangle.
>>>>
>>>>     Find the left most, top most, right most, and bottom most pixel
>>>> coordinate. If the group forms a rectilinear rectangle, then all pixels
>>>> within region should be part of the selected group. So check that.
>>>
>>> Yes, after reading your post and having a good night's sleep the
>>> problem seems much less daunting. I'll use a variant of your solution,
>>> instead of checking that every pixel in the region is selected I'll
>>> calculate the total area of the selected pixels and compare this with
>>> the area of the region. This will save me from iterating through some
>>> data-structures more than neccessary. Thanks for your reply.
>>>
>>
>> And how do you propose to calculate the total area of the selected 
>> pixels without checking each one of them?
> 
>    Given a set of rectangles, multiply their height and their widths, 
> and sum these products together. In the worse case, every rectangle is 
> exactly 1 pixel in size, in which case it's asymptotically the same 
> speed as checking each pixel (though the constant factor will probably 
> be bigger)
> 
>    - Oliver

And what if the rectangles overlap in such a way that their total area 
exactly equals the area of the "bounding box", but they do not in fact 
form a rectangle?  Since you don't want to count overlapping areas more 
than once you need to check each pixel.

(If you want a concrete illustration, take two overlapping squares and 
begin sliding one diagonally relative to the other.  At some 
intermediate point the bounding box area will exactly equal the sum of 
the square areas.)

Mark

Mark P wrote:
> Oliver Wong wrote:
>>
>> "Mark P" <usenet@fall2005REMOVE.fastmailCAPS.fm> wrote in message 
>> news:iiukg.117049$dW3.34758@newssvr21.news.prodigy.com...
>>> eriwik@student.chalmers.se wrote:
>>>> Oliver Wong wrote:
>>>>> <eriwik@student.chalmers.se> wrote in message
>>>>> news:1150379284.584794.263760@r2g2000cwb.googlegroups.com...
>>>>>> I'm having problems with coming up with a good algorithm for the
>>>>>> following:
>>>>>>
>>>>>> Say you have a grid of squares (in this example 4x4 will do), then 
>>>>>> you
>>>>>> select the 4 squares in the center and merge these into one large
>>>>>> square. Then you select some new squares (which might or might not
>>>>>> include the new large square) how do you determine that the new
>>>>>> selection forms a rectangle?
>>>>>>
>>>>>> Currently I'm representing each square/rectangle with the
>>>>>> X/Y-coordinates of the top-left corner and the width and height of 
>>>>>> the
>>>>>> square (so the top/left-most square in a 4x4-grid would be <0, 0, 
>>>>>> 1, 1>
>>>>>> and the merged center-squares would be <1, 1, 2, 2>), is there a 
>>>>>> better
>>>>>> way to represent this?
>>>>>>
>>>>>> Anyone have experience of similar problems or links to sites that 
>>>>>> might
>>>>>> help?
>>>>>     For simplicity, imagine that in your initial grid, every square 
>>>>> is of
>>>>> the same unit size, and we call this size "1 pixel".
>>>>>
>>>>>     Given a group of rectilinear rectangles, some of which may be 
>>>>> multiple
>>>>> pixels in size, you can to determine whether this group would form 
>>>>> a new
>>>>> rectilinear rectangle.
>>>>>
>>>>>     Find the left most, top most, right most, and bottom most pixel
>>>>> coordinate. If the group forms a rectilinear rectangle, then all 
>>>>> pixels
>>>>> within region should be part of the selected group. So check that.
>>>>
>>>> Yes, after reading your post and having a good night's sleep the
>>>> problem seems much less daunting. I'll use a variant of your solution,
>>>> instead of checking that every pixel in the region is selected I'll
>>>> calculate the total area of the selected pixels and compare this with
>>>> the area of the region. This will save me from iterating through some
>>>> data-structures more than neccessary. Thanks for your reply.
>>>>
>>>
>>> And how do you propose to calculate the total area of the selected 
>>> pixels without checking each one of them?
>>
>>    Given a set of rectangles, multiply their height and their widths, 
>> and sum these products together. In the worse case, every rectangle is 
>> exactly 1 pixel in size, in which case it's asymptotically the same 
>> speed as checking each pixel (though the constant factor will probably 
>> be bigger)
>>
>>    - Oliver
> 
> And what if the rectangles overlap in such a way that their total area 
> exactly equals the area of the "bounding box", but they do not in fact 
> form a rectangle?  Since you don't want to count overlapping areas more 
> than once you need to check each pixel.
> 
> (If you want a concrete illustration, take two overlapping squares and 
> begin sliding one diagonally relative to the other.  At some 
> intermediate point the bounding box area will exactly equal the sum of 
> the square areas.)
> 
> Mark

Hmm, after reading other replies I think I've misunderstood the 
question.  Looks like overlapping isn't a possibility.

"Mark P" <usenet@fall2005REMOVE.fastmailCAPS.fm> wrote in message 
news:kNCkg.97753$H71.5841@newssvr13.news.prodigy.com...
>
> Hmm, after reading other replies I think I've misunderstood the question. 
> Looks like overlapping isn't a possibility.

    When I first read the question, it sounded a lot like an implementation 
for the game Puyo Puyo: http://www.retrogaming.it/megadrive/puyopuyo.htm so 
I automatically assumed overlapping wasn't a possibility (to be honest, it 
hadn't even occured to me), and basically went about explaining how to 
implement that aspect of that game.

    - Oliver