Re: One for the programmers or maths/logic geeks

"John Hatpin" <RemoveThisjfhopkin@[EMAIL PROTECTED]
> wrote in message 
news:lfmb24lj268kkgobreqd02jdsm3j40j79g@[EMAIL PROTECTED]
>I must admit that I'm surprised at my seeming inability to come up
> with a neat, fast algorithm defined below.  I've had several stabs at
> it, but whatever approach I've taken so far, I'm not happy with the
> efficiency and robustness of each approach.  Surely AFCA can come up
> with something good?  Let's see.
>
> The background is that I'm coding an object in the Second Life virtual
> 3D world whose MO involves being placed on the ground somewhere on the
> X/Y grid of land, then exploring the owner****p of (X,Y) "cells" of
> land around it to find the boundaries of land consecutively owned by
> the same person as the start cell.  In other words, it's looking for
> the largest rectangle possible which (a) contains itself and (b)
> contains no cells owned by other people.
>
> The information it has available is:
>
> - The (X,Y) coordinates it's at.
> - The maximum and minimum possible values of X and Y (actually 0-255).
> - The owner****p of any given (X,Y) cell.
>
> The information needed from it:
>
> - The (X,Y) minimum and maximum vectors; in other words, the
> coordinates of the NE and SW corners of the largest rectangle of
> consecutive owner****p that includes its start point.  In simpler
> terms, the minimum and maximum values of X and Y that define the
> rectangle.
>

I'm just kibitzing here but how about something like this :
(read while waving hands wildly)

Start by choosing a cell near the middle.

Map the size of the largest contiguous square in each quadrant
around that cell. Call these first-order squares.

Notice that in each quadrant, the first-order square area applies
to every interior cell.

Next step would be to map 2nd-order squares on adjacent boundaries,
then 3rd-order, etc. and look for biggest rectangles. Maybe it would
be efficient to do a binary-split

Enough hand-waving already!
I'm leaving it up to you to work out the details!

Don