\documentclass[jidm,a4paper]{jidm} % NOTE: JIDM is published on A4 paper

\usepackage{graphicx,url}  % for using figures and url format
\usepackage[T1]{fontenc}   % avoids warnings such as "LaTeX Font Warning: Font shape 'OMS/cmtt/m/n' undefined"

\usepackage{amssymb}
\usepackage{amsmath}

\usepackage[ruled,vlined,linesnumbered]{algorithm2e}

\usepackage{color}
\usepackage{textcomp}
\usepackage{array}

\usepackage{enumerate}
\newcommand{\tab}[1]{\hspace{.175\textwidth}\rlap{#1}}
\newcommand{\itab}[1]{\hspace{0em}\rlap{#1}}

%tables
\usepackage{multirow}
\usepackage{booktabs}
\usepackage{ctable}
\setlength{\heavyrulewidth}{0.1em}

%
% Macro definitions
%
\newcommand{\fs}[1]{\tilde{#1}}
% boundary (general)
\newcommand{\bo}[1]{\partial #1}
% closure
\newcommand{\cl}[1]{\overline{#1}}
% crisp spatial difference
\newcommand{\cdiffer}{\ominus}
% crisp spatial intersection
\newcommand{\cinter}{\otimes}
% crisp spatial union
\newcommand{\cunion}{\oplus}
% empty set
\newcommand{\eset}{\varnothing}
% exterior
\newcommand{\ext}[1]{#1^-}
% forall quantifier
\newcommand{\fo}{\forall\,}
% interior
\newcommand{\inter}[1]{#1^\circ}
% logical and
\newcommand{\logand}{\wedge}
% logical or
\newcommand{\logor}{\vee}
% Natural numbers IN
\newcommand{\N}{\mathbb{N}}
% Real numbers IR
\newcommand{\R}{\mathbb{R}}
% "so that" symbol '|' ({x | P})
\newcommand{\sothat}{\,|\,}
% set intersection
\newcommand{\intersection}{\cap}
% set union
\newcommand{\union}{\cup}

% environment "myquote"
\newenvironment{myquote}{\list{}{\leftmargin=0.05in\rightmargin=0.0in}\item[]}{\endlist}

% environment "ldef"
\newenvironment{ldef}[1][l@{\defeq}l]
   {\begin{myquote}$\begin{array}[t]{#1}}
   {\end{array}$\end{myquote}}

% The following data (volume, number and page) are given by the editors prior to publishing your article
\jidmVolume{6}
\jidmNumber{1}
\jidmYear{15}
\jidmMonth{June}
\setcounter{page}{1}

% Includes headers with simplified name of the authors and article title
\markboth{A. C. Carniel, R. R. Ciferri, and C. D. A. Ciferri}
{FuzzyGeometry Abstract Data Type}

% Title of the article
\title{Handling Fuzzy Points and Fuzzy Lines using the FuzzyGeometry Abstract Data Type}

% List of authors
%IF THERE ARE TWO or more institutions, please use:
%\author{Name of Author1\inst{1}, Name of Author2\inst{2}, Name of Author3\inst{2}}
\author{Anderson Chaves Carniel\inst{1}, Ricardo Rodrigues Ciferri\inst{2}, Cristina Dutra de Aguiar Ciferri\inst{1}}

%Affiliation and email
\institute{University of S\~{a}o Paulo, Brazil \\ \email{accarniel@gmail.com, cdac@icmc.usp.br}
\and
Federal University of S\~{a}o Carlos, Brazil \\ \email{ricardo@dc.ufscar.br}
}

% Article abstract - it should be from 100 to 300 words
\begin{abstract}
\emph{Crisp spatial objects} are geometric features with exact location on the extent and well-known boundaries. On the other hand, \emph{vague} or \emph{fuzzy spatial objects} are characterized by uncertain or blurred boundaries and interiors. Despite the importance of fuzzy spatial data in spatial applications, few related work indeed implement them and they do not define abstract data types to enable the management of fuzzy spatial objects by using database management systems (DBMS). To fill this gap in the literature, we propose the \emph{abstract data type} FuzzyGeometry to handle fuzzy spatial objects in the PostgreSQL DBMS. Its implementation is open source. It offers management for fuzzy point objects and fuzzy line objects and provides several operations to handle them. As a result, users are able to access the PostgreSQL in order to use fuzzy spatial objects in spatial queries.
\end{abstract}

% ACM Computing Classification System categories
\category{H.2.8}{Database Management}{Spatial databases and GIS}

% Article keywords in alphabetical order
\keywords{abstract data types, spatial databases, fuzzy spatial objects, spatial fuzzyness}

\begin{document}
\begin{sloppy}

% This is for the grants:
\begin{bottomstuff}
The authors have been supported by the Brazilian research agencies FAPESP, CAPES, and CNPq. %The first author has been supported by FAPESP under the grant numbers 2012/12299-8 and 2013/19633-3.
\end{bottomstuff}

\maketitle

\section{Introduction}
\label{sec:int}

Spatial applications are commonly used for spatial analysis in order to aid in the decision making process. They mainly analyze spatial objects that can be represented by \emph{crisp spatial data types}~\cite{Gut94VLDB,SB06TODS}. These crisp spatial data types can have simple structure, such as crisp point, line, and polygon (that is, region), or complex structure, such as crisp multipoint, multiline, and multipolygon. Real-world phenomena represented by them have exact location in the extent, that is, their geographical coordinates clearly define their geographical positions. In addition, they have well-defined boundaries, expressing with exactness their limit. In order to handle crisp spatial objects in spatial Database Management Systems (spatial DBMS) and Geographical Information System (GIS), spatial operations are defined, such as crisp geometric operations (for instance, union and intersection) and crisp numerical operations (for instance, area and distance).

On the other hand, real-world phenomena frequently have inexact location, uncertain boundaries, or blurred interiors~\cite{Siq14GeoInf}. For instance, the representation of soil mapping, fire and risk zones, oceans, lakes, and air polluted areas. In order to represent these phenomena, we use \emph{vague spatial data types}. There are several models to represent vague spatial objects, such as \emph{exact models}~\cite{Cohn95,PaulySch08QASDM,Bejaoui:2009:QMM,PaulySch10IS}, \emph{rough models}~\cite{BEAIJIS04}, \emph{probabilistic models}~\cite{Cheng:2003:Probabilistic,Li07COMP,Zinn07VLDB}, and \emph{fuzzy models}~\cite{Dilo07IJGIS,Sch08IGI,Sch14ASOC,Carn14ACMGIS}. However, the majority of existing implementations of vague spatial objects~\cite{Krai04Thesis,Dilo06FDSIU,PaulySch08QASDM,PaulySch10IS,Carn15GeoInfo1} are based on the exact models and fuzzy models due to the following factors: (i) exact models reuses existing crisp spatial operations from conventional spatial DBMS and GIS to handle vague spatial objects and (ii) fuzzy models are based on the fuzzy set theory and allows us to refine the definition of a vague spatial object by assigning, for each point, a membership degree between 0 and 1 that indicates how much a point belongs to the object.

Exact models have the advantage of the use of well-known and efficient crisp spatial operations that are largely explored in the literature. As a result, implementations based on these models have an expressive set of vague spatial operations, such as discussed in~\citeN{Carn15GeoInfo1}. However, these implementations are not able to represent in detail a real-world phenomenon since a crisp spatial object is used to denote the well-known part and another crisp spatial object is used to denote the vague part of a vague spatial object. For instance, an air polluted area is represented by two crisp polygon objects, which one object indicates where the pollution certainly occurs (that is, the well-known part) and the other object indicates where the pollution occurs with some degree (that is, the vague part).

On the other hand, fuzzy models allows us to represent a vague spatial object in more details. This is done by assigning a membership degree between 0 and 1 for each point of the object. Membership degrees specify how much a point belongs to a vague spatial object. For instance, due to different concentrations of air pollution at different locations of an air polluted area, these locations are assigned with different membership degrees that specify to which extent each point belongs to the air polluted area. Therefore, differently from exact models, we are able to represent the pollution concentration for each point of a vague spatial object. Vague spatial data based on the exact models are defined as \emph{fuzzy spatial data types}, such as \emph{fuzzy points}, \emph{fuzzy lines}, and \emph{fuzzy regions}.

Despite the advantage to use fuzzy models, only few implementations are based on them~\cite{Krai04Thesis,Dilo06FDSIU}. In addition, they face several limitations, such as: (i) there are no textual or binary representations specifically designed to handle fuzzy spatial objects, (ii) only a small set of operations are defined and implemented, and (iii) its implementation is based on a GIS and not in a spatial DBMS, which can limit the management of fuzzy spatial objects in spatial applications.

To fill this gap, we propose an \emph{abstract data type} (ADT) named FuzzyGeometry. The FuzzyGeometry ADT is based on the fuzzy model and it is an open-source PostgreSQL extension. In this article, we focus on the design and implementation of fuzzy points and fuzzy lines only, which already have several challenges for their definitions and implementations. To handle them, we define \emph{input and output functions}, \emph{fuzzy geometric set operations}, and \emph{fuzzy spatial operations based on the fuzzy set theory}. We also extend our previous work in~\citeN{Carn15GeoInfo2} with the following contents: (i) we detail the specification of the implementation and serialization of fuzzy lines and fuzzy points, (ii) we define textual and binary representations to manage fuzzy lines and fuzzy points, (iii) we exemplify several fuzzy spatial operations by using graphical representations and textual representations, and (iv) we introduce a running example to demonstrate the functionalities of the FuzzyGeometry by using SQL queries.

This article is organized as follows. Section~\ref{sec:rw} summarizes related work. Section~\ref{sec:tb} describes the technical background. Section~\ref{sec:fg} presents our FuzzyGeomety ADT. Section~\ref{sec:re} introduces the running example in order to show how to use the FuzzyGeometry in SQL queries. Finally, Section~\ref{sec:con} concludes the article and presents future work.

\section{Related Work}
\label{sec:rw}

Few works in the literature implement vague spatial data types based on the fuzzy model by using a spatial DBMS or GIS. On the other hand, exact models are also frequently adopted to represent vague spatial objects since they use well-known crisp spatial algorithms. Hence, we compare implementations based on the exact model and the fuzzy model.

Despite there are several exact models~\cite{Cohn95,PaulySch08QASDM,Bejaoui:2009:QMM,PaulySch10IS}, only few implementations are based on them. Vague Spatial Algebra (VASA)~\cite{PaulySch10IS} is an exact model that offers several spatial operations for vague points, vague lines, and vague regions. Implementations based on this model are detailed in in~\citeN{PaulySch08QASDM}, \citeN{PaulySch10IS}\footnote{http://www.cise.ufl.edu/research/SpaceTimeUncertainty/} and \citeN{Carn15GeoInfo1}. However, in this article, we propose an abstract data type for vague spatial data based on the fuzzy model. While VASA has only three levels of representation for vague spatial objects (the well-known part, the vague part, and the part that certainly does not belong to the spatial object), vague spatial objects based on the fuzzy model may have several levels in the interval $[0, 1]$. Therefore, it allows a more detailed representation of spatial vagueness.

For vague spatial data based on the fuzzy model, the Spatial Plateau Algebra (SPA)~\cite{Sch14ASOC} provides definitions for fuzzy spatial data that reuses crisp spatial algorithms. Hence, a fuzzy spatial object, called \emph{spatial plateau object}, is defined as a finite sequence of pairs where each pair is formed by one crisp spatial object and a membership degree in $]0, 1]$. In addition, SPA defines spatial plateau operations to handle spatial plateau objects, such as plateau geometric set operations. Though this implementation concept was proposed, spatial plateau objects were not implemented in a spatial DBMS.
	
Vague spatial data based on the fuzzy model are implemented in~\citeN{Krai04Thesis} and \citeN{Dilo06FDSIU}. The authors in these approaches refer to fuzzy spatial objects as vague spatial objects. Thus, they implement the following vague spatial data types: vague point, vague line, and vague region. A vague point object is defined as a tuple $(x, y, \lambda)$, where $(x, y) \in \R^2$ gives the location, and $\lambda \in ]0, 1]$ gives the membership degree. A vague line object is defined as a finite sequence of tuples $((x_1, y_1, \lambda_1), \ldots, (x_n, y_n, \lambda_n))$ for some $n \in \N$, where each tuple is a vague point object in the vague line constructed by using linear interpolation. A vague region object is composed by several vague lines and the Delaunay triangulation, which is stored together with the vague region object. A membership degree of a point inside a vague region object is calculated by using linear interpolation between membership degrees of vertices of the triangle to which the point belongs. This implementation is performed in the GRASS GIS, and not in a spatial DBMS. Further, they do not implement the vague geometric difference between vague lines. However, our article proposes an abstract data type implemented in a spatial DBMS (that is, the PostgreSQL) to manage fuzzy lines and fuzzy regions as well as several fuzzy spatial operations to handle them.

\section{Technical Background}
\label{sec:tb}

This section summarizes the main needed concepts to understand our proposed FuzzyGeometry ADT. Section~\ref{subsec:vsd} summarizes different models that represent vague spatial data, while Section~\ref{subsec:fst} summarizes concepts from fuzzy set theory.

\subsection{Vague Spatial Data}
\label{subsec:vsd}

While crisp spatial objects have exact location and well-known boundaries, vague spatial objects have inexact location, uncertain boundaries, or blurred interior. There are distinct models to represent vague spatial data, which can be classified as \emph{exact models}~\cite{Cohn95,PaulySch08QASDM,Bejaoui:2009:QMM,PaulySch10IS}, \emph{rough models}~\cite{BEAIJIS04}, \emph{probabilistic models}~\cite{Cheng:2003:Probabilistic,Li07COMP,Zinn07VLDB}, and \emph{fuzzy models}~\cite{Dilo07IJGIS,Sch08IGI,Sch14ASOC,Carn14ACMGIS}.

Exact models aim to reutilize existing abstract data types of crisp spatial data types (for instance, crisp points, crisp lines, and crisp regions) to represent vague spatial objects. In general, vague spatial objects are defined by using two crisp spatial objects. One object represents the vague spatial part and the other object represents the well-known spatial part. The main models are \emph{Egg-Yolk}~\cite{Cohn95}, \emph{Qualitative Min-Max Model} (QMM)~\cite{Bejaoui:2009:QMM}, and \emph{Vague Spatial Algebra} (VASA)~\cite{PaulySch08QASDM,PaulySch10IS}. Egg-Yolk model defines only vague region objects, which are represented by two sub-regions: a sub-region denominates the yolk (that is, vague spatial part) and other sub-region denominates the egg (that is, well-known spatial part) that is contained in the yolk part. QMM model defines vague spatial objects by using two spatial limits, a minimum limit (that is, well-known spatial part) and a maximum limit (that is, includes the minimum limit and extends to the part that possibly belongs to the spatial object). In addition, this model uses qualitative classifications of vagueness levels, such as \emph{completely crisp}, \emph{partially vague}, and \emph{completely vague}. Finally, VASA defines a vague spatial object as a pair of disjoint or adjacent crisp spatial objects of the same type.

Rough models are based on the rough set theory~\cite{pawlak1982rough} that defines a lower and an upper approximation. Hence, a vague spatial object is represented by these approximations. Lower spatial approximation of an object is a subset of its upper spatial approximation. Vague spatial data represented by rough models deal with vague spatial objects with inexact location as well as inexact measures~\cite{BEAIJIS04}.
	
Probabilistic models are based on the probability density functions~\cite{Cheng:2003:Probabilistic,Li07COMP,Zinn07VLDB} and the treatment of spatial vagueness is performed through objects positions and measures. In general, these models deal with expectative of a future event based on the known-characteristics. While the probability density functions are exacts, the location of an object is uncertain.

Fuzzy models, that is, models based on the fuzzy set theory~\cite{Zad65IC}, assign membership degrees in $[0, 1]$ for each point to represent spatial vagueness in different levels. There are several representations of vague spatial data by using the fuzzy set theory. Fuzzy Minimum Boundary Rectangle~\cite{FMBR} includes the fuzzy set theory in order to define membership functions by using several Minimum Boundary Rectangles. Fuzzy spatial data types denominated fuzzy points, fuzzy lines, and fuzzy regions as well as fuzzy geometric set operations, such as, fuzzy geometric union, fuzzy geometric intersection, and fuzzy geometric difference has been defined~\cite{Dilo07IJGIS,Sch08IGI,Sch14ASOC,Carn14ACMGIS}. In addition, vague partitions and their operations are defined~\cite{Dilo07IJGIS}. In this article, we consider the fuzzy spatial data types defined in~\citeN{Dilo07IJGIS} as design goals to implement the FuzzyGeometry ADT. Section~\ref{subsec:fst} summarizes needed fuzzy set theory concepts.

\subsection{Fuzzy Set Theory}
\label{subsec:fst}

Fuzzy set theory~\cite{Zad65IC} is an extension and generalization of the classic (crisp) set theory. In the classic theory, let $X$ be a crisp set of objects, called \emph{universe}. The subset $A$ of $X$ can be described by a function $\chi_A: X \rightarrow \{0, 1\}$, which for all $x \in X$, $\chi_A(x)$ is 1 if and only if, $x \in A$ and 0 otherwise. On the other hand, fuzzy set theory defines a function $\mu_{\fs{A}}$ that maps all elements of $X$ in the real interval $[0, 1]$ by assigning \emph{membership degrees} in a specific set. Further, fuzzy set theory allows that an element $x$ has different membership values in different fuzzy sets. Let $X$ be the universe. Then, the function $\mu_{\fs{A}}: X \rightarrow [0, 1]$ is called of \emph{membership function of the fuzzy set $\fs{A}$}. Therefore, each element of fuzzy set $\fs{A}$ has a membership degree in the real interval $[0, 1]$ according to the membership function: $\fs{A} = \{(x, \mu_{\fs{A}}) \sothat x \in X\}$.

Classic operations among crisp sets also are extended for the fuzzy sets. We will summarize these operations. Let $\fs{A}$ and $\fs{B}$ be fuzzy sets in $X$, then the intersection, union, and difference are defined as follows, respectively.

\begin{itemize}
	\item $\fs{A} \intersection \fs{B} = \{(x, \mu_{\fs{A} \intersection \fs{B}}(x)) \sothat x \in X \logand \mu_{\fs{A} \intersection \fs{B}}(x) = \min(\mu_{\fs{A}}(x), \mu_{\fs{B}}(x))\}$
	\item $\fs{A} \union \fs{B} = \{(x, \mu_{\fs{A} \union \fs{B}}(x)) \sothat x \in X \logand \mu_{\fs{A} \union \fs{B}}(x) = \max(\mu_{\fs{A}}(x), \mu_{\fs{B}}(x))\}$
	\item $\fs{A} - \fs{B} = \{(x, \mu_{\fs{A} - \fs{B}}(x)) \sothat \mu_{\fs{A} - \fs{B}}(x) = \min(\mu_{\fs{A}}(x), 1 - \mu_{\fs{B}}(x)\}$
\end{itemize}

An alpha-cut ($\alpha$-cut) of the fuzzy set $\fs{A}$ for a specific value $\alpha$ is a crisp set defined as follows, $\fs{A}^{\geq \alpha} = \{x \in X \sothat \mu_{\fs{A}}(x) \geq \alpha \logand 0 \leq \alpha \leq 1\}$. When $\alpha$ value is 1, the result is called of core of $\fs{A}$.

Generalizations of fuzzy sets operations, such as intersection and union, replace the minimum and maximum operators by \emph{triangular norms} (t-norm) and \emph{triangular co-norms} (s-norm), respectively. A t-norm $T$ is defined as a commutative, associative, non-decreasing binary operation on $[1, 0]$, with signature $T: [0, 1]^{2} \rightarrow [0, 1]$ satisfying the following boundary conditions, $T(1, x) = x$ and $T(0, x) = 0$ for all $x \in [0, 1]$ \cite{TNBOOK}. Let $x, y \in [0, 1]$, some examples of t-norms are listed as follows.

\begin{itemize}
\item \itab{$T^*(x, y) =
		\begin{cases}
		x & \textrm{if } y = 1\\
		y & \textrm{if } x = 1\\
		0 & \textrm{otherwise}
		\end{cases}$}
	\tab{\tab{\tab{(\emph{drastic intersection})}}}
\item \itab{$T_{p}(x, y) = ab$}
	\tab{\tab{\tab{(\emph{product t-norm})}}}
\item \itab{$T_{l}(x, y) = \max(0, x + y - 1)$}
	\tab{\tab{\tab{(\emph{Lukasiewicz t-norm})}}}	
\end{itemize}

For any t-norm there is an s-norm, which is obtained by De Morgan's laws. Hence, a s-norm is defined as a commutative, associative, non-decreasing binary operation on $[1, 0]$, with signature $S: [0, 1]^{2} \rightarrow [0, 1]$ satisfying the following boundary conditions, $S(1, x) = 1$ and $S(0, x) = x$ for all $x \in [0, 1]$~\cite{TNBOOK}. Let $x, y \in [0, 1]$, some examples of s-norms are listed as follows.

\begin{itemize}
\item \itab{$S^*(x, y) =
		\begin{cases}
		x & \textrm{if } y = 0\\
		y & \textrm{if } x = 0\\
		1 & \textrm{otherwise}
		\end{cases}$}
	\tab{\tab{\tab{(\emph{drastic union})}}}
\item \itab{$S_{p}(x, y) = x+y-xy$}
	\tab{\tab{\tab{(\emph{probabilistic sum})}}}
\item \itab{$S_{l}(x, y) = \min(1, x + y)$}
	\tab{\tab{\tab{(\emph{bounded sum})}}}
\end{itemize}

The height of a fuzzy set $\fs{A}$ is defined as the greatest membership value (sup) of the membership function of $\fs{A}$~\cite{FLCBOOK}, that is, $h(\fs{A}) = sup_{x}[\mu_{\fs{A}}(x)]$. A fuzzy set $\fs{A}$ is called normal when $h(\fs{A}) = 1$, and subnormal when $h(\fs{A}) < 1$. In order to normalize a fuzzy set $\fs{A}$, we apply the normalization operation, which is defined as $\mathit{Norm}_{\mu_{\fs{A}}}(x) = [\mu_{\fs{A}}(x) / h(\fs{A})]$ for all $x \in X$.

The concentration (CON) of a fuzzy set $\fs{A}$ decreases the fuzziness, while the dilation (DIL) of a fuzzy set $\fs{A}$ increases the fuzziness~\cite{FLCBOOK}. They are defined as follows:

\begin{itemize}
	\item $\mu_{\mathit{CON}(\fs{A})}(x) = [\mu_{\fs{A}}(x)]^{p}$ for all $x \in X$ where $p > 1$
	\item $\mu_{\mathit{DIL}(\fs{A})}(x) = [\mu_{\fs{A}}(x)]^{r}$ for all $x \in X$ where $r \in \ ]0, 1[$
\end{itemize}

Finally, there are some notations to textually represent a fuzzy set~\cite{FLCBOOK}. The following definitions are textual representation of a fuzzy set $\fs{A}$.

\begin{itemize}
	\item $\fs{A} = \sum_{x_{i} \in X}\mu_{\fs{A}}(x_{i}) / x_{i}$ when $X$ is finite and discrete
	\item $\fs{A} = \int_{x}\mu_{\fs{A}}(x) / x$ when $X$ is continuous
\end{itemize}

Note that the signs of sum and integral denote the union of the membership degrees and the slash (/) denotes a separator.

%%%%%%%%%%%%%%%%%%%%%%%%

\section{The FuzzyGeometry Abstract Data Type}
\label{sec:fg}

In this section, we propose a novel ADT to handle fuzzy spatial objects, called FuzzyGeometry. We implement the FuzzyGeometry ADT as a PostgreSQL extension. PostgreSQL has free license and it is an extensible DBMS where new ADTs can be implemented by using a low level program language (for instance, C language)\footnote{http://www.postgresql.org/docs/9.5/static/xfunc-c.html}. FuzzyGeometry ADT is implemented in the C language by using the extensibility provided by the PostgreSQL internal library. A detailed documentation of FuzzyGeometry is available at \url{http://gbd.dc.ufscar.br/fuzzygeometry/}.

This section is structured as follows. Section~\ref{subsec:dt} presents the FuzzyGeometry data types and how they are implemented in the PostgreSQL. Section~\ref{subsec:tb} define textual and binary representations of FuzzyGeometry objects. Section~\ref{subsec:op} details fuzzy spatial operations to handle FuzzyGeometry objects in SQL queries.

\subsection{Fuzzy Spatial Data Types of the FuzzyGeometry}
\label{subsec:dt}

Figure~\ref{fig:dt} depicts the fuzzy spatial data types of the FuzzyGeometry ADT. The highest level of hierarchy is the \emph{FuzzyGeometry data type}. The FuzzyGeometry data type is a generalization for fuzzy points and fuzzy lines, which can be simple or complex. The \emph{fuzzy point} data type represents simple fuzzy points, while the \emph{fuzzy multipoint} data type represents complex fuzzy points. Similarly, the \emph{fuzzy linestring} data type represents complex fuzzy lines, while the \emph{fuzzy multilinestring} represents complex fuzzy lines. Note that the current version of the FuzzyGeometry ADT does not provide support for fuzzy regions. Figure~\ref{fig:fd} depicts examples of FuzzyGeometry objects.

\begin{figure}[t]
	\begin{center}		
		\includegraphics[scale=0.37]{figs/datatypes}
		\caption{\label{fig:dt} The hierarchy of the FuzzyGeometry data types.}
	\end{center}
\end{figure}
%
\begin{figure}[t]
	\begin{center}
		\begin{tabular}{c@{\hspace{1cm}}c@{\hspace{1cm}}c@{\hspace{1cm}}c}
			\begin{tabular}{c}
				\includegraphics[scale=0.4]{figs/fpoint}
			\end{tabular}
			& \begin{tabular}{c}
				\includegraphics[scale=0.4]{figs/fmultipoint}
			\end{tabular}
			& \begin{tabular}{c}
				\includegraphics[scale=0.4]{figs/fline}
			\end{tabular}
            & \begin{tabular}{c}
				\includegraphics[scale=0.4]{figs/fmultiline}
			\end{tabular} \\
			(a)
			& (b)
			& (c)
            & (d)
		\end{tabular}
		\caption{\label{fig:fd} Examples of FuzzyGeometry objects: (a) a fuzzy point object, (b) a fuzzy multipoint object, (c) a fuzzy linestring object, and (d) a fuzzy multilinestring object. The membership degrees also are showed, where darker parts have higher membership degrees than lighter areas.}
	\end{center}
\end{figure}

In general, FuzzyGeometry objects have a membership degree for each point in the space to denote inexact location or spatial imprecision. Such membership degree is a value in the real interval $[0, 1]$ that determines the spatial vagueness in a given point. In the following, we will detail each data type of the FuzzyGeometry ADT according to Figure~\ref{fig:dt} by showing its C structure. Hence, these C structures show the attributes that compose fuzzy spatial objects and how they are specified in the low-level implementation of the FuzzyGeometry ADT.

The main C structure of the FuzzyGeometry ADT is the FUZZYGEOM structure. This structure handles the FuzzyGeometry data type, which is a generic data type that can be instanced as fuzzy point objects or fuzzy line objects (Figure~\ref{fig:dt}). Algorithm~\ref{alg:fuzzygeom} shows the FUZZYGEOM structure, which has the following attributes.

\begin{itemize}
	\item The \emph{type} attribute (line 2) is an identifier that indicates the data type of a FuzzyGeometry object (Figure~\ref{fig:dt}), which can be \emph{fuzzy point}, \emph{fuzzy multipoint}, \emph{fuzzy linestring}, and \emph{fuzzy multilinestring}.
	\item The \emph{srid} attribute (line 3) stores the Spatial Reference System Identifier (SRID), which indicates the spatial coordinate system definitions.
    \item The \emph{bbox} attribute (line 4) stores the Minimum Boundary Rectangle (MBR) of a FuzzyGeometry object. Algorithm~\ref{alg:mbr} shows the BBOX structure, which is composed by the minimum and maximum coordinates of each axis, that is, $x$ and $y$.
    \item The \emph{data} attribute (line 5) stores the remaining data related to the FuzzyGeometry object. This is a void pointer to store any kind of data and to aid in the conversion between the FUZZYGEOM structure and similar structures (for instance, the C structure that defines a fuzzy point object).
\end{itemize}

\begin{algorithm}[tb]
\footnotesize
\texttt{typedef struct \{}\\
\quad \texttt{uint8\_t type;}\\
\quad \texttt{int32\_t srid;}\\
\quad \texttt{BBOX *bbox;}\\
\quad \texttt{void *data;}\\
\texttt{\} FUZZYGEOM;}

\caption{\label{alg:fuzzygeom} The C structure to represent the FuzzyGeometry data type (Figure~\ref{fig:fd}).}
\end{algorithm}

\begin{algorithm}[tb]
\footnotesize
\texttt{typedef struct \{}\\
\quad \texttt{double xmin;}\\
\quad \texttt{double xmax;}\\
\quad \texttt{double ymin;}\\
\quad \texttt{double ymax;}\\
\texttt{\} BBOX;}
\caption{\label{alg:mbr} The C structure to represent a MBR of a FuzzyGeometry object.}
\end{algorithm}

In order to aid the handling of FuzzyGeometry objects in main memory, we create a new structure that stores a serialized array of the spatial coordinates $x$ and $y$ and its membership degree, that is, fuzzy points. This structure is named FPOINTARRAY, which is also defined to perform generic operations in serialized arrays, such as insertion, remove, update, and retrieval of elements in such arrays. To efficiently perform these operations, we employ main memory operations in C, such as \emph{memcpy} and \emph{memmove}. We use serialized array of fuzzy points since the PostgreSQL internal library requires that an object should be serialized to be stored in a PostgreSQL table. Further, in order to handle serialized fuzzy points in main memory, we also define the FPOINT structure.

Algorithm~\ref{alg:fpointarray} shows the FPOINTARRAY and FPOINT structures. In the FPOINTARRAY structure (lines 1 to 5), the \emph{serialized\_fpointlist} attribute (line 2) stores the serialized array of fuzzy points, the \emph{npoints} attribute (line 3) stores the current number of stored points, and the \emph{maxpoints} attribute (line 5) stores the maximum number of points that can be stored in the array. The FPOINT structure (lines 7 to 11) contains the coordinates $x$ and $y$ and its membership degree as attributes.

\begin{algorithm}[tb]
\footnotesize
\texttt{typedef struct \{}\\
\quad \texttt{uint8\_t *serialized\_fpointlist;}\\
\quad \texttt{int npoints;}\\
\quad \texttt{int maxpoints;}\\
\texttt{\} FPOINTARRAY;}\\
\ \\
\texttt{typedef struct \{}\\
\quad \texttt{double x;}\\
\quad \texttt{double y;}\\
\quad \texttt{double u;}\\
\texttt{\} FPOINT;}
\caption{\label{alg:fpointarray} The C structures to store serialized array (FPOINTARRAY) of fuzzy points (FPOINT).}
\end{algorithm}

By using the FPOINTARRAY structure, we are able to define the other C structures. Algorithm~\ref{alg:fuzzypoint} shows the FUZZYPOINT and FUZZYMULTIPOINT structures for the fuzzy point and fuzzy multipoint data types (Figure~\ref{fig:dt}), respectively. The difference between the FUZZYPOINT structure and the FPOINT structure (Algorithm~\ref{alg:fpointarray}) is that the FPOINT structure only deals with fuzzy points in main memory to be serialized in the FPOINTARRAY structure, while the FUZZYPOINT structure indeed handle instances of the fuzzy point data type. As a result, we are able to convert an instance of the FUZZYPOINT structure into an instance of the FUZZYGEOM structure. Similarly, we also are able to make conversions from instances of the FUZZYMULTIPOINT structure to instances of the FUZZYGEOM structure. In order to aid these conversions (that is, explicit type conversions in C), the first three attributes of the FUZZYPOINT structure (lines 2 to 4) and the FUZZYMULTIPOINT structure (lines 9 to 11) are the same of the first three attributes of the FUZZYGEOM structure (lines 2 to 4 in Algorithm~\ref{alg:fuzzygeom}). The last attribute of the FUZZYPOINT structure, \emph{point}, is a pointer to an instance of the FPOINTARRAY structure that stores the value 1 in its \emph{npoints} and \emph{maxpoints} attributes since the FUZZYPOINT structure represents the fuzzy point data type. On the other hand, the \emph{point} attribute of the FUZZYMULTIPOINT structure stores a value $n \in \mathbb{N}$ in the \emph{npoints} attribute and a greater value in the \emph{maxpoints} attribute (for instance, $2n$) since it represents the fuzzy multipoint data type.

\begin{algorithm}[tb]
\footnotesize
\texttt{typedef struct \{}\\
\quad \texttt{uint8\_t type;}\\
\quad \texttt{int32\_t srid;}\\
\quad \texttt{BBOX *bbox;}\\
\quad \texttt{FPOINTARRAY *point;}\\
\texttt{\} FUZZYPOINT;}\\
\ \\
\texttt{typedef struct \{}\\
\quad \texttt{uint8\_t type;}\\
\quad \texttt{int32\_t srid;}\\
\quad \texttt{BBOX *bbox;}\\
\quad \texttt{FPOINTARRAY *points;}\\
\texttt{\} FUZZYMULTIPOINT;}\\
\caption{\label{alg:fuzzypoint} The C structures to represent the fuzzy point data type (FUZZYPOINT) and fuzzy multipoint data type (FUZZYMULTIPOINT).}
\end{algorithm}

Algorithm~\ref{alg:fuzzyline} shows the FUZZYLINE and FUZZYMULTILINE structures for the fuzzy linestring and fuzzy multilinestring data types (Figure~\ref{fig:dt}). As for the FUZZYPOINT and FUZZYMULTIPOINT structures, the first three attributes of each structure (lines 2 to 4 in FUZZYLINE structure and lines 10 to 12 in FUZZYMULTILINE structure) are the same of the FUZZYGEOM structure (Algorithm~\ref{alg:fuzzygeom}). The \emph{point} attribute of the FUZZYLINE structure stores the fuzzy points that compose a fuzzy linestring object. Further, this attribute should has at least two fuzzy points and there is no intersection in its line segments. A line segment of a fuzzy linestring object is a consecutive pair of serialized fuzzy points (that is, instances of the FPOINT structure). The \emph{interpolation} attribute indicates the type of interpolation used in the calculation of membership degree of a point in a line segment. The implemented interpolation is the linear; but, other type of interpolations can be also implemented. The FUZZYMULTILINE structure has the following attributes: \emph{ngeoms}, \emph{maxgeoms}, and \emph{geoms}. The \emph{ngeoms} attribute stores the number of fuzzy linestring that is stored in the \emph{geoms} attribute, while \emph{maxgeoms} attribute stores the maximum fuzzy linestring objects that can be stored. This means that the FUZZYMULTILINE structure is formed by a set of pointers of instances of the FUZZYLINE structure stored in the \emph{geoms} attribute.

\begin{algorithm}[tb]
\footnotesize
\texttt{typedef struct \{}\\
\quad \texttt{uint8\_t type;}\\
\quad \texttt{int32\_t srid;}\\
\quad \texttt{BBOX *bbox;}\\
\quad \texttt{FPOINTARRAY *point;}\\
\quad \texttt{uint8\_t interpolation}\\
\texttt{\} FUZZYLINE;}\\
\ \\
\texttt{typedef struct \{}\\
\quad \texttt{uint8\_t type;}\\
\quad \texttt{int32\_t srid;}\\
\quad \texttt{BBOX *bbox;}\\
\quad \texttt{int ngeoms}\\
\quad \texttt{int maxgeoms}\\
\quad \texttt{FUZZYLINE **geoms;}\\
\texttt{\} FUZZYMULTILINE;}\\
\caption{\label{alg:fuzzyline} The C structures to represent the fuzzy line data type (FUZZYLINE) and fuzzy multiline data type (FUZZYMULTILINE).}
\end{algorithm}

Despite we have defined all the C structures to handle the FuzzyGeometry data types, we are not able to use them to store FuzzyGeometry objects in the PostgreSQL. The reason is that the PostgreSQL internal library\footnote{http://www.postgresql.org/docs/9.5/static/xtypes.html} only handles streams of bytes with an alignment, that is, serialized data. Therefore, the aforementioned structures (Algorithms~\ref{alg:fuzzygeom} to~\ref{alg:fuzzyline}) are used only in main memory in order to aid in the handling of fuzzy spatial operations since a pure implementation based on stream of bytes would be complex. Hence, we employ conversions between the internal (main memory) structures and the serialization structure, named FGSERIALIZED. These conversions are efficiently performed since the FPOINTARRAY structure deals with serialized fuzzy points.

Algorithm~\ref{alg:fgserialized} shows the FGSERIALIZED structure, which has the following attributes: \emph{size}, \emph{srid}, and \emph{data}. The \emph{size} attribute is required by the PostgreSQL internal library and stores the size in bytes of the object to be stored in the database. The \emph{srid} is a serialized integer value and corresponds to the \emph{srid} attribute of the FUZZYGEOM structure. The \emph{data} attribute stores the remaining data of a FuzzyGeometry object, that is, the MBR, an identifier of the FuzzyGeometry data type, and the spatial coordinates with their respective membership degrees. The alignment of the serialization is 8, which means that the final size of the object have to be a multiple of 8. Table~\ref{tab:serialization} depicts the serialization order of each FuzzyGeometry data type. This table uses the following notation to show the size in bytes of each serialized element. An element between $<$$>$ represents that such element has 4 bytes, while an element between $[\ ]$ has a size multiple of 8 bytes. Note that for the fuzzy linestring data type, we need to add a padding of 4 bytes to keep the 8-bytes alignment.

\begin{algorithm}[tb]
\footnotesize
\texttt{typedef struct \{}\\
\quad \texttt{uint32\_t size;}\\
\quad \texttt{uint8\_t srid[4];}\\
\quad \texttt{uint8\_t data[1];}\\
\texttt{\} FGSERIALIZED;}
\caption{\label{alg:fgserialized} The C structure to store a FuzzyGeometry object in the PostgreSQL.}
\end{algorithm}

\begin{table}[t]
	\begin{center}
		\caption{\label{tab:serialization} Serialization order of a FuzzyGeometry object stored in the PostgreSQL.}
		\begin{tabular}{m{4.5cm} m{9.5cm}}
        \toprule			
			\centering\textbf{FuzzyGeometry Data Type}		&	\centering\textbf{Serialization Order} \tabularnewline
			\midrule
			\centering Fuzzy Point		&	$[$MBR$]$\newline
													$<$data type identifier$>$\newline
													$<$number of the fuzzy points (0 for empty and 1 otherwise)$>$\newline
													[$x$ coordinate]\newline
													[$y$ coordinate]\newline
													[membership degree]\tabularnewline
			\hline
			\centering Fuzzy Multipoint	&	$[$MBR$]$\newline
													$<$data type identifier$>$\newline
													$<$number of the fuzzy points (0 for empty and 1 otherwise)$>$\newline
													[$x$ coordinate]\newline
													[$y$ coordinate]\newline
													[membership degree]\tabularnewline
			\hline
			\centering Fuzzy Linestring		&	$[$MBR$]$\newline
													$<$data type identifier$>$\newline
													$<$type of interpolation$>$\newline
													$<$number of the fuzzy points (0 for empty and 2 otherwise)$>$\newline
													$<$\textit{padding}$>$\newline
													[$x$ coordinate]\newline
													[$y$ coordinate]\newline
													[membership degree]\tabularnewline
			\hline
			\centering Fuzzy Multilinestring	&	$[$MBR$]$\newline
													$<$data type identifier$>$\newline								
													$<$number of the fuzzy linestrings$>$ \newline
													for each fuzzy linestring \textit{i} \newline
													\-\hspace{0.5cm}[serialization of the fuzzy linestring \textit{i}]\tabularnewline
			\bottomrule
		\end{tabular}
	\end{center}
\end{table}

Once all the internal C structures were defined, we have to link them in the PostgreSQL by using the SQL language. Hence, we use the CREATE TYPE command to create the FuzzyGeometry data type in the PostgreSQL, as showed in Algorithm~\ref{alg:createtype}. Note that only the FuzzyGeometry data type is created since it can be instanced as fuzzy points and fuzzy lines. The \emph{internallength} parameter indicates that the size in bytes of FuzzyGeometry objects is variable since the number of coordinates is not fixed. The \emph{input} and \emph{output} parameters are functions in C that transform a textual representation of a FuzzyGeometry object into its internal representation as well as the inverse, respectively. Similarly, the \emph{send} and \emph{receive} parameters transform a binary representation into an internal representation as well as the inverse, respectively. The textual and binary representations of the FuzzyGeometry data types are presented in Section~\ref{subsec:tb}. The \emph{typmod\_in} and \emph{typmod\_out} parameters deal with the FuzzyGeometry data types. The \emph{category} parameter defines that the FuzzyGeometry data type is a geometric data type. The \emph{alignment} parameter determines the size of the alignment of the serialized data, which is specified to be 8 bytes. Finally, the \emph{storage} parameter specifies the strategy of storage that the PostgreSQL will use for the FuzzyGeometry objects. It was specified to be \emph{main} since it preferentially stores objects in the main table with possible compressions. The complete documentation of the CREATE TYPE command can be found in the PostgreSQL documentation\footnote{http://www.postgresql.org/docs/9.5/static/sql-createtype.html}.

\begin{algorithm}[bt]
\footnotesize
\texttt{CREATE TYPE FuzzyGeometry (}\\
\quad \texttt{internallength = variable,}\\
\quad \texttt{input = fg\_in,}\\
\quad \texttt{output = fg\_out}\\
\quad \texttt{send = fg\_send,}\\
\quad \texttt{receive = fg\_recv,}\\
\quad \texttt{typmod\_in = fg\_typmod\_in,}\\
\quad \texttt{typmod\_out = fg\_typmod\_out,}\\
\quad \texttt{category = 'G',}\\
\quad \texttt{alignment = double,}\\
\quad \texttt{storage = main}\\
\texttt{);}
\caption{\label{alg:createtype} The CREATE TYPE command to create the FuzzyGeometry data type in the PostgreSQL.}
\end{algorithm}

\subsection{Textual and Binary Representations}
\label{subsec:tb}

In order to insert and retrieve FuzzyGeometry objects, we define textual and binary representations for each FuzzyGeometry data type. In addition, these representations allow interoperability between spatial applications since a FuzzyGeometry object has an unique representation. The textual definition can be used for general purpose, while the binary representation can be used in applications that communicate by using network protocols or manage binary data.

We define the \emph{Fuzzy Well-Known Text} (FWKT) as textual representation, which is based on the textual representation of fuzzy sets (Section~\ref{subsec:fst}) and the Well-Known Text representation of the Open Geospatial Consortium (OGC)\footnote{http://www.opengeospatial.org/}. In general, the name of the FuzzyGeometry data type firstly appears and then, in parentheses, the membership degree and coordinate pairs of each point. Empty FuzzyGeometry objects, which contain no coordinates and membership degrees, can be specified by using the symbol \textrm{EMPTY} after the data type name. Table~\ref{tab:fwkt} shows examples of FWKT representations for each FuzzyGeometry data type (Figure~\ref{fig:dt}). Let $(x, y)$ be a coordinate pair, $u$ be a membership degree in real interval $]0, 1]$, and $k, j \in \N$. Then, we define the textual representation FWKT for (i) fuzzy point, (ii) fuzzy multipoint, (iii) fuzzy linestring, and (iv) fuzzy multilinestring data types, as follows.

\begin{enumerate}[(i)]
	\item FUZZYPOINT$(u/x\  y)$
	\item FUZZYMULTIPOINT$(u_1/x_1\  y_1 + ... + u_k/x_k\  y_k)$
	\item FUZZYLINESTRING$(u_1/x_1\  y_1 + ... + u_k/x_k\  y_k)$
	\item FUZZYMULTILINESTRING$((u_{1_1}/x_{1_1}\  y_{1_1} + ... + u_{k_1}/x_{k_1}\  y_{k_1})_1, ..., (u_{1_j}/x_{1_j}\  y_{1_j} + ... + u_{k_j}/x_{k_j}\  y_{k_j})_j)$
\end{enumerate}

\begin{table}[b]
	\begin{center}
	\caption{\label{tab:fwkt} Examples of FWKT representations.}
		\begin{tabular}{m{4.3cm}  m{10cm}}
		\toprule
		\centering\textbf{FuzzyGeometry Data Type}		&	\centering\textbf{FWKT Representation of a FuzzyGeometry object} \tabularnewline
       \midrule
	   \centering Fuzzy Point					&		
FUZZYPOINT(0.7/10 30)\tabularnewline \hline
        \centering Fuzzy MultiPoint					&		
FUZZYMULTIPOINT(0.5/10 20 + 0.8/5 3 + 0.1/30 20)\tabularnewline \hline
            \centering Fuzzy LineString					&		
FUZZYLINESTRING(0.5/1 1 + 0.7/2 2 + 1.0/4 4)\tabularnewline \hline
            \centering Fuzzy MultiLineString					&		
FUZZYMULTILINESTRING((0.3/1 1 + 0.5/2 2), (0.7/3 3 + 1.0/4 4))\tabularnewline
   \bottomrule 			
		\end{tabular}
	\end{center}
\end{table}

We define the \emph{Fuzzy Well-Known Binary} (FWKB) as binary representation, which is based on the Well-Known Binary representation of the OGC. To aid in the FWKB definition, we use the $\mathit{id}(\fs{A})$ function, which extracts the binary format of the data type identifier of a FuzzyGeometry object. It extracts the identifier 1 if $\fs{A}$ is a fuzzy point object, the identifier 2 if $\fs{A}$ is a fuzzy linestring object, the identifier 3 if $\fs{A}$ is a fuzzy multipoint object, and the identifier 4 if $\fs{A}$ is a fuzzy multilinestring object. Further, we use the $\mathit{binary}$ function that extract the binary format of a double value. Let $n$ be the number of points in a fuzzy multipoint and fuzzy linestring object, $l$ be the number of lines in a fuzzy multilinestring object, and $p$ be a fuzzy point with the coordinates $x$ and $y$ with a membership degree $u$. Then, we define the binary representation FWKB for (i) fuzzy point, (ii) fuzzy multipoint, (iii) fuzzy linestring, and (iv) fuzzy multilinestring data types, as follows.

\begin{enumerate}[(i)]
	\item $\mathit{endianess} + \mathit{id}(A) + \mathit{binary}(u) + \mathit{binary}(x) + \mathit{binary}(y)$
	
	\item $\mathit{endianess} + \mathit{id}(A) + \mathit{binary}(n) + \sum_{p_i \in A}^{n}(\mathit{binary}(u)_{p_i} + \mathit{binary}(x)_{p_i} + \mathit{binary}(y)_{p_i})$
	
	\item $\mathit{endianess} + \mathit{id}(A) + \mathit{binary}(n) + \sum_{p_i \in A}^{n}(\mathit{binary}(u)_{p_i} + \mathit{binary}(x)_{p_i} + \mathit{binary}(y)_{p_i})$
	
	\item $\mathit{endianess} + \mathit{id}(A) + \mathit{binary}(l) + \sum_{l_i \in A}^{l}\mathit{FWKB} \text{ of } A_{l_i}$
\end{enumerate}

The signs of sum are used to denote the union between binary data and do not perform the arithmetic sum. Further, \emph{endianess} indicates the way in which the bytes are organized in main memory (that is, either \emph{big-endian} or \emph{little-endian}).

\subsection{Fuzzy Spatial Operations of the FuzzyGeometry}
\label{subsec:op}

FuzzyGeometry ADT provides support to \emph{input and output operations}, \emph{fuzzy geometric set operations}, and \emph{fuzzy spatial operations based on the fuzzy set theory}. The following subsections detail these operations by providing examples and their SQL signatures.

\subsubsection{Input and Output Operations}
\label{ioop}

The input operations transform a FuzzyGeometry object represented in the FWKT and FWKB representations into the internal (main memory) format. This kind of operations are mainly employed to insert new FuzzyGeometry objects in a PostgreSQL relational table. The output operations yield the FWKT and FWKB representations of a FuzzyGeometry object, which is mainly employed to retrieve FuzzyGeometry objects in SQL queries. The SQL signatures for input and output operations are defined as follows, respectively.

\begin{enumerate}[(i)]
	\item \emph{FG\_FuzzyGeomFromText}(text $\mathit{FWKT}$, integer $\mathit{SRID}$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_FuzzyGeomFromBinary}(bytea $\mathit{FWKB}$, integer $\mathit{SRID}$) $\rightarrow$ FuzzyGeometry
    \item \emph{FG\_AsText}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ text
	\item \emph{FG\_AsFWKB}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ bytea
\end{enumerate}

Operation (i) is the input operation for the FWKT representation, while operation (ii) is the input operation for the FWKB representation. These operations also receive the SRID as parameter. Operations (iii) and (iv) are the output operations for the FWKT and FWKB representations, respectively.

\subsubsection{Fuzzy Geometric Set Operations}
\label{fgso}

FuzzyGeometry provides support for the following fuzzy geometric set operations: union, intersection, and difference. In general, we used the formal definition provided by fuzzy models that define fuzzy spatial data (Section~\ref{subsec:vsd}) to implement them. We define the following SQL signatures.

\begin{enumerate}[(i)]
	\item \emph{FG\_Union}(FuzzyGeometry $\mathit{fg1}$, FuzzyGeometry $\mathit{fg2}$, text $s$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_Union}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_Intersection}(FuzzyGeometry  $\mathit{fg1}$, FuzzyGeometry  $\mathit{fg2}$, text $t$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_Difference}(FuzzyGeometry  $\mathit{fg1}$, FuzzyGeometry  $\mathit{fg2}$, text $d$) $\rightarrow$ FuzzyGeometry
\end{enumerate}

Operation (i) is the union operation between FuzzyGeometry objects, which is performed by the spatial union and the fuzzy union to calculate the membership degree of intersecting points. The fuzzy union can be executed by using a specific s-norm $s$, which can be the default union (max operator), drastic union, probabilistic sum, and bounded sum (Section~\ref{subsec:fst}). In addition, the union is only executed for FuzzyGeometry objects of same data type. For instance, the union of two fuzzy linestring objects yields other fuzzy linestring object. In addition, the union operation can be used as an aggregation operator, that is, the operation (ii). This means that, given a set of FuzzyGeometry objects, this operation yields the union among all the objects contained in this set. The strategy to compute this aggregation is to perform the union operation (i) incrementally for each FuzzyGeometry object contained in the set by considering the default union to calculate the membership degree of intersecting points. Figure~\ref{fig:examplefgso}c shows the result of the union operation between two fuzzy multipoint objects (Figures~\ref{fig:examplefgso}a and~\ref{fig:examplefgso}b) that applied the probabilistic sum as s-norm.

Operation (iii) is the intersection operation between FuzzyGeometry objects, which is performed by the spatial intersection and the fuzzy intersection to calculate the membership degree of intersecting points. The fuzzy intersection can be executed by using a specific t-norm $t$, which can be the default t-norm (min operator), drastic intersection, product t-norm, and Lukasiewicz t-norm (Section~\ref{subsec:fst}). The intersection can be executed between FuzzyGeometry objects of different types, and the resulting FuzzyGeometry object is the lower data type by considering the hierarchy: \emph{fuzzy linestring $>$ fuzzy point}. For instance, the intersection between fuzzy linestring objects and fuzzy point objects yields a fuzzy point or a fuzzy multipoint object composed by the commons points with membership degrees calculated by using a t-norm $t$. Figure~\ref{fig:examplefgso}d shows the result of the intersection operation between two fuzzy multipoint objects (Figures~\ref{fig:examplefgso}a and~\ref{fig:examplefgso}b) that applied the product t-norm as t-norm.

Operation (iv) is the difference operation between FuzzyGeometry objects, which is performed by the spatial difference and the membership degrees of intersecting points are calculated by using a difference operator. The supported difference operators are the fuzzy difference (Section~\ref{subsec:fst}) and arithmetic difference. The arithmetic difference is defined by $\mathit{diff}(a, b) = a - b$ if $a > b$ and $0$ otherwise. The difference is only performed between FuzzyGeometry objects of same data type. For instance, the difference between fuzzy linestring objects yields a fuzzy linestring object. Figure~\ref{fig:examplefgso}e shows the result of the difference operation between two fuzzy multipoint objects (Figures~\ref{fig:examplefgso}a and~\ref{fig:examplefgso}b) that applied the fuzzy difference to calculate the membership degrees of intersecting points.

\begin{figure}[bt]
	\begin{center}    	\begin{tabular}{m{3cm}@{\hspace{0.2cm}}m{3cm}@{\hspace{0.2cm}}m{3cm}@{\hspace{0.2cm}}m{3cm}@{\hspace{0.2cm}}m{3cm}}
            \begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.3]{figs/fuzzympoint1}
				\end{tabular}
			\end{center}
			&
			\begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.3]{figs/fuzzympoint2}
				\end{tabular}
			\end{center}
			&
            \begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.3]{figs/funion}
				\end{tabular}
			\end{center}
			&
			\begin{center}
				\begin{tabular}{c}
					\vspace{-0.05cm}
					\includegraphics[scale=0.3]{figs/fintersec}
				\end{tabular}
			\end{center}
			&
			\begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.3]{figs/fdiff}
				\end{tabular}
			\end{center} \tabularnewline
            \scriptsize{FUZZYMULTIPOINT( 0.2/-2 1 + 1/-1 2 + 1/1 1 + 0.4/1 2 + 0.6/2 2)}
			& \scriptsize{FUZZYMULTIPOINT( 0.4/-2 1 + 1/-1 1 + 0.8/1 1 + 0.6/2 2 + 1/3 1)}
            & \scriptsize{FUZZYMULTIPOINT( 0.68/-2 1 + 1/-1 2 + 1/-1 1 + 1/1 1 + 0.4/1 2 + 0.84/2 2 + 1/3 1)}
			& \scriptsize{FUZZYMULTIPOINT( 0.08/-2 1 + 0.8/1 1 + 0.36/2 2)}
			& \scriptsize{FUZZYMULTIPOINT( 0.2/-2 1 + 1/-1 1 + 0.2/1 1 + 0.4/1 2 + 0.4/2 2)} \tabularnewline
			\centering (a) & \centering (b) & \centering (c) & \centering (d) & \centering (e)
		\end{tabular}
		\caption{\label{fig:examplefgso} Result of the fuzzy geometric set operations on two FuzzyGeometry objects (a) and (b): (c) union operation, (d) intersection operation, and (e) difference operation. Each FuzzyGeometry object has its respective FWKT representation.}
	\end{center}
\end{figure}

\subsubsection{Fuzzy Spatial Operations Based on the Fuzzy Set Theory}
\label{fspbfst}

FuzzyGeometry provides support for the following fuzzy spatial operations based on the fuzzy set theory: core, boundary, concentration, dilation, alpha-cut, height, and normalization. These operations can be applied in any type of FuzzyGeometry object, and they have the following SQL signatures.

\begin{enumerate}[(i)]
	\item \emph{FG\_Core}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_Boundary}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_Concentration}(FuzzyGeometry $\mathit{fg}$, double $p$) $\rightarrow$ FuzzyGeometry
	\item \emph{FG\_Dilation}(FuzzyGeometry $\mathit{fg}$, double $r$) $\rightarrow$ FuzzyGeometry
    \item \emph{FG\_Alphacut}(FuzzyGeometry $\mathit{fg}$, double $\alpha$) $\rightarrow$ FuzzyGeometry
    \item \emph{FG\_Height}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ double
    \item \emph{FG\_Normalization}(FuzzyGeometry $\mathit{fg}$) $\rightarrow$ FuzzyGeometry
\end{enumerate}

Operations (i) and (ii) correspond to the core and boundary operations, which return the locations that have exact locations (locations with membership degree equal to 1) and vague locations (locations with membership degree less than 1 and greater than 0), respectively. Figures~\ref{fig:dilaconce}a and \ref{fig:dilaconce}b depict the result of the core and boundary operations on the fuzzy multipoint object of Figure~\ref{fig:examplefgso}a.

Operations (iii) and (iv) correspond to the fuzzy concentration (iii) and dilation (iv) operations (Section~\ref{subsec:fst}), which decrease and increase the membership degrees of the locations according to a $p$ and $r$, respectively. These operations are useful to analyze or edit locations in order to intensify or smooth the spatial vagueness. Figures~\ref{fig:dilaconce}c and \ref{fig:dilaconce}d depicts the result of the concentration and dilation operations on the fuzzy multipoint object of Figure~\ref{fig:examplefgso}a.

Operation (v) performs the fuzzy alpha-cut (Section~\ref{subsec:fst}), which filters the locations that have membership degree equal to or greater to an $\alpha$ value. This means that, this operation identifies locations that contain specifics membership degrees. Operation (vi) corresponds to the fuzzy spatial height that returns the higher membership degree of a FuzzyGeometry object. This operation is necessary for the fuzzy spatial normalization operation (operation (vii)). If the height of a FuzzyGeometry object is 1, than it has a core (for instance, the multipoint object in Figure~\ref{fig:examplefgso}a). Otherwise, the normalization can be used to create a core, which will be the locations with the higher membership degree.

\begin{figure}[tb]
	\begin{center}
		\begin{tabular}{m{3.3cm}@{\hspace{0.5cm}}m{3.3cm}@{\hspace{0.5cm}}m{3.3cm}@{\hspace{0.5cm}}m{3.3cm}}
			\begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.35]{figs/core}
				\end{tabular}
			\end{center}
			&
            \begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.35]{figs/boundary}
				\end{tabular}
			\end{center}
            &
			\begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.35]{figs/fuzzyconc}
				\end{tabular}
			\end{center}
			&
			\begin{center}
				\begin{tabular}{c}
					\includegraphics[scale=0.35]{figs/fuzzydila}
				\end{tabular}
			\end{center} \\
            \scriptsize{FUZZYMULTIPOINT( 1/-1 2 + 1/1 1)}			
            & \scriptsize{FUZZYMULTIPOINT( 0.2/-2 1 + 0.4/1 2 + 0.6/2 2)}
			& \scriptsize{FUZZYMULTIPOINT( 0.04/-2 1 + 1/-1 2 + 1/1 1 + 0.16/1 2 + 0.36/2 2)}
			& \scriptsize{FUZZYMULTIPOINT( 0.447/-2 1 + 1/-1 2 + 1/1 1 + 0.632/1 2 + 0.774/2 2)} \tabularnewline
			\centering (a) & \centering (b) & \centering (c) & \centering (d)
		\end{tabular}
		\caption{\label{fig:dilaconce} Result of the core (a), boundary (b), concentration (c), and dilation (d) operations on the FuzzyGeometry object of Figure~\ref{fig:examplefgso}a, with their respective FWKT representations.}
	\end{center}
\end{figure}

\section{Running Example}
\label{sec:re}

This section provides a running example to illustrate the functionalities of FuzzyGeometry ADT by using the SQL language. The context of this running example is to manage plagues and animal routes in an ecological application. Hence, we consider the following relational table schemas \emph{plague} and \emph{animal}. Each table has an attribute \emph{id} as primary key and an attribute \emph{geo} to store FuzzyGeometry objects. While plagues are represented by fuzzy multipoint objects, animal routes are represented by fuzzy multilinestring objects. The following SQL command exemplifies the creation of the table \emph{plague}. Note that the FuzzyGeometry data type is specified between parentheses in the attribute \emph{geo}.

\begin{quote}
\begin{verbatim}
CREATE TABLE plague(
  id INTEGER PRIMARY KEY,
  geo FUZZYGEOMETRY(FUZZYMULTIPOINT));
\end{verbatim}
\end{quote}

Similarly, we are able to create the animal table. By using textual and binary representations (Section~\ref{sec:tb}), we are able to insert FuzzyGeometry objects in tables. The next SQL command shows the insertion of the fuzzymultipoint object of Figure~\ref{fig:examplefgso}a in the plague table.

\begin{quote}
\begin{verbatim}
INSERT INTO plague VALUES (1,
  FG_FuzzyGeomFromText('FUZZYMULTIPOINT(0.2/-2 1 + 1/-1 2 + 1/1 1 + 0.4/1 2 +
                       0.6/2 2)', 4326))
\end{verbatim}
\end{quote}

Once we have inserted FuzzyGeometry objects in the tables, we are able to perform SQL queries on them. The following query returns the intersecting parts among all animal routes. This query shows the result of the intersection operation between distinct FuzzyGeometry objects of the animal table by using the FWKT representation.

\begin{quote}
\begin{verbatim}
SELECT FG_AsText(FG_Intersection(A.geo, B.geo, 'default t-norm'))
FROM animal as A, animal as B
WHERE A.id <> B.id
\end{verbatim}
\end{quote}

The next SQL query returns the intersecting points between the animal route with \emph{id} equal to 5 and all the plagues of the environment. Hence, we employ the union operation as an aggregation function on the plagues, and then, we compute the intersection between this object and the animal route.

\begin{quote}
\begin{verbatim}
SELECT FG_AsText(FG_Intersection(P.all, A.geo))
FROM (SELECT FG_Union(geo) as all FROM plague) as P, animal as A
WHERE A.id = 5
\end{verbatim}
\end{quote}

The next SQL query returns the plagues with membership degrees greater than 0.8. This means that these plagues need some treatment of the decision makers since they possibly exist due to their high level of membership degrees.

\begin{quote}
\begin{verbatim}
SELECT FG_AsText(FG_Alphacut(P.geo, 0.8))
FROM plague as P
\end{verbatim}
\end{quote}

The next query changes the meaning of spatial vagueness in an animal route (\emph{id} equal to 10) by decreasing its membership degrees. This means that, due to some factors (for instance, a strong rain), the imprecision of this animal route is higher than the original.

\begin{quote}
\begin{verbatim}
SELECT FG_AsText(FG_Concentration(A.geo, 2))
FROM animal as A
WHERE id = 10
\end{verbatim}
\end{quote}

On the other hand, the final SQL query employs the dilation to increase the membership degrees of another animal route (\emph{id} equal to 11). As a result, this query returns an animal route with lesser imprecision than the original.

\begin{quote}
\begin{verbatim}
SELECT FG_AsText(FG_Dilation(A.geo, 0.5))
FROM animal as A
WHERE id = 11
\end{verbatim}
\end{quote}

\section{Conclusions and Future Work}
\label{sec:con}

This article proposes a novel abstract data type, called FuzzyGeometry, to handle vague (fuzzy) spatial objects based on the fuzzy model in the PostgreSQL. More specifically, it handles simple and complex fuzzy points and fuzzy lines. Fuzzy spatial data are an important representation of real-world phenomena that have vague characteristics, that is, inexact location or uncertain boundaries and interiors. Although it can be adequately used to represent spatial vagueness, implementations based on the fuzzy model are limited and have not been incorporated into spatial DBMS. Hence, FuzzyGeometry ADT advances in the state of art to handle vague spatial objects in a spatial DBMS. 	

Several operations have been proposed and implemented to handle FuzzyGeometry objects, such as input and output operations, fuzzy geometric set operations, and fuzzy spatial operations based on the fuzzy set theory. To deal with input and output operations, we propose textual and binary representations in order to insert and retrieve FuzzyGeometry objects in a spatial database. Future work will deal with the implementation of the fuzzy region data type.% We will also propose algorithms in order to extract information by using fuzzy inference~\cite{FLCBOOK} on fuzzy spatial objects.

\bibliographystyle{jidm}
\bibliography{FuzzyGeometry}
\end{sloppy}

\begin{received}
\end{received}

\end{document}
