Bejaoui Lotfi

Pinet François

Bedard Yvan

Schneider Michel

Qualified Topological Relations between Spatial Objects with Possibly Vague Shape

Keywords: Fuzzy spatial objects, topological relations, partial fuzziness, spatial query, integrity constraints, integration à , max

Broad boundaries are generally used to represent objects with fuzzy spatial extents. This concept is typically defined as a polygonal zone that should respect both connectedness and closeness conditions. Therefore, some real configurations, like regions with a partially broad boundary (e.g., a lake with rocker and swamp banks), are considered invalid. The main objective of this paper is to represent different levels of spatial fuzziness and consider these levels during the identification of topological relations. Then, we define a fuzzy spatial object as a minimal extent and a maximal extent. Topological relations are identified by a 4-Intersection matrix that describes four subrelations between the minimal and the maximal extents. For fuzzy regions, 242 relations are distinguished and classified into 40 clusters. This approach permits the representation of partially fuzzy objects as well as the expression of integrity constraints and spatial queries with different levels of fuzziness.

Introduction

To satisfy the requirements of several categories of users, Geographic Information Systems (GIS) and spatial databases provide tools to store, retrieve, analyze, and display spatial data. Ensuring their usability requires controlling the spatial data quality, which can be degraded by several types of imperfections. Several approaches [START_REF] Smithson | Ignorance and Uncertainty: Emerging Paradigms[END_REF], Fisher 1999[START_REF] Mowrer | Accuracy (Re)assurance: Selling Uncertainty Assessment to the Uncertain[END_REF], Duckham et al. 2001) proposed different categorizations of data imperfections that are generally caused by the complexity of reality and limitations of instruments and processes used in the measurements [START_REF] Bédard | Uncertainties in Land Information Systems Databases[END_REF]. Moreover, inappropriate spatial data representations can also be another source of data quality degradation [START_REF] Yazici | Semantic data modeling of spatiotemporal database applications[END_REF][START_REF] Shu | Uncertainty of Geographic Information and its Support in MADS[END_REF], Dilo 2006). Spatial reality is generally forced to be represented by crisp spatial object types (i.e., points, lines, and regions), whereas many spatial objects are inherently fuzzy (e.g., forest stand, pollution zone, valley, or lake). Fuzziness occurs when it is difficult to distinguish an object's boundaries geometry components from other spatial objects. Using crisp spatial object types to represent fuzzy spatial objects entails a clear gap between the spatial reality and its formal representation in databases and GIS [START_REF] Cheng | Formalizing fuzzy objects from uncertain classification results[END_REF][START_REF] Yazici | Semantic data modeling of spatiotemporal database applications[END_REF].

Pertinent solutions were found to overcome the "classical" sources of spatial data quality degradation [START_REF] Bédard | Uncertainties in Land Information Systems Databases[END_REF], Goodchild 1995, Guptill and Morisson 1995[START_REF] Ubeda | Topological Error Correcting in GIS[END_REF], Frank 2001[START_REF] Van Oort | Spatial data quality: from description to application[END_REF], Devillers et al. 2007, Duboisset et al. 2007). Several approaches [START_REF] Burrough | Geographic Objects with Indeterminate Boundaries[END_REF][START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF][START_REF] Clementini | Approximate topological relations[END_REF], Erwig and Schneider 1997[START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF][START_REF] Pfoser | Indeterminacy and Spatiotemporal Data: Basic Definitions and Case Study[END_REF], Dilo 2006) have studied specificities of fuzzy spatial objects to determine their appropriate representation. A review of the literature in this domain stresses that current GIS and spatial database systems do not offer the specific structure to formally represent this type of object (as pointed by Clementini and Di Felice 1997 ten years ago). With regard to this problem, researchers are increasingly more motivated to model spatial fuzziness in order to: (1) reduce the gap between the geographic reality and the spatial models [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF], (2) provide formal modeling tools to represent spatial fuzziness [START_REF] Yazici | Semantic data modeling of spatiotemporal database applications[END_REF], and (3) specify spatial queries involving fuzzy spatial objects (Erwig and Schneider 1997). In the same way, the spatial data integration requires the extraction of heterogeneous representations of the same objects from different data sources. The main difficulty lies in choosing one of them when no information exists about their quality [START_REF] Rodriguez | Inconsistency Issues in Spatial Databases[END_REF]. By using a spatial model that supports spatial fuzziness, it becomes possible to merge different representations in such a way that the integration result looks like a fuzzy spatial object. For example, figure 1 shows a spatial object that has the representation A in a first source and the representation B in a second one. The integration result can correspond to one fuzzy geometry made up of A and B (figure 1). The intersection of A and B corresponds to the certain part (i.e., the part that exists in both representation A and representation B) or the minimal extent of the spatial object. However, the union is the maximal extent that the object can fill; it groups the certain and the uncertain parts (i.e., a geometry part is uncertain when it does not exist in all candidate representations for the integration) of the geometry. Indeed, there are strong and different motivations to present pertinent solutions in order to adequately model the spatial fuzziness. To model fuzzy spatial objects, researchers were firstly inspired by the modeling of crisp spatial objects. In general point-set topology (Egenhofer and Herring 1990), crisp spatial objects are typically decomposed into three mutually disjoint topological invariants: an interior, a boundary, and an exterior. Several approaches [START_REF] Clementini | Approximate topological relations[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF][START_REF] Reis | Topological relations using two models of uncertainty for lines[END_REF]) extend the crisp models by identifying other topological invariants for the fuzzy spatial objects. For example, Clementini and Di Felice [START_REF] Clementini | Approximate topological relations[END_REF] distinguish three topological invariants for fuzzy regions: an interior, a broad boundary (i.e., a two -dimensional boundary), and an exterior. In this approach, the fuzziness is correlated to the broad boundary, which should respect the closeness and the connectedness conditions [START_REF] Clementini | Approximate topological relations[END_REF]Di Felice 1997, Xinming 2004). Thus, any representation that does not verify these conditions is considered invalid. Nonetheless, the fuzziness can also characterize only some parts of an object's geometry. For example, figure 2 shows a lake surrounded by rocker and swamp banks at the same time (figure 2). We denote this kind of feature as partially fuzzy spatial objects that cannot be represented by existing models. Then, the main questions are: How is it possible to define an exact model where different levels of fuzziness could be considered? How can we retain this expressivity during the specification of topological relations between such objects? The first objective of this paper is to allow the representation of three levels of fuzziness: crispness, partial fuzziness, and complete fuzziness. Modeling fuzzy spatial objects requires a framework for identifying topological relations. The second objective is to consider the different levels of spatial fuzziness in the identification of topological relations between fuzzy spatial objects. In several studies [START_REF] Clementini | Approximate topological relations[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF][START_REF] Reis | Topological relations using two models of uncertainty for lines[END_REF], topological relations can be identified by enumerating the intersections between the topological invariants of the fuzzy objects involved. For each model, the number of relations depends upon the number of topological invariants. In this work, we look for an expressive model in which it is possible to specify the fuzziness level of the topological relation

Maximal extent

Minimal extent

Rocker banks Swamp banks instances. We think that it would be pertinent for the user to know whether objects are weakly or strongly disjoint. Accordingly, the third specific objective of this work is to classify the topological relations according to their fuzziness level.

The remainder of the paper is organized as follows. In section 2, we present previous work on the modeling of fuzzy spatial objects and their topological relations. In section 3, we present three fuzzy spatial object types: fuzzy point, fuzzy line, and fuzzy region. Then, section 4 gives a proposition based on the 9-Intersection model (Egenhofer and Herring 1990) in order to identify the topological relations among fuzzy spatial objects. The model is applied to fuzzy regions, and their topological relations are studied in detail in the appendix. As a result of this approach, 242 relations can be distinguished through a 4-Intersection matrix. Section 5 proposes a hierarchical clustering of topological relations between fuzzy regions, and section 6 explains how to use our approach to express spatial queries and integrity constraints. In section 7, our model is compared with existing approaches [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF][START_REF] Clementini | Approximate topological relations[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]). Finally, section 8 presents our conclusions and discusses future research.

Previous work

Spatial vagueness

According to (Erwig and Schneider 1997, Hazarika and Gotts 2001[START_REF] Pfoser | Indeterminacy and Spatiotemporal Data: Basic Definitions and Case Study[END_REF], spatial vagueness can characterize the position or shape of an object's spatial extent. From this perspective, the shape fuzziness refers to the difficulty of distinguishing one object's shape from other objects' shapes. Fuzziness is an intrinsic property of an object that certainly has an extent in a known position but cannot or does not have a well-defined shape (Erwig and Schneider 1997). For instance, a region can be fuzzy when it is surrounded by broad instead sharp boundaries. Spatial vagueness can also characterize well-defined (or crisp) objects when there is uncertainty about object positions despite their sharp shapes; we refer to this scenario as positional vagueness. Figure 3 shows this categorization of spatial vagueness into "shape fuzziness" and "positional vagueness". In this paper, we only deal with the formal representation of fuzzy spatial objects (i.e., objects that have fuzzy shapes) and the topological relations between them. In general, we distinguish between at least two categories of models used to represent spatial vagueness. In the first category, crisp spatial concepts are transferred and extended to formally express spatial vagueness; we speak about exact models as explained in the next section [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF][START_REF] Clementini | Approximate topological relations[END_REF], Erwig and Schneider 1997). In the second category, three principal mathematical theories are generally used: (1) models based on the fuzzy logic [START_REF] Zadeh | Fuzzy sets[END_REF]) (e.g., [START_REF] Altman | Fuzzy set theoretic approaches for handling imprecision in spatial analysis[END_REF][START_REF] Burrough | Fuzzy mathematical methods for soil survey and land evaluation[END_REF][START_REF] Brown | Classification and boundary vagueness in mapping presettlement forest types[END_REF][START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF], Hwang and Thill 2005, Dilo 2006), which can be used to represent continuous phenomena such as temperature, (2) models based on rough sets (e.g., [START_REF] Ahlqvist | Using Rough classification to Represent Uncertainty in Spatial Data[END_REF][START_REF] Varzi | Imprecision in finite resolution spatial data[END_REF], which represent the fuzzy spatial objects as a pair of

Spatial vagueness

Shape fuzziness

Positional vagueness approximations (upper and lower approximations), and (3) models based on probability theory (e.g., [START_REF] Burrough | Fuzzy mathematical methods for soil survey and land evaluation[END_REF]Frank 1996, Pfoser et al. 2005), which is principally used to model errors of position and attributes. In the next section, we present works that formally define fuzzy spatial objects.

Formal definitions of fuzzy spatial objects

Definitions based on exact models.

The Egg-Yolk theory [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF] is an extension of the RCC (Region Connection Calculus) model [START_REF] Randell | Modelling topological and metrical properties of physical processes[END_REF]Cohn 1989, Cohn et al. 1997), it introduces the concept of regions with large boundaries. In fact, a fuzzy region is composed of two crisp regions. The inner region called «yolk » (i.e., the certain part of the geometry), and it is surrounded by an outer region called "white" (i.e., the large boundary or the uncertain part of the geometry). The union of the "yolk" and the "white" corresponds to the "egg". Because points and lines are ignored in RCC model, their fuzziness is not studied in this approach. In addition, fuzzy regions with empty "yolk" or empty "egg" are not admitted. Thus, the crisp regions cannot be represented through the Egg-Yolk theory.

In the same way, Clementini and Di Felice [START_REF] Clementini | Approximate topological relations[END_REF] define the regions with broad boundaries based on the general point-set topology (Egenhofer and Herring 1990). Thus, a region with a broad boundary A is made up of two simple crisp regions A 1 and A 2 , where A 1 ⊆ A 2 . The broad boundary represents the fuzziness, and it is equal to the closure of their difference

2 1 A A A - = ∆
. In this approach, A 1 and A 2 should be topologically consistent; this means that they should be bounded, regular, and closed sets in 2 ℜ [START_REF] Clementini | Approximate topological relations[END_REF]. Moreover, the authors distinguish two kinds of fuzzy lines: broad lines (i.e., all of the line is large) and lines with broad boundaries (i.e., the line's endpoints are ill-defined). Xinming [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]) extends this approach and proposes a more detailed formal definition of fuzzy regions, where he distinguishes four mutually disjoint components: the interior, the boundary's interior, the boundary's boundary, and the exterior (figure 4). The condition A 1 ⊆ A 2 in [START_REF] Clementini | Approximate topological relations[END_REF] does not exist in (Erwig and Schneider 1997). In fact, Erwig and Schneider (Erwig and Schneider 1997) are interested in another kind of vagueness, where a vague region is a composed geometry. The geometry's components belong to a pair of subsets. First, the kernel subset contains the subregions definitely belonging to the vague region. Second, the boundary subset contains the subregions possibly belonging to the vague region. Likewise, the vague points and the vague lines are respectively defined as a pair of subsets of points and lines. Crisp spatial objects can be expressed through this model when the boundary subset is empty. Figure 5 gives an example of a vague region A, in which the white subregions compose to the boundary subset and the gray ones compose the kernel. 2.2.2 Models based on mathematical approaches. [START_REF] Roy | Spatial relations between indeterminate regions[END_REF] deal with indeterminacy, which is defined as knowledge vagueness. They define an indeterminate region through rough sets [START_REF] Pawlak | Rough sets: present state and further prospects[END_REF]). An indeterminate region is composed of a lower and an upper approximation. The difference between these approximations represents the fuzzy part of the region. When this difference is empty, the region is crisp because the two approximations are equal [START_REF] Roy | Spatial relations between indeterminate regions[END_REF].

Fuzzy sets theory is also used to represent fuzzy spatial objects [START_REF] Robinson | Fuzzy Set Theory Applied to the Mixed Pixel problem of Multi-spectral Land Cover Databases[END_REF][START_REF] Altman | Fuzzy set theoretic approaches for handling imprecision in spatial analysis[END_REF][START_REF] Burrough | Fuzzy mathematical methods for soil survey and land evaluation[END_REF][START_REF] Zhan | Topological relations between fuzzy regions[END_REF][START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF][START_REF] Yongming | A Fuzzy Sets Theoretic Approach to Approximate Spatial Reasoning[END_REF], Dilo 2006). Zhan [START_REF] Zhan | Topological relations between fuzzy regions[END_REF] and Dilo (Dilo 2006) interpret a fuzzy spatial object as a fuzzy subset. In [START_REF] Zhan | Topological relations between fuzzy regions[END_REF], the membership function of the fuzzy spatial object is decomposed to n cuts -α (an cut -α is the set of points with a membership value α or higher (e.g. Godjjevac 1999)) in order to facilitate its interpretation. Xinming [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]) defines the fuzzy spatial objects in two different ways. The first definition should respect the properties of the crisp topological space. The second definition should respect topological properties in a fuzzy topological space. In this context, the concept of fuzzy topology is a generalization of crisp topology, in which the sets belonging to the universe are fuzzy (i.e., the membership value is α, where 1 0 ≤ ≤ α

). Schneider [START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF] presents formal definitions of fuzzy spatial object types through fuzzy subsets. For example, a fuzzy region is defined as a generalization of a crisp region in which an arbitrary point of space has a partial membership to the region [START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF]).

In the next section, we highlight some approaches that study the specificities of the topological relations between fuzzy spatial objects.

Topological relations between fuzzy spatial objects

Topological relations are very important in GIS, especially in the specification of integrity constraints [START_REF] Ubeda | Topological Error Correcting in GIS[END_REF] and spatial queries. These relations are based only on the shape of objects and are totally independent of both the coordinates system and geometric transformations. The use of special shapes to express shape fuzziness should imply a different approach for identifying their topological relations. In the crisp context, several models (Egenhofer and Herring 1990, Egenhofer and Franzosa 1991, Mark and Egenhofer 1994, Cohn et al. 1997) studied the specification of topological relations in GIS and spatial databases. These models are based on two main approaches: general point-set topology (Egenhofer and Herring 1990) and mereology 1 [START_REF] Varzi | Imprecision in finite resolution spatial data[END_REF]. First, the 9-interesections model (Egenhofer and Herring 1990) is an extension of the 4-Intersection model (Egenhofer 1989). Based on point-set topology, the 9-Intersection model distinguishes 8 relations between two simple regions (Disjoint, Meet, Overlap, Contains, Inside, Equal, Covers, Covered by), 36 between two simple lines, 19 between a simple region and a simple line, 2 between two points, 3 between a point and a simple line, and 3 between a point and a simple region. In the context of mereology, a first model called RCC-5 [START_REF] Randell | Modelling topological and metrical properties of physical processes[END_REF]) distinguished 5 1 The region is defined as the elementary component of the space, i.e. points and lines are not considered A topological relations among two simple crisp regions. This model was then extended to distinguish 8 topological relations, and it became known as RCC-8 (Cohn et al. 1997).

In the fuzzy context, topological relations can be specified by extending the RCC and 9-Intersection models [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF][START_REF] Clementini | Approximate topological relations[END_REF], Erwig and Schneider 1997[START_REF] Roy | Spatial relations between indeterminate regions[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]). Erwig and Schneider (Erwig and Schneider 1997) use a three-valued logic to underline the spatial fuzziness. Then, an intersection between two topological invariants can be true, false, or maybe (i.e., when the boundary subset participates in the relation). In [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF] With this approach, only 46 combinations correspond to the 46 possible topological relations drawn in [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF]. Figure 6 presents the relation number 15 in [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF]. The main advantage of this approach is its simplicity in identifying the topological relations. However, point, lines, and crisp regions are not covered.

Figure 6. Identification of topological relations in [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF] Clementini and Di Felice [START_REF] Clementini | Approximate topological relations[END_REF] studied approximate topological relations, which correspond to the topological relations between regions with broad boundaries. In fact, they use a 3*3-matrix, in which the sharp boundary is replaced by a broad boundary. After considering a set of consistency rules for the matrix (i.e., twelve rules to eliminate a matrix that cannot be drawn) [START_REF] Clementini | Approximate topological relations[END_REF], only 44 relations can be distinguished and drawn among two simple fuzzy regions. These relations can then be grouped into 17 clusters, for which a conceptual-neighborhood graph was drawn. This approach can be very interesting when it is necessary to coarsely identify the topological relations between fuzzy regions. However, the model is not sufficient when the needs are more specific and the user has a clear idea regarding the relation between fuzzy regions. For example, figure 7 shows an example of two different relations absorbed by the same cluster and identified through the same matrix. [START_REF] Clementini | Approximate topological relations[END_REF] In the same way, Reis et al. [START_REF] Reis | Topological relations using two models of uncertainty for lines[END_REF]) use Clementini's model [START_REF] Clementini | Approximate topological relations[END_REF] in order to identify the topological relations between fuzzy lines. After considering the same 12 conditions defined in [START_REF] Clementini | Approximate topological relations[END_REF], 5 topological relations are identified between two broad lines and 77 between two lines with broad boundaries.

Xinming [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]) presents an extension of the 9-Intersection model that identifies more topological relations than that of [START_REF] Clementini | Approximate topological relations[END_REF]. He identifies

PO (Egg(A), Egg(B)) PPI (Egg(A), Yolk(B)) PO (Yolk(A), Egg(B)) PO (Yolk(A), Yolk(B)) 0 0 1 0 1 1 1 1 1 A B Meet (2) (1)
topological relations through a 4*4-matrix. Indeed, he distinguishes 152 topological relations and presents their correspondent matrices (see the example in the figure 8). The absence of relation clustering is the main limitation of the model. The model becomes useless in practice, however, since it is very difficult to easily and intuitively distinguish all of these relations. Furthermore, Xinming [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF] does not distinguish between the inner and outer boundaries. Hence, many relations cannot be specified through a 4*4-matrix.

Figure 8. Identification of topological relations in [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF] Fuzzy sets' theory is also used to identify the topological relations between fuzzy spatial objects [START_REF] Zhan | Topological relations between fuzzy regions[END_REF][START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF], Dilo 2006). A topological relation in [START_REF] Zhan | Topological relations between fuzzy regions[END_REF]) is called R (i.e., a parameter used to replace the eight relations of the 4-Intersection model (Egenhofer 1989)). For each pair of cuts -α of considered regions, a subrelation r is identified. Then, the possibility of the global relation R is deduced from the number of subrelations r that arise between the different cuts -α . This approach is easy to use in practice, but it presents some complexity when the cuts -α are non-uniformly distributed between 0 and 1. In the same way, Dilo (Dilo 2006) identifies six possible topological relations (i.e. Disjoint, Touches, Crosses, Overlaps, Within, and Equal) between two vague spatial objects. A topological relation is defined based on fuzzy operations (e.g., union, intersection, absolute difference, and bounded difference) applied to fuzzy subsets that represent vague spatial objects. According to Dilo (Dilo 2006), many topological relations may exist at the same time with different Truth degrees (e.g., Overlap(A, B) with the Truth degree = 0,2; Meet(A,B) with the Truth degree = 0,3; Disjoint(A, B) with the Truth degree = 0,5).

Problem statement

The exact models presented earlier [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF][START_REF] Clementini | Approximate topological relations[END_REF], Erwig and Schneider 1997[START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF][START_REF] Reis | Topological relations using two models of uncertainty for lines[END_REF] have the advantage of explicitly distinguishing objects' topological invariants. Through this discrete viewpoint of space, the specification of topological relations can be improved [START_REF] Clementini | Approximate topological relations[END_REF]. For these reasons, we propose an exact model in order to achieve objectives. Nevertheless, we think that the existing models do not distinguish between different levels of fuzziness and are not sufficiently expressive to represent partial fuzziness. In reality, a fuzzy spatial region is not always surrounded by a large boundary everywhere. For example, a lake boundary can be broad in some locations and sharp in some others. This situation cannot be represented by existing exact models, because the connectedness condition is violated. The same problem is present for lines. Only two cases of fuzziness are distinguished in lines (cf. section 2.2.1), but a line can easily have a partially fuzzy interior. Moreover, the studied models are not sufficiently expressive in terms of topological relations since there is no distinction between the inner and outer boundaries for a fuzzy region. Some work tries to offer more expressivity by increasing the number of topological invariants [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]). Nevertheless, the absence of relation clustering limits their practical use. Indeed, the main research questions of our paper are the following:

0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1 A B B° llB lB° B -- A° llA lA° A --
A° : the interior of A lA°: the boundary 's interior llA : the boundary's boundary A --: the exterior with 1-How can we obtain more expressive definitions of the fuzzy spatial object types through an exact model? How can we represent partial fuzziness? 2-What are the topological relations between fuzzy spatial objects? How is it possible to identify topological relations between objects that have different levels of fuzziness? How can we formally identify these relations? 3-How can we classify the topological relations between fuzzy regions in order to facilitate their use in practice? How could resulting clusters reflect the fuzziness level of a topological relation?

Fuzzy spatial objects

In general, there is no agreement regarding the appropriate formal definition of fuzzy spatial objects, because fuzziness can be interpreted in different ways. It is not the objective of this work to unify these interpretations. We are interested in proposing an expressive and easy definition of fuzzy spatial objects through an exact model. In our approach, we transfer the Egg-Yolk's model into point-set topology context in order to both consider points and lines and permit the representation of partially fuzzy objects. From this perspective, we distinguish three fuzzy spatial object types: fuzzy points, fuzzy lines, and fuzzy regions. Each one of these is composed of n crisp object types (i.e., point, line, and region) distributed into a pair of sets called (1) the minimal extent and (2) the maximal extent (figure 9). Figure 9 presents an example of fuzzy points, fuzzy lines, and fuzzy regions. A fuzzy point is a zone that we approximate to a crisp region containing all of positions that the point can possibly fill. The minimal extent of point is equal to its maximal extent because the fuzziness concerns a unique topological invariant: the interior (cf. section 3.1 for more details). For a fuzzy line (cf. section 3.2), the minimal extent is the union of the linear parts. However, its maximal extent can contain some fuzzy parts (i.e., presented as fuzzy points in figure 9 (b)) at which the line can have any shape. For a fuzzy region (cf. section 3.3), the fuzziness concerns the boundary.

The minimal extent refers to the geometry when the boundary is as close as possible (i.e. it is drawn around the area which certainly belongs to the region). The maximal extent is the geometry of the object when the boundary is as far away as possible (i.e. it is drawn around the area which contains all of points possibly belonging to the region). Generally, the minimal extent refers to the geometry's parts definitely belonging to the spatial object. The maximal extent corresponds to the object's geometry when fuzziness is taken into account and added to the minimal extent. Outside of the maximal extent, there are no spatial points that can possibly belong to the object. The number n of crisp object types composing the fuzzy spatial object type is 1 for a fuzzy point (i.e., a zone that we represent as a crisp region composed of the quasi-totality of possible positions of the point (cf. section 3.1)), 2 for a fuzzy region (i.e., two crisp regions (cf. section 3.3)), and n for fuzzy lines (i.e., 1 or n points of the line are fuzzy (cf. section 3.4)). For example, a fuzzy region corresponds to a pair of crisp regions that respectively represent the minimal and maximal extents. This general definition of fuzzy spatial objects is based on the following principles: 1-A fuzzy spatial object is a generalization of a crisp spatial object. 2-The minimal and the maximal extents are made up of crisp spatial object types. Only the combination of two extents corresponds to the fuzzy spatial object. 3-For the minimal and the maximal extents, the topological invariants should be mutually disjoint.

The first principle means that the spatial extent of a fuzzy object is crisp when its minimal extent is equal to its maximal one. The second principle requires that the minimal and maximal extents verify the topological consistency conditions of the crisp spatial object types (e.g., a crisp region should be connected). Finally, the third principle permits the identification of topological relations based on the intersections between the topological invariants of the minimal and maximal extents of two fuzzy spatial objects. In the next sections, we present our definitions of fuzzy point, fuzzy line, and fuzzy region.

Fuzzy point

In the crisp context, a point p(x, y) is a 0-dimensional object type that represents one position (x, y) in space. The only topological invariant composing the shape of a crisp point is its interior. Because a point does not have a boundary (the boundary of an object with N dimensions has N-1 dimensions), the fuzziness can characterize only the interior and thus the point itself. Semantically, a fuzzy point occurs when an intrinsic property of the point or a lack of knowledge does not permit certainty regarding its position. For such a case, the spatial extent of the object is typically replaced by a zone that we represent as a crisp region composed of the family of positions that the point can fill (figure 10). The closure2 of the crisp region represents an infinity of possible positions for the point. Consequently, a fuzzy point does not have a minimal extent; it only has a maximal extent.

Simple Crisp point Fuzzy point To provide an example of a fuzzy point, consider an application to help the fire brigades in their interventions. Generally, a fireman cannot precisely localize the fire source. However, he can draw an area in which the fire source should exist. This intervention area corresponds to a fuzzy point and can be represented through our model. It is clear that the size of the region representing the fuzzy point depends on the fuzziness level (i.e., a larger region refers to a fuzzier point).

Fuzzy line

A simple crisp line is a one-dimensional object type made up of an interior limited by two endpoints. The boundary of a crisp line corresponds to its endpoints, whereas the interior is the set of points connecting them. The fuzziness can characterize any point of the line. Consequently, the line boundary can be partially or completely fuzzy while the interior remains well-defined; we then speak about lines with fuzzy boundaries. In the same way, the interior can be partially or completely fuzzy while the endpoints are well-defined; we then speak about lines with partially and completely fuzzy interiors, respectively (figure 11). The extreme case of line fuzziness arises when all topological invariants of the line (i.e. the interior and the boundary) are fuzzy (figure 11). Thus, a completely fuzzy line corresponds to a crisp region that represents the set of positions that the line can fill. However, a completely crisp line is a particular case of fuzzy lines, for which all of the interior and both endpoints are well defined. The different cases of line fuzziness can be combined as presented in figure 11.

To underline the different levels of line fuzziness, we use four adverbs: (1) weakly, (2) fairly, (3) strongly, and (4) completely. The term "weakly" indicates that one of the topological invariants is partially fuzzy. The term "fairly" reflects either complete fuzziness of one of topological invariants or the case where the interior and endpoints are partially fuzzy at the same time. The term "strongly" specifies complete fuzziness for one of topological invariants and partial fuzziness for the second one. Finally, the term "completely" is used to express total fuzziness of the line's components. Figure 11 shows a symmetrical matrix, in which fuzziness increases from "none" in the upper-left cell to "completely" in the lower-right cell through a progression including "weakly", "fairly," and "strongly". In our model, a fuzzy line is typically composed of two-dimensional parts that correspond to the line's fuzzy points and one-dimensional parts that represent the minimal extent of the line. Thus, the maximal extent is the union of the one-dimensional and two-dimensional parts. The interior of maximal extent corresponds to the union of the interiors of the one-dimensional and two-dimensional parts. In the same way, the boundary of the maximal extent is the union of the boundary of the one-dimensional and two-dimensional parts. Figure 12 In our approach, we look for the most expressive model possible in terms of specification of the topological relations. Consequently, we focus on the definition of the topological invariants for the maximal max L and the minimal min L extents. For each one, we distinguish an interior and a boundary that can be empty according to the configuration of the line (figure 12). From a point-set topology view point, a simple fuzzy line should verify the following conditions:

1-Each one-dimensional part of the simple fuzzy line is connected. 2-Each one-dimensional part of the simple fuzzy line is not self-intersecting.

3-Each one-dimensional part of the simple fuzzy line does not form a loop. 4-Each two-dimensional part verifies the conditions defined for a fuzzy point (section 3.1). 5-If the endpoints are fuzzy, they do not overlap with each other.

The three first conditions are those defined for a crisp line in the general point-set topology. Then, we apply these conditions to each linear part of the fuzzy line. The fourth condition requires that every fuzzy point on the interior or the endpoints of a line respect the topological conditions of a crisp region applied to a fuzzy point (section 3.1). The last condition is defined to eliminate any risk of self-intersection or loop configurations. Figure 13 shows some cases of lines that are invalid according to our model.

Non regular interior of maximal extent Self-intersecting line

The line forms a loop

The endpoints can be identical In the next cases, we give two examples of fuzzy lines:

• A strongly fuzzy line with only one crisp end point : The Bermuda triangle is a region in the Atlantic Ocean where some aircrafts and surface vessels have disappeared. We suppose that we have been appointed to redraw the trajectory of an engine that has disappeared. We will quickly discover that the only certain information is the last position of the engine before the communication interruption. In fact, this point refers to the minimal extent of the line. Far from this point, the trajectory can have any shape and position inside the fuzziness area. Indeed, our model is sufficiently expressive to represent this fuzziness case.

• A fairly fuzzy line with two crisp endpoints : We suppose that an aircraft disappeared for some time from radar screens. After that, the communication with the aircraft returns to normal and the engine arrives at its destination. In this case, the aircraft trajectory is composed of two crisp endpoints. However, the interior is partially fuzzy, because the trajectory can take any unpredictable shape inside the dangerous zone.

Fuzzy region

A crisp region is a two-dimensional spatial object type in which the shape is typically composed of an interior, a boundary, and an exterior. For a region, shape fuzziness occurs when there is difficulty in precisely distinguishing between the interior and the exterior via a sharp boundary. From this perspective, shape fuzziness is generally correlated with the boundary, which can itself be crisp, partially fuzzy, or completely fuzzy. It is possible to draw a minimal spatial extent by considering the boundary to be as close as possible (i.e. it is drawn around the area which certainly belongs to the region). In the same way, a maximal spatial extent can be drawn by considering the boundary to be as far as possible (i.e. it is drawn around the area which contains all of points possibly belonging to the region). Figure 14 represents an example of a fuzzy region in which the boundary is partially fuzzy. The spatial extent of a fuzzy region is composed of a portion called the minimal extent (i.e., all of the points definitely belonging to the spatial object) and covered by a maximal extent (i.e., all of the points possibly belonging to the spatial object). We consider that a simple fuzzy region is made up of two crisp regions: (1) the maximal extent, which can be "Equal", "Contains", or "Covers" (2) the minimal extent (figure 14). When the boundary is totally sharp (i.e. it does not contain any fuzzy point), the region is called completely crisp. This is a particular case of fuzzy region for which the maximal extent is equal to the minimal extent. In the second case, the region's boundary is fuzzy only in some locations. We speak about partially fuzzy regions, where the maximal extent covers the minimal extent. For example, a forest stand or a lake can have sharp boundaries (e.g., rocker borders for a lake and a total cut for a forest stand) and fuzzy boundaries (e.g., swamp borders for a lake) at the same time. The third case represents a typical fuzzy region for which the boundary is entirely fuzzy. For example, the boundary of a pollution zone is fuzzy everywhere since the pollution decreases from its kernel to the region's exterior. In the figure 15, we present an example of each of these three cases. Figure 16 presents some examples of invalid fuzzy regions. In case (a), the region is invalid because its closure is non-regular, i.e. there is an isolated line that belongs to the closure. In case (b), the interior of the region is non-connected because it is composed of two disjoint subregions. In the case (c), the exterior does not respect the connectedness condition since the interior contains a hole.

Topological relations between fuzzy spatial objects

Principles

To identify the topological relations between two fuzzy objects, we interpret their maximal and minimal extents as independent crisp geometries. In fact, our methodology consists of identifying four specific topological relations between the minimal and maximal extents of the fuzzy spatial objects. For that, we define a 4-Intersection matrix containing the following four topological subrelations: R Figure 17 shows the content of the matrix that describes the topological relation between a partially fuzzy region A ~ and a completely fuzzy region B ~. In the matrix (b), the letters O and C are used to denote the relations Overlap and Contains, respectively. The content of the matrix corresponds to the topological subrelations relating the minimal and maximal extents. We use the topological subrelation between the maximal extents R 4 ( max à , max B ) to label the global topological relation.

Topological relations between a fuzzy region and a crisp one

In our approach, the 4-Intersection matrix highlights the subrelations that exist between the components of the fuzzy geometries. Indeed, this expressivity is highlighted when the maximal extent of the fuzzy spatial object is different from the minimal extent. In the other cases, some cells in the matrix will have the same values. For example, figure 19 shows a fuzzy region that overlaps a crisp region. The topological relation can be reduced to a 2-Intersections matrix, because the region B ~ is crisp and so its minimal extent equals its maximal one. Hereafter, we do not study topological relations that involve crisp regions.

A ~ B ~ A ~ L ~ L ~ K ~ P ~ A ~ B ~ A ~
The values assigned to the different cells of the matrix should not be arbitrarily chosen. In general, the value of R ( max à , max B ) enforces the other values. In the next section, we study these aspects specifically for the topological relations between fuzzy regions.

Topological relations between fuzzy regions

Eight topological relations are possible between two simple crisp regions. By considering these as the possible values in the four cells of the matrix, there are 4096 8 4 = possible matrices. However, definition 1 imposes a condition mandating that the extents of a fuzzy region should be related by one of the following relations: Equal( max à , min à ),

Contains( max à , min à ), or Covers( max à , min à ). Indeed, a 4-Intersection matrix cannot identify a topological relation between two fuzzy regions when this condition is violated. Thus, the contents of the matrix's cells are not independent. For example, if the maximal extents are disjoint, it is impossible for an Overlap to exist between the minimal extents (figure 20). In figure 20 1 shows this numbering (see the appendix to explore the relations).

Clustering of topological relations between fuzzy regions

Principles

In our work, the proposed model is expressive in terms of the topological relations between fuzzy regions. In this context, 242 topological relations are distinguished. Consequently, the clustering of relations into larger groups of relations is an important step, because it is very difficult to keep in the mind this great number of relations. It is additionally very difficult to find a name for each one of these regions, and so the user will have difficulty choosing the appropriate operator in order to express a query or integrity constraint. Mark and Egenhofer (Mark and Egenhofer 1994) studied the clustering of the topological relations between simple crisp regions and simple crisp lines both through a formal basis and by taking into account cognitive aspects. Clementini and Di Felice [START_REF] Clementini | Approximate topological relations[END_REF]) defined a topological distance to classify the approximate topological relations between regions with broad boundaries. In this way, they deduced 17 clusters that they represent in a conceptual neighborhood graph.

In our approach, most of the distinguished topological relations are not completely different from each other. For example, two simple fuzzy regions can weakly or completely overlap each other depending on the content of the matrix. In the first case, only the maximal extents overlap. In the second case, however, Overlap is the unique value in the matrix's four cells. Thus, it is possible to deduce the relation's fuzziness level from the content of the 4-Intersection matrix. The objective of this section is to group the 242 topological relations into a limited number of clusters based on their fuzziness levels.

Clustering results

In section 4, we showed that the global topological relation is identified through a 4-Intersection matrix that enumerates four subrelations. Thus, a topological relation becomes possible if it appears at least once in the matrix. This possibility increases according to the number of similar subrelations. For example, a Covers topological relation in which Covers ( max à , max B ) and Covers ( min à , min B ) is stronger than another where only Covers ( max à , max B ).

Because there are eight possible values for the matrix's cells, we distinguish eight basic clusters that we call: DISJOINT, CONTAINS, INSIDE, COVERS, COVERED BY, EQUAL, MEET, and OVERLAP. Each cluster contains all of the topological relations for which at least one of the four subrelations has the same name. For example, figure 21 shows a topological relation that belongs to the following clusters: DISJOINT, CONTAINS, and COVERS. Nevertheless, it belongs to the DISJOINT cluster more strongly than to the CONTAINS and COVERS clusters. 4) weakly (table 2). A topological relation belongs to the cluster completely when the four subrelations are similar. It belongs to the cluster strongly when only three subrelations have the same name as the cluster. The level labeled fairly contains all relations for which two subrelations have the same name as the cluster. Finally, the level called weakly contains the relations for which only one subrelation has the same name as the cluster. Figure 22 presents some relations that belong to different levels of CONTAINS and DISJOINT clusters, respectively, according to the contents of their correspondent matrices.

Overlapping clusters

The main result of this clustering process is a hierarchical classification of the topological relations (figure 23). The top level is made up of eight basic clusters that each contains typically four levels: completely, strongly, fairly, and weakly.

Specification of spatial queries and integrity constraints

In the previous sections, we presented a framework for identifying topological relations between fuzzy regions. Because it uses the 9-Intersection model (Egenhofer and Herring 1990), our model can be easily integrated in a spatial database system. Indeed, the SQL language can be extended in order to retrieve fuzzy regions based on the qualitative information given by the user regarding their topological relation. In fact, a topological relation between two fuzzy regions can be recognized through the combination of four crisp spatial operators. For example, relation number 56 corresponds to (Disjoint, Disjoint, Contains, Covers). Hereafter, we suppose that we integrated our spatial model in a relational engine in order to give an example of its possible use in spatial queries involving fuzzy regions. We suppose that the spatial database stores pollution zones, which are represented as fuzzy regions. In the first query example, the user gives a coarse description of the topological relation when he introduces the specification fairly DISJOINT. The query's results should contain the pollution zones related to zone A by a topological relation belonging to this subcluster. In the second example, the query is more specific because the user identifies all topological subrelations that relate ( min à , min B ), ( min à , max B ), ( max à , min B ), and ( max à , max B ).

The third example shows another use of our model, in which it is possible to display the different fuzziness levels of a relation (e.g., Overlap) that occurs between two fuzzy regions (cf. table 3). Table 3 shows a possible result for the query presented in example 3.

Discussion

Clementini and Di Felice [START_REF] Clementini | Approximate topological relations[END_REF] propose an extension of the 9-Intersection model (Egenhofer and Herring 1990) that uses a broad boundary to replace the sharp boundary. In this approach, 44 topological relations are distinguished between two regions with broad boundaries. By considering topological distance, Clementini and Di Felice [START_REF] Clementini | Approximate topological relations[END_REF] draw a conceptual neighborhood graph that shows similarity degrees between relations classified into 17 clusters. The main advantage of this approach is the ability to support a coarser spatial reasoning involving regions with broad boundaries.

When the needs are more specific, it becomes more difficult to use this model. Furthermore, the identification of a broad boundary as a two-dimensional topological invariant requires respecting consistency conditions related to closeness and connectedness. Xinming [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]) presents a more expressive model than that of [START_REF] Clementini | Approximate topological relations[END_REF], because he decomposes the large boundary into the boundary's interior and the boundary's boundary.

Based on this definition, Xinming [START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]) presents another extension of 9-Intersection model, in which topological relations are identified through a 4*4-Intersection matrix. He distinguishes 152 topological relations presented as variants of the 44 relations from [START_REF] Clementini | Approximate topological relations[END_REF]. Nonetheless, this model does not distinguish between the boundaries of the minimal and maximal extents. Thus, many topological relations cannot be distinguished. Moreover, regions with partially fuzzy boundaries (figure 11) are considered invalid and cannot be presented through this model. In our approach, we resolve this problem by considering a simple fuzzy region as a maximal extent and a minimal extent, in which either Equal ( max à , min à ) (i.e., a crisp region) or Contains ( max à , min à ) or Covers ( max à , min à ). We do not define a large boundary as a topological invariant of fuzzy regions.

Our main motivations for adopting this framework are (1) to consider partially fuzzy regions and (2) to present a more expressive model in terms of the identification of topological relations between simple fuzzy regions. In this work, topological relations are specified through a 4-Intersection matrix that enumerates the topological subrelations between ( min à , min B ), ( min à , max B ), ( max à , min B ), and ( max à , max B ). The topological relations used here are those defined by the 9-Intersection model (Egenhofer and Herring 1990). We distinguish 242 topological relations that we classify into 8 overlapping basic clusters. Each cluster has four membership levels (or subclusters): completely, strongly, fairly, and weakly. Nevertheless, our model is not able to quantify the gradual change inside the maximal extent in the same way as the fuzzy approaches do [START_REF] Zhan | Topological relations between fuzzy regions[END_REF][START_REF] Schneider | A design of topological predicates for complex crisp and fuzzy regions[END_REF], Dilo 2006).

The Egg-Yolk model [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF] was our main inspiration to develop this framework for identifying topological relations. However, there are some fundamental differences between our model and that of [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF]. For instance, the topological relations used in [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF] are those defined in the RCC-5 model [START_REF] Randell | Modelling topological and metrical properties of physical processes[END_REF]Cohn 1989, Cohn et al. 1997). In contrast, our model is based on point-set topology, in which points and lines are considered as the basic crisp spatial object types. In [START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF], a conceptual neighborhood graph was drawn with 44 topological relations are classified into 13 clusters. In our model, we define a hierarchical classification based on the content of the matrices we use to identify the topological relations.

Conclusions and future work

Shape fuzziness is an inherent property of many spatial objects like lakes, valleys, and mountains. In GIS and spatial databases, it is a general practice to neglect shape fuzziness and formally represent fuzzy spatial objects as crisp geometries. Using such inappropriate representations can provide a source of spatial data quality degradation, because the reliability of spatial data is decreased. With emergence of prediction applications, data integration, and strategic decisional needs, researchers are increasingly more motivated to propose different methods for the formal representation of spatial fuzziness. A review of the literature regarding this topic proves that existing exact models do not permit the representation of partially fuzzy objects. For such objects, shape fuzziness partially characterizes one or several of its topological invariants. For example, a lake can have rocker and swamp banks at the same time; the boundary is fuzzy only for the swamp part. In this work, we have proposed an exact model in order to represent spatial objects that can be: crisp, partially fuzzy, or completely fuzzy. We have considered this categorization of fuzziness during the identification of topological relations.

More specifically, this paper contributes in three main ways. Based on point-set topology, we firstly define three basic fuzzy spatial object types: fuzzy point, fuzzy line, and fuzzy region.

Each one of them is typically defined as a minimal extent min à and a maximal extent max à , and these extents must verify some topological conditions in order to be valid. This model permits the representation of partially fuzzy spatial objects considered as invalid in the existing models of [START_REF] Clementini | Approximate topological relations[END_REF][START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF][START_REF] Reis | Topological relations using two models of uncertainty for lines[END_REF]. Then, we identify a topological relation through use of a 4-Intersection matrix that permits the enumeration of four subrelations: R 1 ( min à , min B ), R 2 ( min à , max B ), R 3 ( max à , min B ), and R 4 ( max à , max B ). By using this formalism for simple fuzzy regions, 242 relations can be distinguished (cf. appendix). In order to retain our propositions useful in practice, we propose the clustering of these topological relations. A topological relation can belong to one or several clusters with various levels of membership: completely, strongly, fairly, and weakly. The objective of this qualitative clustering is to improve the specification of spatial queries and integrity constraints involving fuzzy spatial objects.

The main perspective of this work aims to improve the logical consistency of spatial databases involving fuzzy spatial objects. More specifically, we are interested in the specification of integrity constraints in spatial databases storing fuzzy spatial objects. We hope to identify both integrity constraint categories and the requirements for their formal expression. The framework presented earlier can provide a basis for the extension of a formal constraint language like OCL (Duboisset et al. 2007) to express tolerant integrity constraints for fuzzy spatial objects. In the same way, decisional applications require the integration of spatial data from heterogeneous sources before they are stored in a spatial data warehouse [START_REF] Bédard | Spatial On-Line Analytical Processing (SOLAP): Concepts, Architectures and Solutions from a Geomatics Engineering Perspective[END_REF]. The main difficulty lies in choosing one of the available representations. We suggest merging the different representations in such way that the result looks like a fuzzy spatial object. The fuzzy integrity constraints can be used to increase the logical consistency of such data. 13,14,15,17,41,42,43,44,67,69,70,71,72,74,75,80,113,115,116,117,118,120,121,126,157,159,161,162,193,194,195,196,197,198,199,200,201,204,205,208,213,214,215,216 Fairly 16,73,76,119,122,158,175,176,202,203,206,207,209,210,211,212 Strongly 174, 217

DISJOINT Completely 1

Weakly 31,34,36,39,43,44,45,48,51,52,57,59,61,63,67,68,69,71,73,76,77,79,80,82,85,86,88,91,93,94,95,96,102,105,110,113,118,125,128,130,135,137,140,145,146,153,157,163,167,173,181,184,186,189,193,195,198,210,213,218,219,221,223,226,230,232,234,238,240 Fairly 8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,32,33,37,53,54,55,56,60,103,104,152,178,179,180 Strongly 2, 3, 4, 5, 7

CONTAINS Completely 6

Weakly 4,25,26,29,32,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,55,77,78,79,84,91,101,123,124,125,131,138,145,148,170,171,230,231,232 7,18,19,21,25,30,35,38,40,41,42,46,47,50,52,53,55,56,57,59,60,61,63,67,68,69,71,73,76,77,79,80,88,93,94,95,96,99,107,108,115,116,123,124,129,132,135,137,139,141,147,156,159,160,166,167,171,183,185,187,192,194,196,201,211,215,218,219,221,223,225,227,228,231,233,235,239,241 Fairly 20,49,54,58,62,64,65,66,70,72,74,75,78,82,85,86,89,90,91,92,97,98,136,142,168,220,222 Strongly 83, 84, 87

COVERS Completely 81

Weakly 3,12,14,21,22,23,26,30,33,37,39,40,42,44,45,47,49,51,53,61,62,69,70,77,78,83,85,88,90,92,94,99,101,102,103,105,106,107,109,113,114,115,117,122,123,125,126,135,140,141,142,143,151,163,164,166,170,180,186,187,191,195,196,200,212,216,219,220,223,225,226,227,229,232,233,234,235,242 Fairly 50,89,95,100,104,108,110,111,112,116,118,119,120,121,124,128,130,132,133,136,137,138,139,144,165,224,228 Strongly 129, 131, 134

COVERED BY Completely 127

Weakly 2,9,13,18,22,23,28,29,31,32,36,38,41,43,46,48,51,52,56,59,64,67,72,79,82,88,90,93,98,103,105,107,109,113,114,115,117,122,123,125,126,128,132,133,135,138,140,141,142,143,178,184,185,188,193,194,197,209,214,218,225,226,227,229,230,231,236,240,241 Fairly 8,34,35,57,58,99,100,101,102,106,145,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,181,182,183 Strongly 146,147,148,149,151

INSIDE Completely 150

Weakly 9,11,12,15,36,38,39,40,59,61,62,63,64,66,74,80,105,107,108,109,110,112,120,126,153,155,156,161,174,184,185,186,187,188,189,190,191,192,204,205,206,207,213,214,215,216 Fairly 10,65,68,111,114,154,175,176,208 Strongly MEET Completely 177

Weakly 5,11,17,19,28,33,45,46,47,48,60,63,66,71,75,86,87,92,93,94,98,109,112,117,121,130,133,134,139,140,141,149,155,160,162,164,173,178,180,181,183,184,185,186,187,193,194,195,196,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,223,225,226,227,228,230,231,232,233 Fairly 27,96,97,143,144,172,179,182,188,189,191,192,197,198,200,201,202,203,204,205,221,222,224,229,234,235,240,241 Strongly 190,199,236,238,239

Figure 1 .

 1 Figure 1. Integration of different spatial representations of a same object (e.g., lake)

Figure 2 .

 2 Figure 2. A lake with partially fuzzy boundaries

Figure 3 .

 3 Figure 3. Categorization of spatial vagueness

Figure 4 .

 4 Figure4. Topological invariants of a simple fuzzy region in[START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]

Figure 5 .

 5 Figure 5. Vague region in (Erwig and Schneider 1997)

  , a topological relation between two Egg-Yolk regions A and B is specified through a 2*2-matrix that enumerates four subrelations: Egg(A) -Egg(B), Egg(A) -Yolk(B), Yolk(B) -Egg(A), and Yolk(A) -Yolk(B) (figure 4). These four subrelations are those defined in the RCC-5 model: Partially Overlapping (PO), Proper Part (PP), Equal (E), Proper Part Inverse (PPI), and Distinct (D).

Figure 7 .

 7 Figure 7. Identification of topological relations in[START_REF] Clementini | Approximate topological relations[END_REF]

Figure 9 .

 9 Figure 9. Minimal and maximal extents for (a) a fuzzy point, (b) a fuzzy line and (c) a fuzzy region

Figure 10 .

 10 Figure 10. Fuzzy point Since a simple fuzzy point corresponds, in fact, to a simple crisp region, it should verify the following conditions: 1-The closure is a non-empty connected regular closed set. 2-The interior is a non-empty connected regular open set. 3-The boundary and exterior are connected.

  Figure 11. Fuzzy lines

  presents the different cases of fuzzy line decomposition. We should note that the different representations of a line, in figure12, indicate a set of pictograms that we use to show different types of fuzziness for lines. In other terms, these representations are not based on a mathematical model that allows to consider error component of spatial data as in (Chrisman 1991).

Figure 12 .

 12 Figure 12. Topological invariants according to the line fuzziness More formally, a fuzzy line L ~is the union of a maximal extent max L and a minimal extent min L .

Figure 13 .

 13 Figure 13. Examples of invalid lines

Figure 14 .

 14 Figure 14. Region with partial fuzzy boundary

Figure 15 .•

 15 Figure 15. Fuzzy regions Since the minimal and maximal extents are crisp regions, we distinguish three mutually disjoint topological invariants for each of them: an interior, a boundary, and an exterior. Thus, a fuzzy region A ~ is made up of six topological invariants: the interior of the minimal extent °min à , the boundary of the minimal extent min à ∂ , the exterior of the minimal extent - min à ,

Figure 16 .

 16 Figure 16. Examples of invalid fuzzy regions This general definition covers the crisp regions occurring when Equal( max à , min à ). Hereafter, we only focus on the typical fuzzy regions where Contains( max à , min à ) or Covers( max à , min à ).

Figure 17 .

 17 Figure 17. Description of the topological relation between two fuzzy regions: (a) visual content of the matrix, (b)formal identification of the relations between the minimal and maximal extents of the objects involved

Figure 21 .

 21 Figure 21. Example of clustering of a topological relation For each one of the eight basic clusters, we identify four levels of relation membership: (1) completely, (2) strongly, (3) fairly, and (4) weakly (table 2). A topological relation belongs to the cluster completely when the four subrelations are similar. It belongs to the cluster strongly when only three subrelations have the same name as the cluster. The level labeled fairly contains all relations for which two subrelations have the same name as the cluster. Finally, the level called weakly contains the relations for which only one subrelation has the same name as the cluster. Figure22presents some relations that belong to different levels of CONTAINS and DISJOINT clusters, respectively, according to the contents of their correspondent matrices.

Figure 22 .

 22 Figure 22. Evaluation of topological relation's fuzziness

Figure 23 .

 23 Figure 23. Hierarchical classification of the topological relations

Figure 1 .

 1 Figure1. Integration of different spatial representations of a same object (e.g., lake) Figure2. A lake with partially fuzzy boundaries Figure3. Categorization of spatial vagueness Figure4. Topological invariants of a simple fuzzy region in[START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF]) Figure5. Vague region in (Erwig and Schneider 1997) Figure6. Identification of topological relations in[START_REF] Cohn | The 'egg-yolk' representation of regions with indeterminate boundaries[END_REF] Figure7. Identification of topological relations in[START_REF] Clementini | Approximate topological relations[END_REF] Figure8. Identification of topological relations in[START_REF] Xinming | Spatial object modeling in fuzzy topological spaces: with applications to land cover change[END_REF] Figure 9. Minimal and maximal extents for (a) a fuzzy point, (b) a fuzzy line and (c) a fuzzy region Figure 10. Fuzzy point Figure 11. Fuzzy lines Figure 12. Topological invariants according to the line fuzziness Figure 13. Examples of invalid lines Figure 14. Region with partial fuzzy boundary Figure 15. Fuzzy regions Figure 16. Examples of invalid fuzzy regions Figure 17. Description of the topological relation between two fuzzy regions: (a) visual content of the matrix, (b) formal identification of the relations between the minimal and maximal extents of the objects involved Figure 18. Examples of identification of topological relations through a 4-Intersection matrix Figure 19. Example of a topological relation between a fuzzy region and a crisp region Figure 20. Controlling the validity of a Disjoint relation Figure 21. Example of clustering of a topological relation Figure 22. Evaluation of topological relation's fuzziness Figure 23. Hierarchical classification of the topological relations Figure 24. 242 topological relations between fuzzy regions

  , the subrelation O ( min à , min B ) is grey to denote that is not allowed whereas D ( min à ,

	( max à , max B ), 29 matrices are valid when Contains ( max à , max B ), 29 for Inside ( max à , max B ), 46 for Covers ( max à , max B ), 46 for Covered by ( max à , max B ), 65 for Overlap ( max à , max B ), 4 for Meet ( max à , max B ), and 22 when Equal ( max à , max B ). The topological relations are numbered from 1 to 242 according to the relation between max à and max B . Table
		B	B
	min à max Ã	min O ( min à , min B ) --	max --D ( max à , max B )
		(a) Invalid Disjoint' relation	(b) Valid Disjoint' relation
		Figure 20. Controlling the validity of a Disjoint relation
	In order to enumerate the valid 4-Intersection matrices, we firstly studied the possible values in the other three cells for each of the eight possible values of R( max à , max B ). For example, if Contains ( max à , max B ), the only possible relation between max à and min B is Contains; otherwise,
	the expected relation cannot respect the general definition of a fuzzy region. The figure 20 shows an example of an inconsistent matrix in which Disjoint ( max à , max B ) and Contains ( min à , min B ). This matrix is inconsistent because R ( max B , min B ) ∉{Contains, Covers, Equal}. In the second step, we also fix the relation between min à and min B to deduce the possible values of R ( min à , max B ). For example, when Contains ( max à , max B ) and Contains ( min à , min B ), R ( min à , max B ) should not be Meet or Equal. In this way, 31 rules (see table 4 in the appendix)
	are defined in order to ensure the consistency of matrices. In the rules' premises, we specify either R ( max à , max B ) or (R ( max à , max B ) and R ( min à , min B )). Then, we deduce the possible
	values in the remaining cells. In figure 20, the matrix on the left is not valid because it
	requires the minimal extent to be disjoint to the minimal extent (i.e., the definition of the
	fuzzy region is not respected, because R( max

min B

) is black to show that is permitted. Consequently, several of the 4096 possible matrices are invalid because the dependency between the matrix's cells is not respected.

  The resulting 32 subclusters overlap each other because a topological relation typically belongs to different levels of 1, 2, 3, or 4 clusters at the same time. For example, topological relation number 56 (see the appendix and the table 2) belongs fairly to the CONTAINS cluster and weakly to the COVERS and INSIDE clusters. The bottom level of the classification contains the 242 topological relations that appear in different subclusters.

		max à min B	Ã	B	max		COVERS Cluster
			min					CONTAINS Cluster
		Disjoint	Disjoint
		Contains	Covers				DISJOINT Cluster
	Disjoint	Disjoint	Disjoint		Disjoint	Disjoint	Disjoint	Disjoint	Overlap
	Disjoint	Disjoint	Disjoint		Overlap	Contains	Overlap	Contains	Overlap
	Completely disjoint	Strongly disjoint	Fairly disjoint
	Contains	Contains	Contains	Overlap	Covers	Overlap	Disjoint	Overlap
	Contains	Contains	Contains	Contains	Contains	Contains	Contains	Contains
	Completely contains		Strongly contains	Fairly contains	Weakly contains
		175

  In the same way, it is possible to use the model to formally express spatial integrity constraints in a fuzzy context. For example, let the constraint saying that 'two different lakes This constraint can be formally expressed by integrating new spatial operators (e.g., completely Contains, weakly Covers, etc.) in a formal constraint language like the Object Constraint Language (OCL)(Duboisset et al. 2007). The database storing the lakes is consistent only if the topological relations between the different entities belong to fairly MEET or completely DISJOINT subclusters (see example 4).

	Inside Completely Covers Root can be only fairly meet or completely disjoint'. Example 4: Context Lake inv: Weakly Fairly Strongly Disjoint Contains Lake.allInstances forAll (a, b| a<>b implies fairly MEET(a,b) or Covered by Overlap Equal Meet Weakly Fairly Strongly Completely
	completely DISJOINT(a,b));
	242 relations in the bottom level
	Example 1: Select Pollution_Zone.geometry From Pollution_Zone Where
	Fuzzy_Relate (pollution_zone.geometry, A.geometry, fairly DISJOINT);
	Example 2: Select Pollution_Zone.geometry From Pollution_Zone Where
	Fuzzy_Relate (Pollution_Zone.geometry, A.geometry, Disjoint, Meet,
	Contains, Contains);
	Example 3: Select P1.id, P2.id, determine (P1.geometry, P2.geometry, "Overlap")
	From Pollution_Zone P1, P2 Where P1.id<>P2.id;

Appendix: 242 topological relations between fuzzy regions and required rules to deduce them

	181 225			90 182 226		91 183 227			92 184 228
	1	Contains Inside	Overlap Inside	2	Overlap Inside	Overlap Inside	3	Covers Inside		Overlap Inside	4	Contains Meet	Overlap Inside
	Disjoint 93 185 229	Disjoint	Contains 94 186 230	Inside	Contains 95 187 231		Covered by	Contains 188 96 232	Equal
		Disjoint	Disjoint		Contains	Contains		Contains		Contains	Contains	Contains
	5	Meet	Inside	6	Meet	Covered by	7	Meet		Covered by	8	Meet	Inside
	Contains Contains 97 Covers 189 233	Contains Overlap Overlap	Contains Contains 98 Contains 190 234	Contains Contains Overlap	Contains Contains 99 Covers 191 235		Contains Covers Overlap	Inside Contains Overlap 100 192 236	Contains Inside Overlap
	9	Meet	Overlap	10	Meet	Overlap	11 Meet		Covered by	12 Meet	Overlap
	Meet Contains Contains 101 193 237	Contains Inside Overlap	Meet Contains Overlap 102 194 238	Contains Meet Overlap	Meet Contains Overlap 103 195 239		Contains Overlap Overlap	Meet Contains Covers 104 196 240	Contains Overlap Covered by
	13 Disjoint	Inside	14 Disjoint	Inside	15 Disjoint		Covered by	16 Disjoint	Covered by
	Disjoint Contains Contains 105 197 241	Contains Overlap Inside	Disjoint Contains Covers 106 198 242	Contains Covered by Overlap	Disjoint Contains Contains 107 199		Contains Meet Overlap	Disjoint Contains Covers 108 200	Contains Disjoint Overlap
	17			18			19			20
	21 Disjoint Contains 109 Disjoint Overlap 201	Contains Overlap Inside Overlap	22 Covers Contains 110 Disjoint Contains 202 Figure 24. 242 topological relations between fuzzy regions 23 Inside Covers Overlap 111 Overlap Disjoint Overlap Overlap Overlap Overlap Contains Contains Contains 203	24 Disjoint Covers 112 Overlap Contains 204	Covers Covered by Overlap Contains
	25 Covers Contains 205 113 Covers Disjoint Rules	Contains Covered by Overlap Overlap	26 Covers Contains 206 114 Overlap Disjoint	Contains Inside Overlap Disjoint	27 Inside 207 Contains 115 Disjoint Disjoint		Contains Covered by Overlap Overlap	28 208 Equal Contains Overlap 116 Disjoint	Contains Equal Overlap Meet
	29 209 Covers Contains Meet 117 Disjoint	Contains Equal Overlap Overlap	30 210 Equal Disjoint Contains 118 Disjoint	Contains Overlap Covered by Meet	31 211 Overlap Contains Meet 119 Disjoint	Contains Overlap Overlap Disjoint	212 32 Overlap Contains Meet 120 Disjoint	Contains Inside Overlap Meet
	Equal 121 Disjoint	Inside Inside	Equal 122 Disjoint	Covered by Disjoint	Equal 123 Disjoint		Inside Disjoint	Contains 124 Disjoint	Inside Covered by
	33 213 Contains Disjoint	Contains Overlap	34 214 Covers Contains	Equal Overlap	35 215 Contains Covers		Equal Overlap	216 36 Contains Disjoint	Equal Overlap
	Overlap 125 Disjoint	Covered by Meet	Inside 126 Disjoint	Inside Inside	Inside 127 Disjoint		Inside Meet	Meet 128 Disjoint	Inside Covered by
	37 129 217 Contains Contains	Contains Overlap	38 130 218 Contains Meet	Equal Overlap	39 131 219 Covers Covers		Equal Overlap	132 220 40 Contains Meet	Equal Overlap
		Contains	Covered by
	41 133 221 Disjoint Contains Disjoint	Equal Overlap Disjoint	42 134 222 Covers Contains Meet Covers	Equal Overlap Inside Inside	43 135 223 Contains Contains Meet Covers		Equal Overlap Covered by Covered by	136 224 44 Covers Covers Meet Covers	Equal Overlap Covered by Covered by
		Disjoint	Inside			Disjoint	Covered by		Disjoint		Inside	Disjoint	Covered by
		Covers Covers	Equal Overlap		Covers Covers	Equal Overlap		Contains Covers	Equal Covered by	Contains Covered by	Equal Covered by
		Contains	Overlap		Covers	Overlap		Contains		Overlap	Overlap	Overlap

Table 4 .

 4 Required rules for topological relations between fuzzy regions

	Rule 1: Let A ~ and B ~ are two simple fuzzy regions, if Disjoint ( max à , max B ) then Disjoint ( min à , min B ).	min à max Ã	B D ( min à , min min B ) --	B --max D ( max à , max B )

The closure, in point set topology, is the union of the interior and the boundary.

The spatial relations (i.e., Equal, Contains, Covers) used in this definition are those defined in(Egenhofer and Herring 1990).

Covered by Covers

Covered by

Equal

Covered by Contains

Inside

Covered by

Covered by Covered by

Covered by

Covered by

Covered by Contains

Inside

Covered by

Covered by Covers

Covered by Overlap

Covered by Contains

Covered by

Covered by

Covered by Equal

Covered by

Covered by

Covered by Covers

Inside

Covered by

Covered by Overlap

Covered by Covers

Covered by Objects with Undetermined Boundaries, Burrough, P. & Frank, A. (Ed.) (Taylor & Francis), pp. 171-187. COHN, A.G., BENNETT, B., GOODAY J. and GOTTS, N.M., 1997, Qualitative Spatial Representation and Reasoning with the Region Connection Calculus, GeoInformatica, 1(3), pp. 275-316. CHRISMAN, N.R., 1991, The error component in spatial data. In: Maguire, D.J., Goodchild, M.F and Rhind, D.W. (eds.), Geographical Information Systems: Principles and Applications, Volume 1, pp. 165-174. DEVILLERS, R., BÉDARD, Y., JEANSOULIN, R., and MOULIN, B., 2007, Towards Spatial Data Quality Information Analysis Tools for Experts Assessing the Fitness for Use of Spatial Data, International Journal of Geographical Information Sciences (IJGIS), Vol. 21, 3, pp. 261-282. DILO, A., 2006, Representation and reasoning with vagueness in spatial information: A system for handling vague objects. PhD thesis, ITC, Netherlands, 187p. DUBOISSET, M., PINET, F., KANG M.-Ah. and SCHNEIDER M., 2007, A General Framework to Implement Topological Relations on Composite Regions. To appear in: Lecture Notes in Computer Science, Springer. DUCKHAM, M., MASON, K., STELL, J., and WORBOYS M., 2001, A formal ontological approach to imperfection in geographic information. Computer, Environment and Urban Systems, 25, pp. 89-103. EGENHOFER, M.J., 1989, A formal definition of binary topological relations. In Poceedings of the third international conference on Foundations of Data Organisation and Algorithms (FODO), W.Litin and H.J.Scheck (Ed.) (NY: Springer-Verlag), Lecture notes in computer science, 367, pp. 457-472. EGENHOFER, M. J. and FRANZOSA, R.D., 1991, Point-set Topological Relations. International journal of geographical Information Systems, 5(2), pp. 161-174. EGENHOFER, M. and HERRING J., 1990, A mathematical framework for the definition of topological relations. In Proceedings of the Fourth International Symposium on Spatial Data Handling, K. Brassel and H. Kishimoto (Ed.), Zurich, Switzerland , pp. 803-813. ERWIG, M. and SCHNEIDER, M., 1997, Vague regions. In 5th International Symposium on Advances in Spatial Databases (SSD'97), Lecture Notes in Computer Science, 1262, pp. 298-320. FISHER, P.F., 1999, Models of uncertainty in spatial data. In Geographical Information Systems, P. A. Longley, M. F. Goodchild, D. J. Maguire, and D. W. Rhind (Ed.) (New York: John Wiley & Sons), pp. 191-205. FRANK, A.U., 2001, Tiers of ontology and consistency constraints in geographical information systems. In International Journal of Geographical Information Science, 15(7), 667--678. GODJJEVAC, J., 1999, Idées nettes sur la logique floue. Presses polytechniques et universitaires romandes, Lausanne. GOODCHILD, M.F., 1995, Attribute Accuracy. In Elements of spatial data quality, S.C. Guptill and J.L. Morrison (Ed.) (New York: Elsevier Science inc.), pp. 59-79. GUPTILL, S.C. and MORRISON, J.L., 1995, Spatial data quality. In Elements of spatial data quality, S. C. Guptill and J. L. Morrison (Ed.) (New York: Elsevier Science inc.). HAZARIKA, S.M. and COHN, A.G., 2001, A taxonomy for spatial vagueness, an alternative egg-yolk interpretation. In Proceeding of the COSIT 2001, The fifth international Conference On Spatial Information Theory, D.R. Montello (Ed.) (California: Springer-Verlag), Lecture Notes in Computer Science, 2205, pp. 92-107. HWANG, S., and THILL, J-C., 2005, Modeling Localities with Fuzzy Sets and GIS, In: Cobb M, Petry F, and Robinson V (eds) Fuzzy Modeling with Spatial Information for Geographic Problems, Springer-Verlag, pp. 71-104.