John Hatpin <RemoveThisjfhopkin@[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).
Presumably this only applies if the object is placed in the intersection,
rather than one of the arms, right? If in one of the arms, then it has
to "find" that arm and not the other one it is not in?
>
> 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.
So then every coordinate inside the answer has to be queried, to guard
against enclaves.
>
> 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.
But the rectangles can't be divided below a certain quantum, right? In
other words, each valid X,Y coordinate is an integer, or at least a
rational number with a bound on the denominator?
>
> 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.
Can the answer be memorized once queried, so it case we need to know again
it can be retrieved from memory rather than re-queried? How much memory
can your object maintain?
> 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.
Because you have detect enclaves, I don't see how a binary method would be
of benefit, anyway.
....
>
> So what I'm doing is coding a moving sound generator, which, when
> placed on a plot, works out its boundaries and then continuously
> "flies" around the available space, emitting bird noises at random as
> it moves. You won't see it, it's invisible. It should never go into
> land owned by someone else - that's trespassing.
>
> It's that initial calculation of the boundaries that I'm working on
> here; once it has that rectangle of consecutively-owned land worked
> out, it can safely fly anywhere within the rectangle, giving it even
> coverage.
How im****tant is the even coverage? I'd be tempted to just make it fly
around at pseudo-random (or maybe depth-first systematically), checking
each non-checked square before entering it and remembering the result for
future use. That way it would cover all accessible land regardless of the
shape, although perhaps not evenly.
Xho
--
-------------------- http://NewsReader.Com/
--------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.
|
