Re: Selecting and merging rectangles
- From: Logan Shaw <lshaw-usenet@xxxxxxxxxxxxx>
- Date: Fri, 16 Jun 2006 07:32:29 GMT
eriwik@xxxxxxxxxxxxxxxxxxx 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
.
- References:
- Selecting and merging rectangles
- From: eriwik
- Selecting and merging rectangles
- Prev by Date: Re: Segmentation fault if I dont use printf?
- Next by Date: Re: finding nearest place
- Previous by thread: Re: Selecting and merging rectangles
- Next by thread: Re: Software Serialization (Both the Act, and the terminology)
- Index(es):
Relevant Pages
|
