# A 16-Intersection Matrix for the Polygon-Polyline Topological Relation for Geographic Pictorial Query Languages

Anna Formica, Mauro Mazzei, Elaheh Pourabbas, Maurizio Rafanelli

► To cite this version:

Anna Formica, Mauro Mazzei, Elaheh Pourabbas, Maurizio Rafanelli. A 16-Intersection Matrix for the Polygon-Polyline Topological Relation for Geographic Pictorial Query Languages. International Cross-Domain Conference and Workshop on Availability, Reliability, and Security (CD-ARES), Aug 2012, Prague, Czech Republic. pp.302-316, 10.1007/978-3-642-32498-7_23 . hal-01542449

HAL Id: hal-01542449

https://inria.hal.science/hal-01542449

Submitted on 19 Jun 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A 16-intersection matrix for the Polygon-Polyline Topological Relation for Geographic Pictorial Query Languages

A. Formica, M. Mazzei, E. Pourabbas, M. Rafanelli

National Research Council
Istituto di Analisi dei Sistemi ed Informatica "Antonio Ruberti"
Viale Manzoni 30, I-00185, Rome, Italy
{anna.formica,mauro.mazzei,elaheh.pourabbas,maurizio.rafanelli}@iasi.cnr.it

**Abstract.** In this paper we address the problem of formalizing qualitative topological relationships between geographical objects in a Geographical Pictorial Query Language (GeoPQL) in order to completely capture the semantics of the user queries. We focus on the polygon-polyline topological relation and we define a 16-intersection matrix that has been conceived to enhance and distinguish the semantics of cells' content with respect to the well-known 9-intersection matrix. On the basis of such distinctions, we revise the geographic operators of GeoPQL and we give their formal semantics. In order to implement our proposed 16-matrix, we invoked in GeoPQL the open source Java libraries JTS Topology Suite, which conforms to the Simple Features Specification for SQL published by the Open GIS Consortium-OGC. Finally, the proposed 16-intersection matrix is illustrated through some query examples.

**Keywords:** Pictorial query languages, topological relationships, intersection matrix.

## 1 Introduction

Human knowledge about spatial world is necessarily approximate, and *spatial reasoning* is an area where humans consistently reason approximately with good results [11]. Approximate qualitative spatial reasoning is a research area that has been conceived to represent commonsense reasoning and to incorporate such reasoning techniques in computer systems [16]. In particular, this research area deals with the development of techniques and tools for reasoning with non-metrical and incompletely specified spatial knowledge [6]. In this context, most studies focused on fundamental aspects of space such as topology, orientation, size, and shape. These topics have been extensively investigated since more than one decade both at a mathematical level [7], and within Geographic Information Systems (GIS) [20] [22] [23] [27]. The remarkable amount of studies in these directions aimed at including qualitative reasoning methods in standard GISs in order to overcome the key limitations of these systems which are entirely based
on numerical methods [6] [21]. Indeed, numerical approaches for representing and reasoning on spatial information are ineffective to process imprecise or uncertain data [30]. For this reason, advanced GISs must provide an effective and accessible query system to appropriately capture a user's desired search criteria and a user's mental query model [17] [18]. Specifically, the user's query mental model is the user's perception regarding the semantics of the query in his/her mind.

In general, geographic queries can be better expressed by using graphical metaphors in query languages. They are powerful to express the user's query mental model [24], and to exploit the semantics of data models in order to facilitate query formulation. In the field of spatial databases many authors studied the way to formulate queries using graphical configurations, and to embed them into query languages, for instance [18] [28]. In particular, in [18] the authors proposed a pictorial query language, called *Geographical Pictorial Query Language* (GeoPQL), to address the user's query mental model and to answer to his/her queries. They defined a set of Symbolic Graphical Objects (SGOs) to graphically represent the spatial configurations of geographic entities (i.e., *point*, *polyline*, and *polygon*), the spatial relationships of pairs of SGOs, as well as the spatial operators based on an Object-Calculus. In this paper, we refer to GeoPQL. Indeed, the formalization of qualitative topological relationships between spatial objects is one of the main topics in the representation and manipulation of spatial data. In order to characterize such topological relationships, the well-known 9-Intersection matrix is extensively used [12].

Suppose the user wants to find all the Italian regions which are passed through by a river. This query can be graphically represented in the GeoPQL working area, for instance, by means of one of the pictorial queries shown in Figures 1 and 2, where regions and rivers are represented by polygons and polylines, respectively. With respect to the pictorial query shown in Figure 1, the one given in Figure 2 also requires that an internal part of the river is on the boundary of (touches) the region. The 9-Intersection matrices related to these figures differ for only one value, i.e., in correspondence to the intersection between the boundary of the polygon and the interior of the polyline. In particular, according to the standard notation in the OGC environment [3], in the case of Figure 1, it is 0, meaning that the dimension of the intersection is a point, whereas in the case of Figure 2, it is 1 meaning that this dimension is a line.

However, often the abstractions of spatial relationships defined in the literature cannot efficiently capture the variety of semantics associated with the user queries. For instance, in the case of Figure 2, the intersection between the boundary of the polygon and the interior of the polyline consists of three points and one line. This level of detail can not be incorporated in a unique 9-intersection matrix. For this reason, in [9], [10], three different 9-intersection matrices, representing point, polyline, and polygon intersection results, respectively, have been introduced.

In this paper, we focus on this problem and we propose a 16-intersection matrix, which is the main contribution of this paper, which enables us to embed in a unique matrix the point, polyline, and polygon intersection results.
<figure><img src="image_2.png" /><figcaption>Fig. 1. A pictorial representation of a pass through relationship in GeoPQL</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2. A pictorial representation of pass through and touch relationships in GeoPQL</figcaption></figure>
Essentially in our proposed matrix, we enhance the semantics of the interior and boundary of a polyline and a polygon, respectively. Specifically, the interior of a polyline is decomposed into isolated single interior points ($\mathcal{L}_{i_p}$) and interior lines $\mathcal{L}_{i_t}$. Similarly, the boundary of a polygon is decomposed into isolated single boundary points ($P_{b_s}$) and boundary lines ($P_{b_t}$). In particular, with respect to the well-known matrices proposed in the literature where for each cell only null or non-null intersections are given, the 16-intersection matrix provides, for a given topological relationship, the number of connected components that are in the intersection of the pair of SGOs. On the basis of such distinctions, we revise the geographic operators of GeoPQL and we give their formal semantics. These formalizations allow us not only to precisely distinguish each operator but also to define composite operators that correspond to the combination of different topological relationships. For instance, in both the aforementioned figures, the geo-operator corresponding to the topological relationship is “pass-through” but, in the case of Figure 2, it is also combined with the “touch” operator. In order to implement our proposal, we invoked in GeoPQL the open source Java libraries JTS Topology Suite [4], which conforms to the Simple Features Specification for SQL published by the Open GIS Consortium-OGC.

The paper is structured as follows. In Section 2, the GeoPQL operators are revised. In Section 3, the 16-intersection matrix is formally defined and some examples are given in order to clarify it from a graphical point of view. In the same section, a query example is provided in order to show our proposal. In Section 4, we illustrate the implemented 16-intersection matrix in GeoPQL. In Section 5 the related work follows, and in Section 6 the conclusion is given.

## 2 Revised GeoPQL operators

In this paper, among the possible geographical pictorial languages proposed in the literature, we focus on GeoPQL [18]. Below, we start by recalling the notion of Symbolic Geographical Objects (SGOs).

**Definition 21 [SGO].** Given a Geographic Information System, a Symbolic Geographical Object (SGO) is a 5-tuple $\psi = (id,geometric_type, objclass, \Sigma, \Lambda)$ where:

- id is the SGO identifier assigned by the system to uniquely identify the SGO in a query;

- geometric_type can be a point, a polyline or a polygon;

- objclass is the geographical concept name belonging to the database schema and iconized by the SGO, identifying a geographical class (set of instances) of the database;

- $\Sigma$ represents the set of typed attributes of the SGO which can be associated with a set of values by the user;

- $\Lambda$ is an ordered set of pairs of coordinates, which defines the spatial extent, and position of the SGO with respect to the coordinate reference system of the working area.
The GeoPQL algebra consists of 12 binary geo-operators, 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))<fnref n="1" />, Geo-crossing (CRS), Geo-pass-through (PTH), Geo-overlapping (OVL), Geo-equality (EQL)). Our focus is on the polygon-polyline relation, therefore in this paper we will consider a subset of the topological operators, namely, disjoint (DSJ), inclusion (INC), touch (TCH), and pass through (PTH). Indeed, the remaining operators are not considered because in the case of the polygon-polyline relation they are not applicable (see for instance CRS which is defined between two polylines, OVL which is defined between two polygons, or EQL which is defined for two polylines or two polygons).

The formal semantics of the above mentioned operators is formally given in the Definition 22 below. 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 polygon $\mathcal{P}$ and a polyline $\mathcal{L}$, in our approach, $P_i, P_{b_p}, P_{b_l}, P_e$ denote the interior, single boundary points, boundary lines and exterior of the polygon $\mathcal{P}$, respectively, and $\mathcal{L}_{i_p}, \mathcal{L}_{i_l}, \mathcal{L}_b, \mathcal{L}_e$, denote single interior points, interior lines, boundary points (or end points) and exterior of the polyline $\mathcal{L}$.

With respect to the existing literature, where there is no distinction between isolated single boundary points and boundary lines of a polygon, and between isolated single interior points and interior lines of a polyline, in our approach the different notations, namely $P_{b_p}, P_{b_l}$ for a polygon, and $\mathcal{L}_{i_p}, \mathcal{L}_{i_l}$ for a polyline, are respectively introduced. They allow us to distinguish different configurations, as for instance the ones shown in Figure 3, where the intersection between a polygon and a polyline consists of one isolated point, case (a), or a line, case (b). These configurations correspond to two different pictorial queries that the user can draw to represent the TCH geo-operator but they have different computational models, as we will see in the next section.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Boundary point vs boundary line intersections</figcaption></figure>

<footnote n="1">¹ Note that in our approach the operators *cover* and *covered-by*, extensively used in the literature, can be represented by using the INC geo-operator.</footnote>
For the sake of simplicity, in the rest of this paper we will consider the
geometric_type component of a SGO. In particular, due to the focus of our
paper, we will concentrate on the polygon and polyline geometric types.

**Definition 22 [Geo-operators].** Let SGO be the set of all possible SGOs.
Given a polygon P, and a polyline L both in SGO, the binary geo-operations
DSJ, INC, TCH, and PTH are formally defined as follows, where $k \in \{i,b_p,b_l,e\}$,
and $j \in \{i_p,i_l,b,e\}$:

- DSJ (geo-disjunction):

$$
\mathcal{P} \text{ DSJ } \mathcal{L} \text{ iff } \mathcal{P}_k \cap \mathcal{L}_j = \emptyset \text{ } j, k \neq e
$$

- INC (geo-inclusion):

$$
\mathcal{P} \text{ INC } \mathcal{L} \text{ iff } \mathcal{P}_k \cap \mathcal{L}_j = \mathcal{L}_j, k = i, j = i_p
$$

- TCH (geo-touching):

assume $S = \mathcal{L}_j \cap \mathcal{P}_k \neq \emptyset$ where $j \neq e$ and $k = b_l, b_p$. $\mathcal{P}$ TCH $\mathcal{L}$ iff $\forall x \in S$, and $\forall I(x)$, where $I(x)$ is a neighborhood of $x$, the following holds:

$$
I(x) \cap \mathcal{L}_j \cap \mathcal{P}_e = \emptyset \text{ or } I(x) \cap \mathcal{L}_j \cap \mathcal{P}_i = \emptyset, j \neq e.
$$

- PTH (geo-pass-through):

$$
\mathcal{P} \text{ PTH } \mathcal{L} \text{ iff } \mathcal{P}_k \cap \mathcal{L}_{i_l} \neq \emptyset, k = i, e.
$$

According to the definition above, for instance, both the configurations given
in Figure 3 correspond to the TCH operator, where in the case (a) one single
interior point of the polyline is in common to the boundary of the polygon, and
in case (b) one interior line of the polyline is in common to the boundary of
the polygon. Note that, in the case (b) we assume that the number of isolated
single points which are in common between the boundary of the polygon and
the polyline is zero.

In our approach, it is possible to have pictorial queries by combining two
geo-operators, i.e., TCH + PTH, and TCH + INC. In such cases, the semantics
of the *composite* geo-operators requires that the above definition holds for both
the involved geo-operators.

3 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 ma-
trix 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 boundary points (*P*<sub>b<sub>p</sub></sub>) and boundary lines (*P*<sub>b<sub>l</sub></sub>) of the polygon, as well
as the distinction between isolated single interior points (*L*<sub>i<sub>p</sub></sub>) and interior lines
(*L*<sub>i<sub>l</sub></sub>) of the polyline. Second, each cell in the matrix contains a number providing
additional information with respect to the 9-intersection matrix, corresponding
to the number of connected components that are in the intersection between the
pair of SGOS. Below, the formal definition of the 16-intersection matrix is given.
**Definition 31 [16-intersection matrix].** Given a polygon $\mathcal{P} \in \mathcal{SGO}$, and a
polyline $\mathcal{L} \in \mathcal{SGO}$, the 16-intersection matrix is defined by the following 4x4
matrix:

$$
\mathcal{L}_{i_p} \begin{pmatrix} \mathcal{P}_i & \mathcal{P}_{b_p} & \mathcal{P}_{b_l} & \mathcal{P}_e \\ - & 0 \dots n & - & - \\ 0 \dots n & - & 0 \dots n & 0 \dots n \\ 0, 1, 2 & 0, 1, 2 & - & 0, 1, 2 \\ 1 \dots n & - & 1 \dots n & 1 \dots n \end{pmatrix}
$$

where each element ($\mathcal{L}_j, \mathcal{P}_k$), $j \in \{i_p, i_l, b, e\}$ and $k \in \{i, b_p, b_l, e\}$ is defined as
follows:

$$
(\mathcal{L}_j, \mathcal{P}_k) = \begin{cases} |I| & (j = i_p, k = b_p), (j = b, k \neq b_l) \\ |C| & (j = e, i_l, k \neq b_p) \\ - & \text{incomparable} \end{cases}
$$

and:

- I is the set of isolated single points in $\mathcal{L}_j \cap \mathcal{P}_k$;

- C is the set of connected components in $\mathcal{L}_j \cap \mathcal{P}_k$.

Note that, since the end points of a polyline are two, in any 16-intersection
matrix the sum of the numbers in the third row is always equal to two.

For instance, the element ($\mathcal{L}_e, \mathcal{P}_i$) of the matrix above denotes the number
of connected components (polygons) contained in the intersection between the
interior points of the polygon and the external points of the polyline. Similarly,
the element ($\mathcal{L}_{i_p}, \mathcal{P}_{b_p}$) denotes the number of isolated single points contained in
the intersection between single interior points of the polyline and single boundary
points of the polygon.

In six cases the elements of the matrix are incomparable. In fact, in three
cases, namely ($\mathcal{L}_{i_p}, \mathcal{P}_{b_l}$), ($\mathcal{L}_{i_l}, \mathcal{P}_{b_p}$), ($\mathcal{L}_b, \mathcal{P}_{b_l}$), the comparison is performed be-
tween isolated single points and lines, and in the other three cases, namely
($\mathcal{L}_{i_p}, \mathcal{P}_i$), ($\mathcal{L}_{i_p}, \mathcal{P}_e$), ($\mathcal{L}_e, \mathcal{P}_{b_p}$), the comparison is between isolated single points
and portions of the $\mathcal{R}^2$ space.

In order to further clarify the issue, in the following subsection a query ex-
ample is shown.

**3.1 A query example**

Consider the following user query *q*:

Find all the Italian regions that are passed through by a river.

As already mentioned in the Introduction, this query, which involves the PTH
operator, can be specified by using different pictorial representations. For in-
stance, the one shown in Figure 4 (a) is a possible pictorial query of *q*. The
16-intersection matrix corresponding to this configuration is the following:
<figure><img src="image_5.png" /><figcaption>Fig. 4. Two possible pictorial representations of q</figcaption></figure>

$$ (m_1) \quad \begin{array}{c} \mathcal{L}_{i_p} \\ \mathcal{L}_{i_l} \\ \mathcal{L}_b \\ \mathcal{L}_e \end{array} \begin{pmatrix} \mathcal{P}_i & \mathcal{P}_{b_p} & \mathcal{P}_{b_l} & \mathcal{P}_e \\ - & 6 & - & - \\ 3 & - & 0 & 4 \\ 0 & 0 & - & 2 \\ 4 & - & 6 & 3 \end{pmatrix} $$

In fact, we have:

- six points which are single boundary points of the polygon and single interior points of the polyline (element $(\mathcal{L}_{i_p}, \mathcal{P}_{b_p})$ of the matrix, see Figure 5-(a));

- three connected components (polylines) which belong to the polyline and interior of the polygon (element $(\mathcal{L}_{i_l}, \mathcal{P}_i)$ of the matrix, see Figure 5-(b));

- four connected components (polylines) which belong to the polyline and the exterior of the polygon (element $(\mathcal{L}_{i_l}, \mathcal{P}_e)$ of the matrix, see Figure 5-(c));

- two boundary points of the polyline which are exterior points of the polygon (element $(\mathcal{L}_b, \mathcal{P}_e)$ of the matrix, see Figure 5-(d));

- four connected components (polygons) that are internal to the polygon and external to the polyline (element $(\mathcal{L}_e, \mathcal{P}_i)$ of the matrix, see Figure 5-(e));

- six connected components (polylines) that are external to the polyline and are the boundary lines of the polygon (element $(\mathcal{L}_e, \mathcal{P}_{b_l})$ of the matrix, see Figure 5-(f));

- three connected components (polygons) that are external to the polygon and external to the polyline (element $(\mathcal{L}_e, \mathcal{P}_e)$ of the matrix, see Figure 5-(g)).

A simpler pictorial representation of $q$ is, for instance, shown in Figure 4 (b). Indeed $q$ can be represented in an equivalent way by one of the two pictorial queries shown in Figures 4 (a) and (b) representing the PTH operator, but the corresponding 16-intersection matrices are different. The 4x4 matrix corresponding to the simpler pictorial query of Figure 4 (b) is shown below:

$$ (m_2) \quad \begin{array}{c} \mathcal{L}_{i_p} \\ \mathcal{L}_{i_l} \\ \mathcal{L}_b \\ \mathcal{L}_e \end{array} \begin{pmatrix} \mathcal{P}_i & \mathcal{P}_{b_p} & \mathcal{P}_{b_l} & \mathcal{P}_e \\ - & 1 & - & - \\ 1 & - & 0 & 1 \\ 1 & 0 & - & 1 \\ 1 & - & 1 & 1 \end{pmatrix} $$
<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /><figcaption>Fig. 5. Graphical representation of the elements of the matrix $m_1$</figcaption></figure>
In the next section, the GeoPQL system will be presented and the 16-intersection matrices related to both the pictorial representations of the query $q$ of Figure 4 (a) and (b) will be further illustrated.

# 4 The GeoPQL system

GeoPQL is a stand alone tool, in which the developed pictorial functions are integrated with ESRI-ArcView® [2] in order to exploit its basic browsing and drawing functions as well as its underlying geographical database called ArcMap [1]. ArcMap represents geographic information as a collection of layers, where each layer corresponds to a particular dataset overlayed in the map. GeoPQL allows users to formulate their queries using drawing facilities and correctly interprets the query syntax and semantics on the basis of its underlying sound algebra (for details, see [18]).

<figure><img src="image_13.png" /><figcaption>Fig. 6. Answer to the pictorial query shown in Figure 1, as highlighted regions</figcaption></figure>

For instance, in the Introduction, Figure 1 illustrates the pictorial formulation of the query shown in Figure 4 (b) in the GeoPQL working area, on the geographical database of Italy. As we can see in Figure 1 in the “Relation list” on the right side of the working area, GeoPQL correctly identifies the spatial relationship between the SGOS (*Rivers 1 PTH Regions 1*). Then, this query is translated and visualized to the user in a SQL like language [18], as shown on
the top of Figure 6. Note that during the drawing phase which involves modifications, deletions and shifting of the pictorial representation, the textual query is continuously updated. The query is executed on ArcMap and the result is shown in Figure 6, where the highlighted regions are the answer. The 16-intersection matrix $m_2$ given in Section 3, corresponding to this example, is shown on the bottom left of Figure 7. 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, i.e. 0, 1, and 2 which stand for point, line, and polygon, respectively, according to the native representation of the OGC environment. The matrix indicated on the bottom, instead, is our proposed one, and contains in each cell the number of connected components that are in the intersection between the pair of SGOs.

Note that, in order to implement our proposed 16-intersection matrix we invoked in GeoPQL the open source Java libraries JTS Topology Suite [4]. JTS Topology Suite is an API of 2D spatial predicates and functions and provides a complete, consistent, robust implementation of fundamental 2D spatial analysis methods. It conforms to the Simple Features Specification for SQL published by the Open GIS Consortium-OGC® [3].

<figure><img src="image_14.png" /><figcaption>Fig. 7. 16-intersection matrices corresponding to the query shown in Figure 1</figcaption></figure>

Note that in Figure 7, which represents a simple PTH relationship, the matrix on the bottom left does not essentially add information to the matrix given on
<figure><img src="image_15.png" /><figcaption>Fig. 8. 16-intersection matrices corresponding to the query shown in Figure 2</figcaption></figure>

the top left. The 16-intersection matrix corresponding to Figure 2 is shown in Figure 8. In this figure, a different scenario, where the matrices illustrate a composite PTH+TCH between SGOs. In fact, as anticipated in the Introduction, our proposed matrix provides, for instance, the number of points (($\mathcal{L}_{i_p}, \mathcal{P}_{b_p}$) = 3), and the number of polylines (($\mathcal{L}_{i_l}, \mathcal{P}_{b_l}$) = 1) that are in the intersection between the interior of the polyline and the boundary of the polygon. This is not the case of the matrix on the top left of the same figure, which simply provides the values 0, and 1, simply indicating the type of the intersection values respectively. Note that in the OGC environment the *F* (FALSE) notation corresponds to *incomparable* and 0 in our 16-intersection matrix notation.

Finally, in Figure 9, the matrices related to the pictorial representation of the query *q* of Figure 4 (a) are shown, where the matrix on the bottom left of the figure corresponds to the matrix $m_1$ given in Section 3. The level of detail of these matrices differs, for instance, in the case of the element ($\mathcal{L}_{i_p}, \mathcal{P}_{b_p}$). In fact, the number of isolated interior points of the polyline which are also isolated boundary points of the polygon are six, whereas the standard OGC notation only provides the value zero, standing for an intersection of type point. Similarly, in the case of the element ($\mathcal{L}_e, \mathcal{P}_{b_l}$), the number of boundary lines of the polygon that are external to the polyline are six whereas, according to the standard OGC notation, the corresponding cell of the matrix provides the value one, simply standing for an intersection of type polyline. Note that the answers to both the queries shown in Figures 8 and 9 are null.
<figure><img src="image_16.png" /><figcaption>Fig. 9. 16-intersection matrices corresponding to the query shown in Figure 4 (a)</figcaption></figure>

## 5 Related Work

In the last few years, a number of proposals focused on the problems regarding the topological relations between SGOs. Some papers studied the conceptual neighborhood of topological relations between polylines [29] or between regions [15]. Similarly, other proposals discussed qualitative spatial reasoning [30], models [25] [26]. With regard to the operators and algebras for geographical data, in [19] the authors introduced the oriented polylines, and extended the set of operators proposed in [17] [18]. With regard to binary topological relations, the 4-Intersection and 9-Intersection models [12] have been proposed, and a comparison between them has been made [13]. Regarding the 9-intersection model, the definition of binary topological relationships based on the interior ($A^{\circ}$), boundary ($\partial A$), and exterior ($A^{\text{−}}$) of a 2-dimensional point set embedded in $\mathbb{R}^2$ have been introduced [14].

Concerning the topological relationships between geographical features, there is a number of different proposals in the literature, see for instance [5] [26] [8] [9] [10]. For instance, in [5] the authors refer to a calculus-based method, and investigate 17 relationships between polyline-polygon relations. In the mentioned paper some configurations, such as the relationship between a polyline entirely lying on the boundary of the polygon, are not considered. In [26] the authors present an extended model for describing topological relations between sets (objects) in GISs. However, they do not consider polygon-polyline relationships. In
this paper, we consider the aforementioned relationships, and the cases in which
a polyline partially or totally overlaps the boundary of the polygon.

In [8] the authors focus on six kinds of topological relations between a poly-
line and a polygon, and illustrate a hierarchical representation of these relations.
They propose sixteen polyline-polygon topological relations as well as a concep-
tual neighborhood graph. However, the topological operators and their possible
combinations are not discussed.

In [9] [10], starting from the Geographical Pictorial Query Language (GeoPQL)
proposed in [18], a preliminary study has been proposed which regards constraint
relaxation on topological operators in the case of queries which produce null an-
swers. As already clarified in the Introduction, in the aforementioned papers,
given a topological relationship, three 9-intersection matrices have been defined
that necessarily require to compute 27 matrix elements. In this paper, the 16-
intersection matrix allows us to significantly reduce the number of elements to
be evaluated to 10.

6 Conclusion

In this paper, we addressed the polygon-polyline topological relation and we de-
fined a 16-intersection matrix that has been conceived to enhance and distinguish
the semantics of cells' content with respect to the well-known 9-intersection ma-
trix. In order to implement our proposed 16-matrix, we invoked in GeoPQL the
open source Java libraries JTS Topology Suite, which conforms to the Simple
Features Specification for SQL published by the Open GIS Consortium-OGC.
The cases related to the polygon-polygon and polyline-polyline topological rela-
tions will be investigated in future work.

References

1. www.esri.com/software/arcgis/

2. www.esri.com/software/arcview/

3. www.opengeospatial.org/standards

4. www.vividsolutions.com/jts/JTSHome.htm

5. Clementini,E., Di Felice,P., van Oosterom,P. (1993) A small set of formal topo-
logical relationships suitable for end-user interaction. SSD 1993, LNCS N. 692,
Springer-Verlag, pp. 277-295.

6. Cohn, A., Hazarika, S. (2001) Qualitative spatial representation and reasoning: an overview. Fundamenta Informaticae 46(1-2), pp. 1-29.

7. Cui, Z., Cohn, A. G., Randell, D. A. (1993) Qualitative and Topological Relation-
ships in Spatial Databases. In: Abel, D. J. and B. Chin Ooi (Eds). SSD 1993, LNCS
N. 692, Springer-Verlag, pp. 296-315.

8. Deng,M. (2008) A hierarchical representation of line-region topological relations, the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XXXVII, Part B2, pp. 25-30, Beijing.

9. D'Ulizia,A., Ferri,F., Grifoni,P., Rafanelli,M. (2006) Relaxing constraints on GeoPQL operators to improve query answering. DEXA 2006, LNCS N. 4080, Springer-Verlag Publ., pp. 728-737.
10. D'Ulizia,A., Ferri,F., Grifoni,P., Rafanelli,M. (2007) Constraint relaxation on topological operators which produce a null value as answer to a query. IRMA 2007, Canada.

11. Dutta S. (1988) Approximate spatial reasoning, IEA/AIE 1988, Volume 1.

12. Egenhofer,M.J., Franzosa,R.D. (1991) Point-set topological spatial relations. International Journal of Geographical Information Systems, Vol.5, N.2, pp. 161-174.

13. Egenhofer, M.J.,Sharma, J., Mark,D.M. (1993) A critical comparison of the 4-intersection and 9-intersection models for spatial relations: formal analysis. Autocarto 11, Eds R.McMaster & M.Armstrong.

14. Egenhofer,M.J., Mark,D.M. (1995) Modeling conceptual neighborhoods of topological line-region relations. International Journal of Geographical Information Systems, Vol.9, N.5, pp. 555-565.

15. Egenhofer,M.J., (2010) The family of conceptual neighborhood graphs for region-region relations. GIScience 2010, LNCS N.6292, Springer-Verlag Publ., pp. 42-55.

16. Escrig, M.T., Toledo F. (1998) Qualitative Spatial Reasoning: Theory and Practice. Frontiers in Artificial Intelligence and Applications, IOS Press.

17. Ferri,F., Pourabbas, E., Rafanelli,M. (2002) The Syntactic and semantic correctness of pictorial configurations to query geographic databases by PQL. ACM SAC 2002, Spain.

18. Ferri,F., Rafanelli,M. (2005) GeoPQL: a Geographical Pictorial Query Language that resolves ambiguities in query interpretation. Journal of Data Semantics, Springer-Verlag Publ., LNCS N. 3534, pp. 50-80.

19. Ferri,F., Grifoni,P., Rafanelli,M. (2005) A pictorial human computer interaction to query geographical data. PCI 2005, LNCS N.3746, Springer-Verlag, pp. 317-327.

20. Frank,A. U. (1993) The Use of Geographical Information Systems: the User Interface Is the System. In: Medyckyj-Scott, D. and H. M. Hearnshaw (Eds.), Human Factors in Geographical Information Systems, Belhaven Press, pp. 15-31.

21. Frank,A.U. (1996) Qualitative Spatial Reasoning: Cardinal Directions as an Example. Geographic Information Systems, Vol. 10, No. 3, pp. 269-290.

22. Gould, M. D. (1989) Human Factors Research and Its Value to GIS User Interface Design. In: GIS/LIS, Orlando 1989, Florida, USA, pp. 541-550.

23. Grudin, J. (1992) Utility and Usability: Research Issues and Development Contexts. Interacting with Computers 4(2), pp. 209-217.

24. Kuhn, W. (1993) Metaphors Create Theories for Users. In: Frank, A. U. and I. Campari (Eds). COSIT 1993, LNCS N. 716, Springer, pp. 366-376.

25. Li,S. (2006) A complete classification of topological relations using 9-intersection method. International Journal of Geographical Information Science, Vol.20. N.6, pp. 589-610.

26. Liu,K.F., Shi,W.Z. (2007) Extended model of topological relations between spatial objects in geographic information systems. International Journal of Applied Earth Observation and Geoinformation, Vol.9, pp. 264-275.

27. Medyckyj-Scott, D., Hearnshaw, H. M.(Eds.) (1993) Human Factors in Geographical Information Systems, Belhaven Press.

28. Papadias D., Sellis T. (1995) A Pictorial Query-by-Example Language. Journal of Visual Languages and Computing, Vol.6, N.1, pp. 53-72.

29. Pereira Reis,R.M., Egenhofer, M.J., Matos,J. (2008) Conceptual neighborhoods of topological relations between lines. SDH 2008, France, 23-25, pp. 557-574.

30. Schultz, C.P.L., Clephane, T.R., Guesgen, H.W., Amor, R. (2006) Utilization of Qualitative Spatial Reasoning in Geographic Information Systems. In Proc. of Int. Symposium on Spatial Data Handling: Progress in Spatial Data Handling, Riedl, A., Kainz, W., Elmes, G.A. (Eds.) Springer-Verlag, pp. 27-42.