At 04:22 PM 4/17/01 +0200, Roeland van der Spek wrote:
>1. create points from the nodes in the polygons that represent the bodies of
>water
>2. use Triangulator to create Thiessen polygons around these newly created
>nodes/points
>3. calculate the distance to the node that is in the same Thiessen
>polygon as the point you want to calculate the distance from....
Unfortunately, this nice idea doesn't really work either.
Recall that the question was to assign to each of many points its distance
to the nearest "body of water"--a polygon, presumably. One approach is to
divide the plane into regions; each region consists of all points closest
to a given body of water. The problem is then solved with a
point-in-polygon solver followed by a quick point-to-polygon distance
calculation.
This idea extends the notion of Thiessen (Voronoi, Dirichlet)
polygon. However, it is a distinctly different construct: in particular,
the region boundaries usually contain parts of parabolas and so are not
even polygons in the usual sense.
For example, consider a long straight stretch of river, part of whose
boundary is represented by a line segment between two widely separated
points. Let's call this segment "D". Suppose that nearby is a pond or
lake (such as a cutoff oxbow). To simplify the analysis, imagine this pond
is so small that we can practically represent it as a single point
"F". (This simplification still produces the correct conclusions.)
Locally, the generalized Thiessen region corresponding to D and F is
bounded by the locus of points equidistant from D and F. This, by
definition, is a parabola with directrix D and focus F. Since parabolas
are everywhere non-linear, and (the usual) Thiessen polygons always have
piecewise linear boundaries, NO Thiessen polygon software will generate a
perfectly correct solution.
In particular, the "Triangulator" approach described above will produce
highly erroneous results in all such areas where a long line segment
represents a portion of a polygon's boundary.
One work-around is to represent polygon boundaries not just by their nodes,
but by their nodes together with a collection of tightly-spaced points
marching around their perimeters. This in effect creates piecewise linear
approximations to the parabolic arcs in step 2 above. It will also greatly
increase time and RAM requirements for the solution.
It's no longer as "easy as 1-2-3," but it can be done. (I have taken this
approach in ArcView, which doesn't do a bad job at all.) However, the
approximation inherent in the method, together with its complexity, suggest
that a raster solution will be just as good as this vector approach.
Preparata and Shamos (Computational Geometry: An Introduction,
Springer-Verlag, 1985) indicate that an algorithm has been developed to
compute the generalized Thiessen regions, but they do not provide
references. I would be grateful to hear from anyone who can supply a
reference or code, in any language.
--Bill Huber
Quantitative Decisions
_______________________________________________________________________
List hosting provided by Directions Magazine | www.directionsmag.com |
To unsubscribe, send e-mail to [EMAIL PROTECTED] and
put "unsubscribe MapInfo-L" in the message body.
