At 03:43 PM 4/11/01 -0400, a respondent wrote:
>At first sight, if your bodies of water are closed polygons, you could
>determine which body of water is the closest of a particular point. To
>narrow the search, you could calculate the distance between your point and
>the centroid of each body of water and keep, say, the 10 closest ones.
This clever idea will fail in some exceptional cases, such as when the
bodies of water are long rivers: New Orleans, for instance, is right on the
Mississippi River, but it is closer to the centroids of hundreds of
tributaries (and hundreds of other rivers, lakes, and bayous unconnected to
the Mississippi) than it is to the centroid of the river itself.
The computational geometry literature contains many efficient and correct
solutions to the problem of finding the distances from each point to its
nearest polygon. One of them, a vector approach, generalizes the Thiessen
polygon construction; references to this are in Preparata & Shamos'
book. Another, a raster approach, constructs the distance grid for the
collection of water body polygons. After this preliminary computation,
finding the required distances is very rapid: you just interpolate within
the distance grid. Other approaches use quadtrees or other spatial data
structures precomputed from the polygons. Most GIS software has one (or
more) of these solutions built in to its basic functionality.
>Since the distance between a point and a
>line is proportional to the area of the triangle formed by the point and the
>two nodes of the line,
This statement assumes the perpendicular from the point to the line falls
between the two nodes, which will usually *not* be the case.
The general formula is easily expressed in vector notation. Let the
endpoints of the line segment be a and b and let the point be p. Let v =
b-a. Each of a, b, p, and v is a vector. Compute t = inner product of v
with (p-a) and v2 = inner product of v with itself; t and v2 are
numbers. If t <= 0, the closest point to p is a and the distance is
|p-a|. If t >= v2, the closest point to p is b and the distance is
|p-b|. Otherwise, v2 <> 0, the point c = a + t*v/v2 is the closest point
to p along the line segment between a and b, and the distance is |p-c|.
>I would use the determinant method to calculate it.
>This method works as follow: calculate the determinant of this matrix:
>xp yp 1
>x1 y1 1
>x2 y2 1
None of these possibilities can be expressed by a determinant based on the
point and node coordinates alone: a square root operation is unavoidable
(except for some special configurations). This is clear when you consider
the effect of changing the units of measurement. If all coordinates are
multiplied by z, to be consistent the answer had better be multiplied by
|z|; however, the determinant above (or any similar looking expression)
will be multiplied by z^2.
--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.
