On May 10, 12:23 pm, John Hatpin
<RemoveThisjfhop...@[EMAIL PROTECTED]
> wrote:
> 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.
>
> Caveats:
>
> 1. The owner might not own a neat rectangle of land. For example,
> they may have an L-shaped plot, in which case the solution should be
> the rectangle containing the intersection plus the larger branch of
> the 'L' (or one at "random" if they're identical; it doesn't matter
> which).
>
> Another example would be a sub-letting, where someone owns a large
> rectangle but has sold a smaller rectangle on their land to someone
> else - that smaller rectangle should not intersect with the solution.
>
> In fact, land is parcelled in rectangles, and sometimes divided or
> joined, so it's possible to end up owning a plot of any shape that can
> be put together with rectangles.
>
> 2. The object may be placed anywhere - even a corner, for example.
>
> 3. It takes a significant time to query the owner****p of each cell of
> land, so an optimised algorithm will examine owner****p as few times as
> reasonably possible. However, this should not be taken to extremes -
> for example, a brute force method that involved testing every single
> cell on the grid should be avoided; a binary-chop method to reduce the
> time taken to search in a given direction would be an unnecessary
> complication, and a simpler serial search preferred.
>
> 4. If there's a balance between searching inwards from 0 and 255 and
> outwards from the start position, the latter is preferred, since most
> plots of land are pretty small.
>
> 5. It's possible to own an entire region, from 0 to 255 on both axes.
I'm not sure anything but a brute force method of checking every cell
would work. Is it possible that someone would own just a few cells at
(50, 50) or something like that? How else would you find that but
checking every cell? You could query x from 0 to max, y from 0 to
max, find nothing, declare you own the whole block, and get sued for
random birdsong intrusion, if there are SL lawsuits. I'm sure there
are.
What's the problem with a brute force method? Is there a cost
associated with the query? 2^16 is a pretty small number of things to
ask a y/n question of, unless you're paying for each one or something.
--
Kevin
|
