|
From: Mark R. D. <mdi...@la...> - 2003-06-29 17:10:32
|
Thomas Howe wrote:
> Those both seem fine. Keep in mind, though, that those only describe how to do range queries.
> Distance queries are a bit different. A distance query in a Moore neighborhood can be done fairly easily using one of the many graphics line drawing algorithms. This will be more difficult (I think, but I'm not quite sure) to determine in the VonNeumannTopology. So we should figure out how to caluculate those distances.
>
But, this is what I'm really talking about. I think its important not to
confuse continuous and descrete spatial concepts here. Both "range" and
"distance" in a discrete space are bound to a concept of "spatial
structure" which we currently define in the neighborhood rule. The rules
define which positions are "equidistant" to a particular position.
So in all the below cases the x's are all the same distance from "c"
(1), and the o's are all the same distance from "c" (2).
A Moore space
o o o o o
o x x x o
o x c x o
o x x x o
o o o o o
A vn space
o
o x o
o x c x o
o x o
o
A hex space
o o o
o x x o
o x c x o
o x x o
o o o
The euclidean or lineBresenham definition of distance is a mapping of a
"discrete grid" onto a "continuous space" and represents a space with
completely different "spatial structure" than the above spaces. The
space this describes is the one defined below.
http://mathworld.wolfram.com/Disk.html
http://mathworld.wolfram.com/ClosedDisk.html
The Hex space is the only "above" discrete space that most closely
matches the "disk" criteria, still the mapping of its distance function
onto the discrete grid would not be euclidean in nature due to the
staggering of the rows of the 2D storage grid. Its distance function
represents the following grid patterns for even and odd rows.
o o o o o o
o x x o o x x o
o x c x o o x c x o
o x x o o x x o
o o o o o o
I think the Bresenham and Euclidean concepts of space attempt to map
descrete coordinates conceptually to continuous space, they are useful
and I suspect very important in terms of mapping between the two, both
for visualization and for cartographic style "projection". I also
suspect that the different "above" descrete cases would "project" quite
differently (if at all!) onto a continuous realm and such functions are
of the same nature as your Bresenham function for Moore neighborhoods.
But I'm still not convinced that the particular Bresenham function is an
accurate "projection" onto the continuous realm for a "Moore structured"
space. I have an idea of what the accurate projections would be in such
cases, but don't have a set of equations that will define it yet.
> One particularly nice thing about those references, though is that it gives us a reference to use to name our topology lib (perhaps). See:
>
> http://mathworld.wolfram.com/Neighborhood.html
>
What are you thinking of for a name?
Cheers,
-Mark
|