Approximate answering of queries involving polyline–polyline topological relationships

Abstract

In geographic information systems, pictorial query languages are visual languages which make easier the user to express queries by free-hand drawing. In this perspective, this article proposes an approach to provide approximate answers to pictorial queries that do not match with the content of the database, that is, the results are null. It addresses the polyline–polyline topological relationships and is based on an algorithm, called Approximate Answer Computation algorithm, which exploits the notions of Operator Conceptual Neighborhood graph and 16-intersection matrix. The operator conceptual neighborhood graph represents the conceptual topological neighborhood between Symbolic Graphical Objects and is used for relaxing constraints of queries. The nodes of the operator conceptual neighborhood graph are labeled with geo-operators whose semantics has been formalized. The 16-intersection matrix provides enriched query details with respect to the well-known Dimensionally Extended 9-Intersection Model proposed in the literature. A set of minimal 16-intersection matrices associated with each node of the operator conceptual neighborhood graph, upon the external space connectivity condition, is defined and the proof of its minimality is provided. The main idea behind each introduced notion is illustrated using a running example throughout this article.

Keywords

Visualization languages topological relationships geo-operator intersection matrix operator conceptual neighborhood graph approximate answer

Introduction

Qualitative spatial reasoning is an important technique that has been widely used to represent commonsense knowledge.^1–3 This research area deals with the development of tools and techniques for reasoning with non-metrical and incompletely specified spatial knowledge.⁴ Most studies focused on fundamental aspects of space such as topology, orientation, size, and shape. These aspects have been extensively investigated both at a mathematical level^5–9 and within geographic information systems (GISs).^10,11

Standard GISs are entirely based on numerical methods for representing and reasoning on spatial information,^4,12 which are ineffective to process imprecise or uncertain data.¹³ In order to overcome these limitations, and to better understand and represent user’s mental model of spatial reasoning, GISs should provide an effective and an accessible query system. In such so-called qualitative reasoning-based systems,^4,13 in the case queries do not match with the content of the database and the results are null, approximate answers are proposed to the user by relaxing query constraints. In this article, we deal with this class of queries, and accordingly, we propose an approach that supports the user in the selection of the spatial constraints to be relaxed or maintained in order to provide a non-null answer.

In general, geographic queries can be better expressed using graphical metaphors in query languages which are powerful to express the user’s mental model of the query.¹⁴ The need for advanced geographic query languages in GISs has been emphasized since the 1990s.¹⁵ However, GIS software packages have traditionally been developed by experts for experts; therefore, the proposed query languages were highly technical and limited to a restricted group of skilled users. For this reason, with the increasing complexity of GISs, geographic query languages should satisfy two basic requirements: they must be powerful and easy to use, at the same time. Powerful, because they have to retrieve information about complex database schemas, keeping track of several relations existing among data. Easy to use, because the access to the stored information should not be limited to experts, but should be conceived for non-specialized end-users.^16,17 These two basic requirements find a common solution in the development of advanced visual geographic query languages.¹⁸ Visual query languages are high-level declarative query languages that can be iconic,¹⁹ pictorial,²⁰ and query-by-example.²¹ They are languages for querying databases that use visual representations to depict the main features of the domain of interest and express-related queries.²² This article focuses on pictorial query languages, that is, visual languages where queries are formulated by free-hand drawing. The semantics of pictorial queries is expressed by the user drawing itself, which specifies the properties that the query answer has to satisfy, and does not require the user to be aware about the underlying query language syntax.

In the literature, some proposals discuss the way to formulate queries using pictorial configurations, for instance, Ferri et al.^20,23 In particular, in the mentioned papers, a pictorial query language, called Geographical Pictorial Query Language (GeoPQL), has been proposed in order to address the user’s mental model of the query. GeoPQL allows users to formulate queries using drawing facilities and correctly interprets the query syntax and semantics on the basis of its underlying algebra. In these works, a set of Symbolic Graphical Objects (SGOs) has been defined to graphically represent the spatial configurations of geographic entities (i.e. point, polyline, and polygon), the spatial relationships between SGOs, as well as the spatial operators based on an object-calculus. In this article, we refer to GeoPQL and we focus on the topological relationships between polylines. Note that, in this work, we assume that in a polyline there are no self-intersections, bifurcations, or loops.

In order to clarify the problem addressed in this article, suppose the user formulates the following query on the Italian geographic database: Find the rivers that touch a railway. In the GeoPQL working area, this query can be pictorially represented as shown in Figure 1.

Figure 1.

Pictorial query formulation.

The answer to this query in the Italian geographic database is null. In this article, we propose an approach which provides an approximate answer to the user that can satisfy her/his request. To this end, first of all, we revise and formalize the GeoPQL geo-operators. Then, we introduce the operator conceptual neighborhood (OCN) graph which is used as a guide to indicate how the pictorial query of the user can be approximated through the transition from a given topological relationship to the adjacent thereof.

In the OCN graph, a node is labeled with one (or a combination of two) geo-operator(s), and an arc represents the conceptual topological neighborhood between nodes. The conceptual topological neighborhood is captured according to the notion of deformation in line with Egenhofer²⁴ (as discussed in section “The OCN graph”).

In the proposed method, the operators labeling the nodes of the OCN graph are associated with the corresponding intersection matrices. In particular, we introduce the notion of 16-intersection matrix which provides enriched query details with respect to the well-known Dimensionally Extended 9-Intersection Model (DE-9IM) proposed in the literature.^8,25 In fact, in contrast with the existing proposals, we distinguish the notions of isolated single interior points and interior lines of a polyline, and we are able to represent additional lower dimension intersections in the same matrix. This issue is extensively discussed in section “Comparison of the 16-intersection matrix with other matrices.”

We introduce the notion of external space connectivity upon which a set of minimal 16-intersection matrices has been defined. We prove that this set is minimal, that is, the 16-intersection matrix associated with any pictorial configuration in GeoPQL is equivalent to one belonging to this set.

The set of minimal 16-intersection matrices also allows us to define an algorithm, the Approximate Answer Computation algorithm, in order to provide approximate answers to the users.

We remark that the external space connectivity rule and the notion of minimal 16-intersection matrix have been conceived in order to relax constraints and, therefore, to provide approximate answers to GeoPQL pictorial queries with null results. In fact, currently, in GeoPQL, any pictorial query drawn by the user is re-conducted to a pictorial one associated with a minimal 16-intersection matrix.

To summarize, the main contributions of this work are as follows:

Re-visitation and formalization of the semantics of the GeoPQL geo-operators;

Definition of the OCN graph, based on the GeoPQL geo-operators, that is addressed to represent the conceptual topological neighborhood between SGOs;

Formalization of the 16-intersection matrix that enables us to distinguish the notions of isolated single interior points and interior lines of a polyline, and to represent additional lower dimension intersections in the same matrix which are not captured by the well-known DE-9IM;

Formal proof related to identification of the set of minimal 16-intersection matrices associated with the OCN graph;

Definition of the Approximate Answer Computation algorithm in order to relax constraints and compute approximate query results in GeoPQL.

The article is structured as follows. In section “Related work,” the related work is given. Successively, in section “Revised GeoPQL operators,” the GeoPQL operators are revised and formalized. In section “The 16-intersection matrix,” the 16-intersection matrix is formally defined, and some examples are provided in order to show our proposal. In section “The OCN graph,” the notion of the OCN graph is given. In section “Minimal 16-intersection matrix,” some formal definitions are given in order to introduce the theorem regarding the set of minimal 16-intersection matrices. In section “Algorithm,” we define an algorithm that identifies the possible configurations that can approximate the user query, according to the semantics of the geo-operators given in section “Revised GeoPQL operators.” In section “The system implementation,” we illustrate the implementation of the 16-intersection matrix and the algorithm discussed in sections “The 16-intersection matrix” and “Algorithm,” respectively. Finally, in section “Comparison of the 16-intersection matrix with other matrices,” the comparison of the 16-intersection matrix with other representative matrices proposed in the literature is given, and section “Conclusion” concludes.

Related work

Qualitative spatial reasoning is essentially based on the manipulation of qualitative spatial relationships.^3,4,12,13,26 To this end, topologic, direction, and orientation (orientation relations describe where objects are placed relative to one another. They can be defined in terms of a primary object, the reference object, and the frame of reference. Unlike the topological relationships in spatial entities, orientation is not a binary relation⁴) relationships have been investigated in the literature.^7,25–30 Furthermore, several studies have been carried out to extend and incorporate qualitative relationships in query languages.¹³ For instance, spatial-query-by-sketch, that is a visual spatial query language, allows the users to draw an example of the spatial configuration they are interested in using a pen.¹⁵ This language is based on spatial relationships and a computational model that, for a given relation, determines the least number of differences in the 9-intersection matrices. Therefore, the conceptual neighborhood graph has been derived for eight line–line relationships, which are disjoint, meet, overlap, covers, coveredBy, contains, equal, and inside. A similar approach to Spatial-Query-by-Sketch, proposed in Schultz et al.,³¹ focuses on the interpretation of user sketches, which have been drawn via a touch-sensitive screen. Topological relationships, which are extracted from the user’s sketched scene, become the query criteria. This mentioned work explores problems related to the combination of qualitative and numerical methods, such as managing the ambiguous nature of qualitative terms (e.g. “near”), providing a simple query system, and visualizing fuzzy qualitative query solutions. Another visual approach that assists non-experts in performing GIS queries is the Metaphor GIS Query Language.³² A geometaphor is a pair composed of a graphical part (drawing) and a descriptive part (icon). The geometaphor has been introduced to link both spatial and semantic aspects of the geographic data. Queries are specified by placing instances of geometaphors on a drawing area and supplying both spatial operators and context parameters.

The notion of conceptual neighbors has been introduced by Freksa and Röhrig.² Neighborhoods are defined by considering the continuous translation or deformation of the objects within a given relation. For instance, in the two-dimensional (2D) space, if two polylines are disjoint, and one polyline is moved toward the other, the polylines must first touch before they cross. With regard to this notion, in Nedas et al. 33 and Pereira Reis et al.,³⁴ the authors propose 33 topological relationships between simple undirected polylines (i.e. two distinct boundaries or end points, no self-intersections, bifurcations, or loops), which are modeled by the 9-intersection matrix.

Our proposal differs from the above-mentioned papers for several points, which will be illustrated in detail in section “Comparison of the 16-intersection matrix with other matrices.” Here, we address one of these points, concerning the symmetrical property of the spatial operators. In fact, in the aforementioned works, the spatial operators are not symmetric (e.g. covers and coveredBy are distinguished), whereas in GeoPQL, the geo-operators are symmetric because the target of the query is independent of the order of the operands (for more detail, see, for instance, Ferri and Rafanelli²⁰). Consequently, the 33 configurations illustrated in Pereira Reis et al.³⁴ are reduced to 23 (in fact, see Figure 2 in Pereira Reis et al.,³⁴ where the pairs: LL3–LL8, LL4–LL15, LL5–LL9, LL6–LL10, LL7–LL16, LL12–LL17, LL14–LL19, LL26–LL29, LL27–LL30, and LL28–LL31 coincide). Since in our approach we also assume the external space connectivity rule (see section “Minimal 16-intersection matrix”), the number of configurations are further reduced to 10 (in fact, in the mentioned figure, the following configurations: LL3, LL6, LL8, LL10, LL11, LL12, LL13, LL14, LL17, LL18, LL19, LL21, LL23, LL26, LL28, LL29, LL31, LL32, and LL33 do not satisfy the external space connectivity rule). In addition, in our approach, since we distinguish between isolated single interior point and interior line intersections, the number of configurations on which we focus is 13. In particular, as we will show in section “Minimal 16-intersection matrix,” this number becomes 11 because the matrices (d) and (f), as well as (l) and (n), in Table 1 coincide. The reason is that the semi-planes generated by a polyline are not distinguished. This issue will be investigated in a future work.

Figure 2.

(a) Isolated single interior point versus (b) interior line intersections.

Table 1.

The set $A (L, Q)$ of 16-intersection matrices associated with $L$ , $Q$ .

Geo-operator	Configuration	Matrix
DSJ		$\begin{matrix} \begin{matrix} ℒ_{i_{p}} \\ ℒ_{i_{l}} \\ ℒ_{b} \\ ℒ_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 0 & - \\ - & 0 & - & 1 \\ 0 & - & 0 & 2 \\ - & 1 & 2 & 1 \end{matrix}) \end{matrix}$ (a)
INC		$\begin{matrix} \begin{matrix} ℒ_{i_{p}} \\ ℒ_{i_{l}} \\ ℒ_{b} \\ ℒ_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 1 & - \\ - & 1 & - & 1 \\ 0 & - & 1 & 1 \\ - & 0 & 0 & 1 \end{matrix}) \end{matrix}$ (b)
INC		$\begin{matrix} \begin{matrix} ℒ_{i_{p}} \\ ℒ_{i_{l}} \\ ℒ_{b} \\ ℒ_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 2 & - \\ - & 1 & - & 2 \\ 0 & - & 0 & 2 \\ - & 0 & 0 & 1 \end{matrix}) \end{matrix}$ (c)
CRS		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 1 & - & 0 & - \\ - & 0 & - & 2 \\ 0 & - & 0 & 2 \\ - & 2 & 2 & 1 \end{matrix}) \end{matrix}$ (d)
TCH		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 0 & - \\ - & 0 & - & 1 \\ 0 & - & 1 & 1 \\ - & 1 & 1 & 1 \end{matrix}) \end{matrix}$ (e)
		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 1 & - & 0 & - \\ - & 0 & - & 2 \\ 0 & - & 0 & 2 \\ - & 2 & 2 & 1 \end{matrix}) \end{matrix}$ (f)
		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 1 & - \\ - & 1 & - & 2 \\ 0 & - & 0 & 2 \\ - & 1 & 1 & 1 \end{matrix}) \end{matrix}$ (g)
		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 1 & - \\ - & 0 & - & 2 \\ 0 & - & 0 & 2 \\ - & 1 & 1 & 1 \end{matrix}) \end{matrix}$ (h)
		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 0 & - \\ - & 1 & - & 1 \\ 0 & - & 1 & 1 \\ - & 1 & 1 & 1 \end{matrix}) \end{matrix}$ (i)
		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 0 & - \\ - & 1 & - & 2 \\ 0 & - & 0 & 2 \\ - & 2 & 2 & 1 \end{matrix}) \end{matrix}$ (l)
		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 1 & - \\ - & 1 & - & 1 \\ 1 & - & 0 & 1 \\ - & 1 & 1 & 1 \end{matrix}) \end{matrix}$ (m)
TCS		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 0 & - \\ - & 1 & - & 2 \\ 0 & - & 0 & 2 \\ - & 2 & 2 & 1 \end{matrix}) \end{matrix}$ (n)
EQL		$\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 & - & 0 & - \\ - & 1 & - & 0 \\ 0 & - & 2 & 0 \\ - & 0 & 0 & 1 \end{matrix}) \end{matrix}$ (o)

DSJ: geo-disjunction; INC: geo-inclusion; CRS: geo-cross; TCH: geo-touching; TCS: geo-touchcross; EQL: geo-eq1.

In Formica et al.,^35,36 a 16-intersection matrix and an OCN graph have been presented but in the case of the polygon–polyline topological relationships. In this article, we propose and formalize a 16-intersection matrix and an OCN graph for the polyline–polyline topological relationships, which are both inherently different with respect to the ones presented in the aforementioned papers. In addition, in this article, we introduce the notion of minimal 16-intersection matrix, we identify a set of minimal 16-intersection matrices, and we prove that this set is minimal.

Finally, in Belussi et al.,³⁷ an approach for relaxing topological selection and join operators has been presented. It relies on a different technique with respect to our proposal which essentially uses index-based algorithms and similarity functions specifically defined for relaxation purposes without defining enriched intersection matrices.

Revised GeoPQL operators

In this section, we revise and formalize the GeoPQL operators in the case of polyline–polyline topological relationships. Below, we start by introducing a simplified notion of SGOs defined in Ferri et al.²³

Definition 3.1 [SGO]

Given a GIS, an SGO is characterized by a $geometric_type$ component which can be a polyline, a polygon, or a point.

The GeoPQL algebra²⁰ consists of a set of binary geo-operators in $R^{2}$ , which are logical (Geo-union (UNI), Geo-any (ANY), Geo-alias (ALS)), metrical (Geo-difference (DIF), and Geo-distance (DIS)), and topological (Geo-disjunction (DSJ), Geo-touching (TCH), Geo-inclusion (INC), Geo-cross (CRS), Geo-equality (EQL), Geo-pass-through (PTH), Geo-overlapping (OVL)). Regarding the topological relationships, we focus on the polyline–polyline SGOs; therefore, we restrict our attention to Geo-disjunction (DSJ), Geo-touching (TCH), Geo-inclusion (INC), Geo-cross (CRS), and Geo-equality (EQL). The remaining Geo-pass-through (PTH) and Geo-overlapping (OVL) refer to the case of polygon–polyline and polygon–polygon topological relationships, respectively.

The formal semantics of the above-mentioned operators is formally given in Definition 3.3. Before introducing it, we have to present the notation we use in our approach, which differs from the one usually adopted in the literature as explained below.

Given a polyline $L$ , in our approach $L_{i_{p}}$ , $L_{i_{l}}$ , $L_{b}$ , and $L_{e}$ denote isolated single interior points, interior lines, boundary points (or end points), and the exterior of the polyline $L$ , respectively. With regard to the existing proposals in the literature, where there is no distinction between isolated single interior points and interior lines of a polyline, in our approach, the different notations $L_{i_{p}}$ and $L_{i_{l}}$ are introduced. They allow us to distinguish different configurations, as for instance the ones shown in Figure 2, where the intersection between polylines is one isolated interior point, case (a), or a line, case (b). These configurations correspond to two different pictorial queries that the user can draw to represent the CRS and the new TCS (Geo-touchcross) operators, and they have different intersection matrices, as we will see in the next section. Note that the GeoPQL algebra is now extended with the TCS geo-operator, which was not included in the previous algebra.

In the following, the notion of semi-neighborhood is introduced. It will be used to formally define the geo-operators between polylines.

Definition 3.2 [Semi-neighborhood]

Given a polyline $L \in SGO$ , let $R_{a}^{L}$ and $R_{b}^{L}$ be the semi-planes of $R^{2}$ defined by $L$ and its extension. Let us consider a point $x \in L$ and a neighborhood of x, $I (x)$ . Then, $I (x)_{a}^{L}$ and $I (x)_{b}^{L}$ are the two semi-neighborhoods of $I (x)$ belonging to $R_{a}^{L}$ and $R_{b}^{L}$ , respectively.

Definition 3.3 [Geo-operators]

Given two polylines $L$ , $Q \in SGO$ , the binary geo-operations DSJ, TCH, INC, CRS, TCS, and EQL are formally defined as follows, where $k, j \in {i_{p}, i_{l}, b, e}$ :

DSJ (geo-disjunction):

$L$ DSJ $Q$ iff $L_{j} \cap Q_{k} = \emptyset, j, k \neq e$

TCH (geo-touching):

Assume $S = L_{j} \cap Q_{k} \neq \emptyset$ where $j, k \neq e$ . Then:

$L$ TCH $Q$ iff $\exists$ at least one connected component $S_{c} \in S$ such that $\exists$ $x \in S_{c}$ and a small enough $I (x)$ :

$I (x)_{a}^{Q} \cap L_{j} \cap Q_{e} = \emptyset$ AND $I (x)_{b}^{Q} \cap L_{j} \cap Q_{e} \neq \emptyset$ AND

$L_{e} \cap Q_{j} \neq \emptyset$ AND $L_{j} \cap Q_{e} \neq \emptyset$ ,

and $\exists /$ $y \in S_{c}$ , and a small enough $I (y)$ :

$I (y)_{a}^{Q} \cap L_{j} \cap Q_{e} \neq \emptyset$ AND $I (x)_{b}^{Q} \cap L_{j} \cap Q_{e} = \emptyset$

where $I (x)_{a}^{Q}$ , $I (x)_{b}^{Q}$ , $I (y)_{a}^{Q}$ , $I (y)_{b}^{Q}$ are semi-neighborhoods of $I (x)$ and $I (y)$ (see Definition 3.2).

INC (geo-inclusion):

$L$ INC $Q$ iff $L_{e} \cap Q_{j} = \emptyset, j \neq e$ .

CRS (geo-cross):

Assume $S = L_{j} \cap Q_{k} \neq \emptyset$ where $j, k \neq e, b$ . Then:

$L$ CRS $Q$ iff $\exists$ at least one connected component $S_{c} \in S$ such that $S_{c}$ is a point and $\exists$ $I (x)$ , small enough:

$I (x)_{a}^{Q} \cap L_{j} \cap Q_{e} \neq \emptyset$ AND $I (x)_{b}^{Q} \cap L_{j} \cap Q_{e} \neq \emptyset$ .

where $I (x)_{a}^{Q}$ and $I (x)_{b}^{Q}$ are semi-neighborhoods of $I (x)$ (see Definition 3.2).

TCS (geo-touchcrossing):

Assume $S = L_{k} \cap Q_{j} \neq \emptyset$ , where $j, k \neq e, b$ . Then:

$L$ TCS $Q$ iff $\exists$ at least one connected component $S_{c} \in S$ such that $S_{c}$ is a polyline and $\exists y, z \in S_{c}, y \neq z$ , and small enough $I (y)$ and $I (z)$ :

$I (y)_{a}^{Q} \cap L_{j} \cap Q_{e} \neq \emptyset$ AND $I (z)_{b}^{Q} \cap L_{j} \cap Q_{e} \neq \emptyset$

where $I (y)_{a}^{Q}$ and $I (z)_{b}^{Q}$ are semi-neighborhoods of $I (y)$ and $I (z)$ (see Definition 3.2).

EQL (geo-equal):

$L$ EQL $Q$ iff $L_{j} \cap Q_{k} = L_{j} = Q_{k}, \forall j = k$ .

Note that the (geo-touchcrossing) operator is defined when the polylines cross and touch each other as shown in Figure 2(b)).

The 16-intersection matrix

In this section, we introduce the 16-intersection calculi matrix (16-intersection matrix for short) which is on the basis of our approach. The 16-intersection matrix for polyline–polyline features differs from the classical 9-intersection matrix⁷ for two main reasons. First, it extends the 9-intersection matrix by introducing the distinction between isolated single interior points ( $L_{i_{p}}$ ) and interior lines ( $L_{i_{l}}$ ) of the polylines. Second, each cell in the matrix provides additional information with respect to the 9-intersection matrix, corresponding to the number of connected components that are in the intersection between the SGOs. The formal definition of the 16-intersection matrix is given below.

Definition 4.1 [16-intersection matrix]

Given two polylines $L$ , $Q \in SGO$ , the 16-intersection matrix is defined by the following 4 × 4 matrix

\begin{matrix} \begin{matrix} ℒ_{i_{p}} \\ ℒ_{i_{l}} \\ ℒ_{b} \\ ℒ_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 0 \dots n & - & 0, 1, 2 & - \\ - & 0 \dots n & - & 0 \dots n \\ 0, 1, 2 & - & 0, 1, 2 & 0, 1, 2 \\ - & 0 \dots n & 0, 1, 2 & 1 \dots n \end{matrix}) \end{matrix}

where each element $(L_{j}, Q_{k}), j, k \in {i_{p}, i_{l}, b, e}$ is defined as follows

(ℒ_{j}, Q_{k}) = {\begin{array}{l} | I | & (j = i_{p}, k = i_{p}, b), (j = b, k = i_{p}, b, e), (j = e, k = b) \\ | C | & (j = i_{l}, k = i_{l}, e), (j = e, k = i_{l}, e) \\ - & i n c o m p a r a b l e \end{array}

and

I is the set of isolated single points in $L_{j} \cap Q_{k}$ ;

C is the set of connected components in $L_{j} \cap Q_{k}$ .

In the above matrix, for instance, the element $(L_{i_{p}}, Q_{i_{p}})$ of the matrix above denotes the number of isolated single points contained in the intersection between the interior points of the polyline $L$ and interior points of the polyline $Q$ . Similarly, the element $(L_{i_{l}}, Q_{e})$ denotes the number of lines contained in the intersection between single interior lines of the polyline $L_{i_{l}}$ and exterior of the polyline $Q_{e}$ . Note that, since we assume that a polyline has two end points, in any 16-intersection matrix, the sum of the cell contents in the third row, as well as in third column, is always equal to 2. In six cases, the elements of the matrix are incomparable. In fact, in four cases, namely, $(L_{i_{p}}, Q_{i_{l}})$ , $(L_{i_{l}}, Q_{b})$ , $(L_{b}, Q_{i_{l}})$ , $(L_{i_{l}}, Q_{i_{p}})$ , the comparison is performed between isolated single points and lines, and in the other two cases, namely $(L_{i_{p}}, Q_{e})$ , $(L_{e}, Q_{i_{p}})$ , the comparison is between isolated single points and portions of the $R^{2}$ space.

In order to further clarify the issue, in the following, an example of a pictorial query and the associated 16-intersection matrix related to the geo-operator CRS is given. As we observe, for instance, in this configuration, the polylines have four isolated single interior points in common, represented in the corresponding cell $(L_{i_{p}}, Q_{i_{p}})$ . Similarly, the contents of the other cells of the matrix are computed

\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 4 & - & 0 & - \\ - & 0 & - & 5 \\ 0 & - & 0 & 2 \\ - & 5 & 2 & 4 \end{matrix}) \end{matrix}

(1)

Note that in GeoPQL, the above configuration is re-conducted to the simple CRS configuration shown in the following, where the related 16-intersection is given as well

\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 1 & - & 0 & - \\ - & 0 & - & 2 \\ 0 & - & 0 & 2 \\ - & 2 & 2 & 1 \end{matrix}) \end{matrix}

(2)

The OCN graph

In the following, we address the notion of deformation in line with Egenhofer.²⁴ It is a unary operation consisting of one among movement, rotation, size, or shape modifications. Indeed, in this article, we prefer to use the term modification rather than deformation because the latter, in our opinion, is more appropriate to describe only the size and shape modifications. Furthermore, we assume that the size modification of a polyline has upper and lower bounds in order to guarantee that the polyline remains invariant and neither coincides with or subsumes $R^{1}$ , nor collapses to a point.

The notion of modification allows us to introduce below the definition of OCN graph for topological relationships, whose rationale is the same underlying the conceptual neighborhood graph defined in previous studies.^2,24

Definition 5.1 [OCN graph]

The OCN graph is a graph where each node is labeled by at most two geo-operators corresponding to a possible pictorial configuration, and an arc directly connects two nodes if and only if it is possible to transit from one configuration to another by applying one appropriate modification operation.

Neighborhood is defined by considering the continuous translation or deformation of objects within the given relation. For instance, if two polylines are not touching (i.e. they are disjoint), and one is moved toward the other, they must first touch before they cross. In essence, two nodes are adjacent if and only if the operations they denote can be transformed into one another by continuously modifying the related SGOs.²⁴

In Figure 3, the OCN graph of the polyline–polyline case is shown. This graph illustrates the transitions among six nodes, which are DSJ, TCH, CRS, INC, TCS, and EQL. Let us consider, for instance, the CRS node from which it is possible to transit to TCH, INC, TCS, and EQL nodes. Figure 4 shows these transitions. In particular, in Figure 4(a) and (b), the transition from CRS to TCH and INC nodes by applying, respectively, the movement and rotation modification operations are shown. Accordingly, in the transition from CRS to TCS by applying the rotation operation, we obtain the configuration shown in Figure 4(c), where the polylines have one internal line in common. Analogously, the transition from CRS to EQL occurs by applying the rotation operation if and only if the lengths of the polylines coincide (Figure 4(d)). The transitions related to the remaining nodes of the OCN graph can be defined similar to the above cases, and for the sake of simplicity they are not illustrated.

Figure 3.

The OCN graph of polyline–polyline topological relationships.

Figure 4.

Transitions from CRS to adjacent nodes.

Minimal 16-intersection matrix

In section “The 16-intersection matrix,” we have introduced the notion of 16-intersection matrix associated with two polylines, independently of the related geo-operators. Below, we address the 16-intersection matrices associated with two polylines by considering the geo-operators which are the labels of the OCN graph nodes discussed in the previous section.

Definition 6.1 [16-intersection matrices associated with two polylines]

Given two polylines, $L$ , $Q \in SGO$ , consider the set of geo-operators labeling the nodes of the OCN graph. The set of 16-intersection matrices associated with $L$ , $Q$ , indicated as $A (L, Q)$ , according to the related geo-operators is shown in Table 1.

The symmetric closure of the set of 16-intersection matrices $A (L, Q)$ is introduced.

Definition 6.2

Given two polylines $L$ , $Q \in SGO$ , consider the set $A (L, Q)$ defined above. The symmetric closure of $A (L, Q)$ , indicated as $A^{*} (L, Q)$ , is defined as follows

A^{*} (L, Q) = A (L, Q) \cup (⋃_{M \in A (L, Q)} M^{*})

where $M *$ is the symmetric of the matrix $M$ .

16-intersection matrix given below allows us to introduce the notion of minimal 16-intersection matrix.

Definition 6.3 [Equivalent 16-intersection matrix]

Consider a 16-intersection matrix $M$ related to the polylines $L$ , $Q \in SGO$ . A 16-intersection matrix $M'$ is equivalent to $M$ iff for each element of the matrices the following conditions holds

\forall i, j M_{ij} = 0 \Leftrightarrow M'_{ij} = 0

For instance, the 16-intersection matrices (1) and (2) given in section “The 16-intersection matrix” are equivalent. Note that these matrices differ only for the number of times the CRS operator is applied, as shown by the related configurations (four intersection points in the former, and one intersection point in the latter).

Definition 6.4 [Minimal 16-intersection matrix]

Given a 16-intersection matrix $M$ related to the polylines $L$ , $Q \in SGO$ , consider the set $E (M)$ of all possible 16-intersection matrices equivalent to $M$ . Then, $M$ is minimal iff the following conditions holds

\forall M' \neq M, M' \in ε (M) \Rightarrow M_{ij} ⩽ {M'}_{ij} \forall i, j .

Again, consider the above-mentioned 16-intersection matrices given in section “The 16-intersection matrix.” We will see in the theorem below that matrix (2) is the minimal in the set of 16-intersection matrices equivalent to (1).

Finally, we introduce the notion of external space connectivity of a pictorial configuration, allowing us to deal with a configuration whose external points form one connected component of the $R^{2}$ space.

Definition 6.5 [External space connectivity]

Given a pictorial configuration involving the SGOs $L$ , $Q$ . The external space of a configuration is connected iff $M_{4, 4} = 1$ in the related 16-intersection matrix $M$ .

For the sake of simplicity, the pictorial configurations satisfying the above definition will be referred to as externally connected pictorial configurations. For instance, in section “The 16-intersection matrix,” the pictorial configuration associated with matrix (1) is not externally connected (the element $M_{4, 4} = 4$ ), whereas the pictorial configuration associated with matrix (2) is externally connected (the element $M_{4, 4} = 1$ ).

We are able now to provide the set of minimal 16-intersection matrices associated with an externally connected pictorial configuration involving two polylines.

Theorem 6.1 [Set of minimal 16-intersection matrices]

Let $L$ , $Q \in SGO$ be two polylines satisfying Definition 6.5. The symmetric closure of $A (L, Q)$ , that is, $A^{*} (L, Q)$ , is the set of all possible minimal 16-intersection matrices associated with $L$ , $Q$ .

Proof

The proof is given in the Supplementary Material. In essence, it takes into account that, for each 16-intersection matrix $M$ in the set $A^{*} (L, Q)$ , the following holds:

External space connectivity rule. The element $M_{4, 4} = (L_{e}, Q_{e}) = 1$ . In fact, the external space to the polylines cannot be empty and cannot exceed 1 (according to Definition 6.5);

Polylines rule. Both the sums of the values of the second row and the second column are greater than zero. In fact, a portion of a (or the whole) polyline necessarily (i) overlaps the other polyline ( $(L_{i_{l}}, Q_{i_{l}}) > 0$ ) or (ii) is external to it ( $(L_{i_{l}}, Q_{e}) > 0$ ). Analogously for the second column.

Boundary points rule. Both the sums of the values of the third row and the third column are equal to 2. In fact, each of the two boundary points of a polyline is as follows: (i) internal ( $(L_{b}, Q_{i_{p}}) = 1 or 2$ ), or (ii) in common ( $(L_{b}, Q_{b}) = 1 or 2$ ), or (iii) external ( $(L_{b}, Q_{e}) = 1 or 2$ ) to the other polyline. Analogously for the third column.

Intersection rule. As a consequence of the external space connectivity rule, if the polylines intersect (i.e. by excluding the case related to DSJ operator), then $M_{2, 4} = M_{3, 4}$ ( $(L_{i_{l}}, Q_{e}) = (L_{b}, Q_{e})$ ) and $M_{4, 2} = M_{4, 3}$ ( $(L_{e}, Q_{i_{l}}) = (L_{e}, Q_{b})$ ).

In fact, if no portion or one (two) portion(s) of a polyline is (are) external to the other, then necessarily no boundary point or one (two) boundary point(s) is (are) external, respectively, and vice versa.

To summarize, the above theorem proves that each of the eleven 16-intersection matrices of Table 1 is minimal, and there are no other minimal 16-intersection matrices which can be associated with an externally connected pictorial configuration. Note that, in Table 1, the matrices (d) and (f), as well as (l) and (n), although corresponding to different configurations, coincide (see also section “Related work”).

Algorithm

As mentioned earlier, in the case of queries with null answers, our approach identifies the possible configurations that can approximate the user query according to the semantics of the geo-operators given in Definition 3.3, and the OCN graph of Figure 3. In the following, for a better illustration, we use $g o_{i} (i = 1, \dots, 6)$ ) and $N_{j} (j = 1, \dots, 6)$ notations to indicate a geo-operator and a node of the OCN graph, respectively.

In order to obtain an approximate answer, we refer to the OCN graph, which has been weighted, as shown in Figure 5. The weights have been computed by comparing the 16-intersection matrices of Table 1. In particular, we compute the total number of cells, whose values change from 0 (empty intersection) to a value equal to or greater than 1 (non-empty intersection), and vice versa. For the sake of simplicity, we refer to these cells as triggered cells. In the case of more than one matrix associated with a node of the graph, we select the minimal total number of triggered cells. For instance, let us consider the DSJ and INC nodes of the OCN graph. Their corresponding minimal matrices are shown in Table 1. As we observe, the number of triggered cells between DSJ and INC-(b) is 5, while this number in the case of DSJ and INC-(c) is 4. We select 4 which is the minimal between the total number of triggered cells. Therefore, this is also the label associated with the arc connecting the nodes DSJ and INC. Similarly, we compute the weights associated with the remaining arcs.

Figure 5.

Weighted OCN graph.

The query computation process is based on the following algorithm, called Computation Algorithm, which includes the Approximate Answer Computation algorithm for providing non-null answers to the user query. Essentially, it starts from the pictorial formulation of a query by the user, proceeds for a few steps for evaluating the intermediate results, and ends when one or more answers can be provided to the user, or such an answer cannot be computed at all. In the following, the application of the above algorithm to our running example is shown:

According to Step (1) of the algorithm, the user formulates the query Find the rivers that touch a railway. It is shown in Figure 1, in the GeoPQL working area, on the geographical database of Italy;

In Step (2), the GeoPQL system runs the query and identifies the TCH spatial relationship between the SGOs (Rivers 2 TCH Railway 1) (note that the numbers 1 and 2 represent the order by which the SGOs Railway and River have been drawn) as we can see in Figure 6 in the “Relation list” on the right side of the working area;

In Step (3), the system maps this geo-operator to the TCH node of the OCN graph (Figure 3);

In Step (4), the system assigns the starting node label to the node TCH in the OCN graph;

In Step (5), the result of this query is evaluated. It is null, and it is shown in “Found elements” of Figure 6 (see on the right side); consequently, the Approximate Answer Computation algorithm runs;

In Step (6), the system generates the queries related to CRS, TCS, DSJ, INC nodes which are adjacent to TCH, and for each node evaluates the query answers. The results about these queries are illustrated in Figures 7 –10, respectively;

According to Step (6)-(ii), two non-null answers are obtained: one corresponding to the CRS node and the other to the DSJ node. In the former case, 15 rivers crossing a railway are identified, in the latter only one river which is disjoint from a railway is found. Since the CRS and DSJ nodes are connected to the starting node TCH with the minimal weights 0, 1, respectively, the query answer related to the CRS node is provided to the user and the algorithm terminates.

COMPUTATION ALGORITHM

(1) The user formulates his/her pictorial query(2) The system runs the query and identifies the geo-operator

g o_{i} (1 \leq i \leq 6)

invoked by the query(3) The identified

g o_{i}

is mapped to the corresponding node

N_{j} (1 \leq j \leq 6)

in the OCN graph(4) Assign to

N_{j}

the label starting node

S_{p} (p : = 1)

(5) If the query answer is null then go to Step (6), else go to Step (8)

APPROXIMATE ANSWER COMPUTATION

(6) For each node

M_{k} (1 \leq k < 6)

adjacent to

S_{p}

the related queries are generated, the query answers are evaluated, and: (i) if only one non-null answer is obtained, then propose it to the user and go to Step (8); (ii) if two or more non-null answers are obtained, then propose to the user the answer(s) related to the nodes connected with

S_{p}

with the arc(s) with minimal weight(s) and go to Step (8) (iii) if all the query answers are null then: select the node(s)

M_{k}

connected to the arc(s) with minimal weight(s);

p : = p + 1, q : = p

, and assign the label starting node

S_{p}

to each

M_{k}

; if

S_{p} \equiv M_{k}

with

1 \leq p < q

then go to Step (7) else go to Step (6)

(7) Give “No Solution found” and go to Step (8)

(8) Exit

Figure 6.

TCH operator identification and query result.

Figure 7.

Result of the query approximation by the CRS operator.

Figure 8.

Result of the query approximation by the TCS operator.

Figure 9.

Result of the query approximation by the DSJ operator.

Figure 10.

Result of the query approximation by the INC operator.

The system implementation

GeoPQL is a stand-alone tool whose pictorial functions have been integrated with ESRI-ArcGIS^® (www.esri.com/software/arcgis/) in order to exploit its basic browsing and drawing functions. In GeoPQL, the geo-data warehouse is saved to the shape file format and is managed by the application of ESRI ArcMap. ArcMap represents geographic information as a collection of layers, where each layer corresponds to a particular dataset overlayed in the map. In this work, in GeoPQL, we introduced new functionalities that take into account the 16-intersection matrix and the Computation Algorithm presented above, as described below. In order to provide approximate answers to pictorial queries with null results, in the system any 16-intersection matrix is re-conducted to one of the minimal 16-intersection matrices shown in Table 1.

Let us illustrate the implementation of the 16-intersection matrix with an example. Consider the 16-intersection matrix (1) given in section “The 16-intersection matrix.” It is shown on the bottom left of Figure 11. As we can observe, the content of the 16-intersection matrix illustrated on the top left of the above-mentioned figure represents the type of the intersections results, that is, 0, 1, and 2, which stand for point, polyline, and polygon, respectively, according to the native representation of the Open GIS Consortium-OGC^® environment (www.opengeospatial.org/standards). Note that this representation has been proposed in the OGC environment for the 9-intersection matrix and in this work, we extended it to the 16-intersection matrix. The matrix indicated on the bottom of the same figure is our proposed one, and contains in each cell the number of connected components that are in the intersection between the SGOs.

Figure 11.

Example of an implemented 16-intersection matrix.

Regarding the implementation of the 16-intersection matrix, we invoked in GeoPQL the open-source Java libraries JTS Topology Suite (www.vividsolutions.com/jts/JTSHome.htm), which has been widely used in Open GISs. JTS Topology Suite is an API of two-dimensional (2D) spatial predicates and functions, and provides a complete, consistent, and robust implementation of the fundamental 2D spatial analysis methods. It conforms to the Simple Features Specification (www.opengeospatial.org/standards) for SQL which is published by OGC.

In order to correctly implement the OCN graph, we used the graphical modeling language Unified Modeling Language (UML) of Open-Source software Argo UML (argouml.tigris.org), where we have defined objects, classes, and inheritance relationships. In Figure 12, the UML representation of the OCN graph is shown, where the attributes are required to allow the correct interaction of the classes. The classes that have been created correspond to the pictorial configurations and the related 16-intersection matrices shown in Table 1. In the class definition, an attribute that takes into account an identifier of the 16-intersection matrix, referred to as 16-character string, has been considered. For instance, the identifier of the pictorial configuration associated with the 16-intersection matrix (1) given in section “The 16-intersection matrix” is $1 F 0 FF 0 F 20 F 02 F 221$ (see top-left of Figure 11), where each set of four characters corresponds to the four rows of the 16-intersection matrix, respectively. Note that, according to the OGC standards, the character “F” represents the incomparable intersection operations, and “0,”“1,” and “2” stand for point, polyline, and polygon intersections, respectively (section “The 16-intersection matrix”). This identifier, in our approach, corresponds to the following: $4 F 0 FF 0 F 50 F 02 F 524$ , where the numbers of connected components in the related kind of intersections have been taken into account (see bottom-left of Figure 11). As shown in Figure 11, the system allows the user to visualize on the bottom-left the 16-intersection matrix associated with his/her pictorial query and compare it with the matrix on the top-left, obtained by following the native representation of the OGC environment.

Figure 12.

UML representation of the OCN graph.

Our algorithm has been implemented with the Java language, which imports the UML class instances generated by Argo UML. The OCN graph has been developed in the context of a package, called GeoPQL.polyline-polyline.

Comparison of the 16-intersection matrix with other matrices

In this subsection, the 16-intersection matrix will be compared with the DE-9IM proposal,^8,25 and the three 9-intersection matrices presented in D’Ulizia et al.^38,39 In order to better clarify the issue, consider Figure 2(a) and (b) in section “Revised GeoPQL operators.” Below $L_{i}$ , $L_{b}$ , and $L_{e}$ denote the internal, boundary, and external points of the polyline $L$ , respectively (analogously for $Q$ ). Let us consider the DE-9IM, which is a standard in GISs, where each cell represents the maximum number of dimensions of the intersections of the polylines, on the basis of their interior, boundary, and exterior points. The pictorial configurations of Figure 2(a) and (b) in section “Revised GeoPQL operators” can be distinguished according to the DE-9IM, and they are, respectively

\begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 0 & F & 1 \\ F & F & 0 \\ 1 & 0 & 2 \end{matrix}) \end{matrix} \begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 1 & F & 1 \\ F & F & 0 \\ 1 & 0 & 2 \end{matrix}) \end{matrix}

where 0, 1, 2, and F stand for points, lines, areas, and empty intersections, respectively. Note that these matrices differ only for the element ( $L_{i}, Q_{i}$ ) because the intersections of the interior points of the polylines of Figure 2(a) and (b) are one point and one line (zero and one dimensions), respectively.

Let us now focus on the proposal defined in D’Ulizia et al.^38,39 In the mentioned papers, given a topological relationship, three 9-intersection matrices, here referred to as 3 × 9-intersection matrices, are defined, corresponding to point, polyline, and polygon intersections. In the case of Figure 2(a), we have the following 3 × 9-intersection matrices

\begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 1 & 0 & \infty \\ 0 & 0 & 2 \\ \infty & 2 & \infty \end{matrix}) \end{matrix} \begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 0 & 0 & 2 \\ 0 & 0 & 0 \\ 2 & 0 & \infty \end{matrix}) \end{matrix} \begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) \end{matrix}

where, for instance, the element ( $L_{i}$ , $Q_{i}$ ) of the first matrix is 1 because the intersection between the internal points of the polylines is one single point. The corresponding elements in the remaining matrices are 0 because these intersections are not either polylines or regions, respectively. In the case of Figure 2(b), the 3 × 9-intersection matrices are given below

\begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ \infty & 0 & \infty \\ 0 & 0 & 2 \\ \infty & 2 & \infty \end{matrix}) \end{matrix} \begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 1 & 0 & 2 \\ 0 & 0 & 0 \\ 2 & 0 & \infty \end{matrix}) \end{matrix} \begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) \end{matrix}

In this case, the element ( $L_{i}$ , $Q_{i}$ ) of the first matrix is $\infty$ according to the approach of the authors. The corresponding element is 1 in the second matrix, which means that such an intersection is one polyline, and 0 in the third matrix because this intersection is not a region.

Let us analyze the corresponding 16-intersection matrices proposed in our work. In the case of the configuration of Figure 2(a), we have already shown that the related 16-intersection matrix is the matrix (d) given in Table 1, whereas, in the case of Figure 2(b), it corresponds to the matrix (n) in the same table.

Consider now the pictorial configuration given in Figure 13, where the intersection of the interior points of the polylines contains both these dimensions, that is, one point and one line. The matrix representing this configuration according to DE-9IM is the following

\begin{matrix} \begin{matrix} L_{i} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i} & Q_{b} & Q_{e} \\ 1 & F & 1 \\ F & F & 0 \\ 1 & 0 & 2 \end{matrix}) \end{matrix}

which coincides with the matrix representing the configuration of Figure 2(b). In fact, the element ( $L_{i}, Q_{i}$ ) corresponds to the maximum number of dimensions in the intersection of the interior points of the polylines, that is, 1. According to this model, it is not possible to represent additional lower dimension intersections in the same matrix (a zero-dimensional intersection besides a one-dimensional intersection). Whereas, according to our proposal, it is possible to represent both these dimensions in the same 16-intersection matrix, as follows

\begin{matrix} \begin{matrix} L_{i_{p}} \\ L_{i_{l}} \\ L_{b} \\ L_{e} \end{matrix} & (\begin{matrix} Q_{i_{p}} & Q_{i_{l}} & Q_{b} & Q_{e} \\ 1 & - & 0 & - \\ - & 1 & - & 3 \\ 0 & - & 0 & 2 \\ - & 3 & 2 & 2 \end{matrix}) \end{matrix}

where the zero- and one-dimensional intersections of the interior points of the polylines are represented by the elements ( $L_{i_{p}}, Q_{i_{p}}$ ) and ( $L_{i_{l}}, Q_{i_{l}}$ ), respectively.

Figure 13.

Zero- and one-dimensional intersections of polylines.

Conclusion

In this article, we proposed an approach which provides approximate answers to polyline–polyline pictorial queries with null results. It is based on the notions of minimal 16-intersection matrix associated with a pictorial configuration, and OCN graph. A theorem has been provided which identifies a set of minimal 16-intersection matrices and proves that this set is minimal, that is, the 16-intersection matrix associated with any pictorial configuration is equivalent to one belonging to this set. The set of minimal 16-intersection matrices enabled us to devise the Approximate Answer Computation algorithm, providing approximate answers to the users. As a future work, we are planning to introduce the notion of semi-plan in the 16-intersection matrix, in order to distinguish the matrices associated with different configurations (see the matrices (d)–(f), and (l)–(n) in Table 1), as well as to investigate the proposed approach in the cases of the polygon–polyline and polygon–polygon topological relationships.

Footnotes

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Dutta

Approximate spatial reasoning: integrating qualitative and quantitative constraints. Int J Approx Reason1991; 5(3): 307–330.

Freksa

Röhrig

Dimensions of qualitative spatial reasoning. In: Piera Carretè

Singh

(eds) Qualitative reasoning and decision technologies: proceedings of the QUARDET93. Barcelona: CIMNE, 1993, pp. 483–492.

Escrig

Toledo

Qualitative spatial reasoning: theory and practice (volume 47 of frontiers in artificial intelligence and applications). Amsterdam: IOS Press, 1998.

Cohn

Hazarika

Qualitative spatial representation and reasoning: an overview. Fundam Inform2001; 46(1–2): 1–29.

Cui

Cohn

Randell

DA.

Qualitative and topological relationships in spatial databases. In: DJ

Abel

Chin Ooi

(eds) Proceedings of the SSD 1993: lecture notes in computer science, vol. 692. London: Springer-Verlag, 1993, pp. 296–315.

D’Onofrio

Pourabbas

Modelling temporal thematic map contents. J ACM SIGMOD Rec2003; 32(2): 34–41.

Egenhofer

. Reasoning about binary topological relations. In: Proceedings of the SSD 1991: lecture notes in computer science (Proceedings of the second international symposium on advances in spatial databases), vol. 525. London: Springer-Verlag, 1991, pp. 143–160.

Egenhofer

Franzosa

RD.

Point-set topological spatial relations. Int J Geograph Inform Syst1991; 5(2): 161–174.

Kuipers

Qualitative reasoning: modeling and simulation with incomplete knowledge. Automatica1999; 25(4): 571–585.

10.

Frank

AU.

The use of geographical information systems: the user interface is the system. In: Medyckyj-Scott

Hearnshaw

(eds) Human factors in geographical information systems. London: Belhaven Press, 1993, pp. 15–31.

11.

Medyckyj-Scott

Hearnshaw

(eds). Human factors in geographical information systems. London: Belhaven Press, 1993.

12.

Frank

AU.

Qualitative spatial reasoning: cardinal directions as an example. Int J Geograph Inform Syst1996; 10(3): 269–290.

13.

Schultz

CPL

Clephane

Guesgen

. Utilization of qualitative spatial reasoning in geographic information systems. In: Riedl

Kainz

Elmes

(eds) Progress in spatial data handling: international symposium on spatial data handling. Berlin, Heidelberg: Springer-Verlag, 2006, pp. 27–42.

14.

Kuhn

Metaphors create theories for users. In: Frank

Campari

(eds) Proceedings of the COSIT 1993: lecture notes in computer science, vol. 716. London: Springer-Verlag, 1993, pp. 366–376.

15.

Egenhofer

MJ.

Query processing in spatial-query-by-sketch. J Visual Lang Comput1997; 8(4): 403–424.

16.

Aoidh

Bertolotto

Wilson

DC.

Understanding geospatial interests by visualizing map interaction behavior. Inform Visual2008; 7: 275–286.

17.

Kapler

Wright

Geotime information visualization. Inform Visual2005; 4: 136–146.

18.

Calcinelli

Mainguenaud

Cigales a visual language for geographic information system: the user interface. J Visual Lang Comput1994; 5(2): 113–132.

19.

Lee

Chin

FL.

An iconic query language for topological relationship in GIS. Int J Geograph Inform Syst1995; 9(1): 25–46.

20.

Ferri

Rafanelli

GeoPQL: a geographical pictorial query language that resolves ambiguities in query interpretation. In: Ferri

Rafanelli

(eds) Journal of data semantics III: lecture notes on computer science, vol. 3534. London: Springer-Verlag, 2005, pp. 50–80.

21.

Papadias

Sellis

A pictorial query-by-example language. J Visual Lang Comput1995; 6(1): 53–72.

22.

Catarci

Visual query languages. In: Liu

Ozsu

(eds) Encyclopedia of database systems. New York: Springer, 2009, pp. 3399–3405.

23.

Ferri

Pourabbas

Rafanelli

. The syntactic and semantic correctness of pictorial configurations to query geographic databases by PQL. In: Proceedings of the 2002 ACM symposium on applied computing (SAC 2002), Madrid, 11–14 March 2002, pp. 432–437. New York: ACM.

24.

Egenhofer

. The family of conceptual neighborhood graphs for region-region relations. In: Fabrikant

Reichenbacher

van Krevald

. (eds) Proceedings of GIScience 2010: lecture note in computer science, vol. 6292. London: Springer-Verlag, 2010, pp. 42–55.

25.

Clementini

Di Felice

van Oosterom

A small set of formal topological relationships suitable for end-user interaction. In: DJ

Abel

Chin Ooi

(eds) Proceedings of SSD 1993: lecture notes in computer science, vol. 692. London: Springer-Verlag, 1993, pp. 277–295.

26.

Freska

Cognitive and linguistic aspects of geographic space. In: Mark

Frank

(eds) Qualitative spatial reasoning. Drodrecht: Kluwer Academic Publishers, 1991, pp. 361–372.

27.

Abdelmoty

Williams

. Approaches to the representation of qualitative spatial relationships for geographic databases. In: Proceedings of the advanced geographic data modeling (AGDM’94): international GIS workshop, no. 40, Delft, The Netherlands, 12–14 September 1994, pp. 204–216. Delft: The Netherlands Geodetic Commission (Publications on Geodesy).

28.

Deng

A hierarchical representation of line-region topological relations. Int Arch Photogramm Rem Sens Spatial Inform Sci2008; XXXVII(Pt B2): 25–30.

29.

A complete classification of topological relations using 9-intersection method. Int J Geograph Inform Syst2006; 20(6): 589–610.

30.

Liu

Shi

WZ.

Extended model of topological relations between spatial objects in geographic information systems. Int J Appl Earth Obs2007; 9: 264–275.

31.

Schultz

CPL

Guesgen

Amor

. Computer-human interaction issues when integrating qualitative spatial reasoning into geographic information systems. In: Proceedings of the 7th ACM SIGCHI New Zealand chapter’s international conference on computer-human interaction: design centered HCI (CHINZ 2006), Christchurch, New Zealand, 6–7 July 2006, pp. 43–51. New York: ACM.

32.

Sebillo

Tortora

Vitiello

The metaphor GIS query language. J Visual Lang Comput2000; 11(4): 439–454.

33.

Nedas

Egenhofer

Wilmsen

Metric details of topological line-line relations. Int J Geograph Inform Syst2007; 21(1): 21–48.

34.

Pereira Reis

Egenhofer

Matos

Conceptual neighborhoods of topological relations between lines. In: Ruas

Gold

(eds) Headway in spatial data handling: 13th international symposium on spatial data handling (SHD’08). Berlin, Heidelberg: Springer, 2008, pp. 557–574.

35.

Formica

Mazzei

Pourabbas

. A 16-intersection matrix for the polygon-polyline topological relation for geographic pictorial query languages. In: Quirchmayr

BAsl

You

. (eds) Multidisciplinary research and practice for information systems (Lecture notes on computer science), vol. 7465. London: Springer-Verlag, 2012, pp. 302–316.

36.

Formica

Pourabbas

Rafanelli

Constraint relaxation of the polygon-polyline topological relation for geographic pictorial query languages. Comput Sci Inf Syst2013; 10(3): 1053–1075.

37.

Belussi

Catania

Podestà

Topological operators: a relaxed query processing approach. GeoInformatica2012; 16(1): 67–110.

38.

D’Ulizia

Ferri

Grifoni

. Relaxing constraints on GeoPQL operators to improve query answering. In: Stéphane

Josef

Wagner

(eds) Proceedings of the DEXA 2006: lecture notes in computer science, vol. 4080. London: Springer-Verlag, 2006, pp. 728–737.

39.

D’Ulizia

Ferri

Grifoni

. Constraint relaxation on topological operators which produce a null value as answer to a query. In: Proceedings of the information resources management association (IRMA 2007), Vancouver, BC, Canada, 19–23 May 2007.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.16 MB