Path: csiph.com!usenet.pasdenom.info!gegeweb.org!eternal-september.org!feeder.eternal-september.org!mx05.eternal-september.org!.POSTED!not-for-mail
From: Eric Sosman <esosman@comcast-dot-net.invalid>
Newsgroups: comp.lang.java.programmer
Subject: Re: Converting Text File To Rectangles
Date: Wed, 13 Feb 2013 13:25:08 -0500
Organization: A noiseless patient Spider
Lines: 59
Message-ID: <kfglor$s6i$1@dont-email.me>
References: <7f49c487-f016-43a3-83a4-feebe072f76c@googlegroups.com> <kfc7r5$rd1$1@dont-email.me> <2rhnh817qca2g575nk2l0p6sqe2g8t03fi@4ax.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 13 Feb 2013 18:24:27 +0000 (UTC)
Injection-Info: mx05.eternal-september.org; posting-host="0d73d8cc209bff1c6395088b400d0605"; logging-data="28882"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+vRdGX56eBqgY+PIQ+MI6s"
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130107 Thunderbird/17.0.2
In-Reply-To: <2rhnh817qca2g575nk2l0p6sqe2g8t03fi@4ax.com>
Cancel-Lock: sha1:Hz1usbCfFEVC63UUXid8LMoty7E=
Xref: csiph.com comp.lang.java.programmer:22294

On 2/13/2013 12:06 PM, Gene Wirchenko wrote:
> On Mon, 11 Feb 2013 21:02:47 -0500, Eric Sosman
> <esosman@comcast-dot-net.invalid> wrote:
>
>> On 2/11/2013 8:51 PM, Scyth3 wrote:
>>> I have a save and load method for certain rectangles I need for a game. Say the user wants to save a map. The outputted map would look like this:
>>>
>>>
>>> 50 250 50 50
>>> 50 350 50 50
>>> 50 400 50 50
>>> 50 500 50 50
>>> 150 300 50 50
>>> 200 450 50 50
>>> 200 500 50 50
>>> 250 150 50 50
>>> 300 100 50 50
>>> 400 50 50 50
>>> 450 150 50 50
>>> 550 100 50 50
>>>
>>> X Y Width Height
>>>
>>> Now, how would I read this, and turn it into a rectangle?
>>
>>      Turning it into twelve rectangles would be easy, but I don't
>> know how you'd turn it into one.  Perhaps you could keep track of
>> the minimum X,Y and the maximum implied X,Y and form one rectangle
>> that surrounds the entire thing.  That rectangle might not be the
>> minimal surrounding rectangle, but it would be minimal among those
>> whose sides were parallel to the axes.
>
>       It would be a minimal regardless of whether the sides were
> parallel to the axes.  The vertices of each rectangle give the
> furthest extent of the rectangle in one direction (or two in the
> parallel case).

     The minimal surrounding rectangle's sides are not necessarily
parallel to the axes.  Counterexample: Let there be two surrounded
rectangles, each a 2x2 square, one centered at (1,1) and the other
at (99,99).  The minimal axis-aligned surrounding rectangle is a
square with one corner at the origin and its opposite at (100,100);
its area is 100*100=10000 and its perimeter is 4*100=400.

     Now consider a long skinny rectangle at a 45-degree angle,
lying athwart the y=x line.  To enclose the two small squares, it
must be 2*sqrt(2) wide and 100*sqrt(2) long, for an area of
2*100*2=400 and a perimeter of 2*(2+100)*sqrt(2)~=288.5, both
considerably smaller than their counterparts on the large square.

     It's true I didn't specify what I meant by "minimal," and
there may be other measures than area and perimeter that would
lead to a different conclusion.  But for those two, at least,
requiring the rectangle's sides to be axis-parallel can lead
to rejecting smaller non-aligned rectangles.

-- 
Eric Sosman
esosman@comcast-dot-net.invalid