4 
, N 
\ B x 
$5 A: Gb } 
Xa E EUM i 
  
  
  
  
  
(A, B)=a. 4 
lay-0 
? Ó 
A 
A 
all À 
1, 4 ^ 
ANE 
^N tp j 
~ ; 
b= ter 7 
  
ctions between two 
tance orders (such as 
s), directional orders 
' in front/behind to 
as one spatial object 
1s whether a spatial 
greatest lower bound 
pletion lattices, Fig.6 
ng from the normal 
asured by distances, 
NS 
1965], the concept of 
are fuzzy, since the 
ts, the distances or 
  
  
relations. 
| 1996 
directions between these subsets are difficult to be represented 
just by a single value. If we define the fuzzy membership values 
as the covering percentages of generated region areas (or point 
numbers and line lengths) by the dynamic intersection of sets in 
R^, we can find that the Hausdorff metric is just the special 
case with the fuzzy membership value equal to one. Based on 
the changes of the covering areas of regions ((or point numbers 
and line lengths) from an empty set to a complete set, we can 
estimate the fuzzy membership values from zero to one, then we 
can quantitatively derive the metric relations between subsets. 
For reasons of simplicity the distances and directions between 
closed sub-regions discussed in this paper only, related models 
for estimation of fuzzy membership functions are defined as 
follows: 
_A{[K@BANK, HARK NK,OB(A)]} 
ACK)+ACK,) 
  
o, (4) 
[13] 
A{[KORONK, H AK NK, DRO)]} 
eu A(K)+A(K,) 
  
where A{*} means covered area sizes by dynamic intersections 
with the parameters À and@ for distances and directions 
separately, the functions O<® (A)<l and O<Q (0)<1 with 
the parameters O<A<p(K,,K,) and 0<0<p(K,,K,)+r are 
called the size distribution functions [Chen, 1991; Serra, 1982]. 
An examples of distance relations between two spatial regions 
is shown in Fig.7. 
4.2. Distance Relations between Sets in Constrained Spaces 
In a space, there are often some obstacles such as rivers 
between objects. In this case, we cannot take a straight path if 
the path crosses the rivers; we should take the shortest path that 
does not cross the river except at bridges. The shortest path 
between a location p, and a point p, in a space E with a 
constrained set C is defined by the shortest path among all 
possible continuous paths connecting p, and p, that does not 
intersect the obstacle set C. In mathematics, this shortest path is 
called the "geodesic line" and its length denoted by the geodesic 
distance d, (p,.p;). If the obstacle set C cuts apart two points 
p, and p, to two separated sets, there is no continuous path 
linking p, and p,,inthis case we define di (p.p, )=+0 . As 
the descriptions in [Lantuejoul and Maisonneuve, 1984], the 
geodesic distance d,(p,,p,) satisfies all the properties of 
distance functions, so the space E defined with a geodesic 
distanced,is also a metric space. Similarly, the shortest 
distance between sets K, and K, in a given space X with a 
constrained set C also can be defined by the geodesic Hausdorff 
distance based on the geodesic morphological operations [Chen, 
1991; Lantuejoul and Maisonneuve, 1984]. 
The geodesic Hausdorff distance between sets is defined on the 
space and the constrained space C where each point is a non 
empty compact set of. R^. If K, and K, denote two non empty 
compact set in. A" (or equivalently two points in %), then the 
quantity: 
p, (KK, )einf(e:K, C 6 D; (K,), EoD (KY: [14] 
  
  
  
  
  
Fig.7. The distance relations between subsets and their size 
distribution functions. 
  
tr rrr rrr 
NN p NN NAN . S 
NARS, Pu 
x 
z 7 
VN x 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
Fig.8. The geodesic Hausdorff distances between sets constrained 
by set C. 
defines a metric p, on X , known as the geodesic Hausdorff 
metric. From equation [14], D; is the geodesic dilation denoted 
by D: (K,)-(zeC |B.(z,e) AK, mny , B. (z,e)-zeKH (z.p)&e) is 
the geodesic ball with a center z and a radius £ , and. p, is the 
radius of the smallest geodesic ball B, such that both K, is 
contained in the dilated set D2(K,) and K, is contained in the 
dilated set D_(K]) . 
In particular case when K, and K, are reduced to two points, 
the geodesic Hausdorff distance p,(K,,K,) coincides with the 
point geodesic distance. Similarly, we also can define the 
dynamic 9-intersection for the spatial relation of geodesic 
distance and fuzzy geodesic distances between partial separated 
subsets. The detail description of these formulas is omitted in 
this paper. An example is shown in Fig.8 for illustrating the 
notation of the geodesic and fuzzy geodesic Hausdorff distance 
between two compact sets. 
5. ALGORITHMS AND EXAMPLES 
5.1. Algorithms 
To determine the Hausdorff distances or directions between 
spatial objects in layer-based vector or raster GIS environments, 
the main problem is how to realize the operations of 
morphological dilation and logical intersection. The dilation by 
the structure elements of disks or angular bearings can be 
treated as general and oriented buffer operations separately, and 
logical intersections can be implemented by overlay operations 
in GIS environments. Since both buffering and overlay are basic 
data analyzing functions included in many commercial GIS 
software, the implementation of the Hausdorff distances or 
directions changes to a very easy problem. In a raster GIS 
environment, the main problem is how to considerate the 
different distance functions when we generate buffer zones. For 
square grid raster data, generally used distance functions can be 
separated as 4-connection, 8-connection and quasi-Euclidean 
distances in 2-D digital spaces. The detail descriptions of 
algorithms for determining the Hausdorff distances can be 
103 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996