COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Selecting and merging rectangles

• Follow

```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

```
 0
Reply eriwik (500) 6/15/2006 1:48:04 PM

```<eriwik@student.chalmers.se> wrote in message
> 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

```
 0
Reply owong (5281) 6/15/2006 2:22:05 PM

```Oliver Wong wrote:
> <eriwik@student.chalmers.se> wrote in message
> > 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

--
Eriwik

```
 0
Reply eriwik (500) 6/16/2006 5:59:21 AM

```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
```
 0
Reply lshaw-usenet (926) 6/16/2006 7:32:29 AM

```eriwik@student.chalmers.se wrote:
> Oliver Wong wrote:
>> <eriwik@student.chalmers.se> wrote in message
>>> 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
>

And how do you propose to calculate the total area of the selected
pixels without checking each one of them?
```
 0
Reply usenet134 (507) 6/16/2006 8:51:26 AM

```"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
>>>> 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
>>
>
> 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

```
 0
Reply owong (5281) 6/16/2006 2:42:48 PM

```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
>>>>> 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
>>>
>>
>> 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
```
 0
Reply usenet134 (507) 6/16/2006 5:57:22 PM

```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
>>>>>> 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
>>>>
>>>
>>> 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.
```
 0
Reply usenet134 (507) 6/16/2006 6:30:40 PM

```"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

```
 0
Reply owong (5281) 6/16/2006 9:33:01 PM

8 Replies
47 Views