\chapter{Basic Data Types for Computational Geometry} 
\label{Basic Data Types for Computational Geometry}

LEDA provides a collection of simple data types for computational geometry, 
such as points,
vectors, directions, hyperplanes, segments, rays, lines, affine
transformations, circles, polygons, and operations connecting these types.

The computational geometry kernel has evolved over time. The first kernel
(types \mbox{$\mathit{point}$}, \mbox{$\mathit{line}$}, \ldots) was restricted 
to two-dimensional geometry and used floating point arithmetic as the 
underlying arithmetic. We found it very difficult to implement reliable 
geometric algorithms based on this kernel. See the chapter on computational
geometry of \cite{LEDAbook} for some examples of the danger of floating
point arithmetic in geometric computations. Starting with version 3.2
we therefore also provided a kernel based on exact rational arithmetic (types
\mbox{$\mathit{rat\nspaceunderscore\_point}$}, \mbox{$\mathit{rat\nspaceunderscore\_segment}$}, \ldots). 
This kernel is still restricted to two dimensions. 
The further development of computational geometry will occur in close 
cooperation with the CGAL effort \cite{fgkss:cgalarticle,over:cgalarticle}.


All two-dimensional object types defined in this section support
the following operations:


{\bf Equality and Identity Tests}\\

\setlength{\typewidth}{2cm}
\setlength{\callwidth}{6.5cm}
\computewidths

\function {\mbox{$\mathit{bool}$}}
{identical} 
{\mbox{$\mathit{object}\ \mathit{p},$}
\mbox{$\mathit{object}\ \mathit{q}$}} 
{Test for identity. }

\operator {\mbox{$\mathit{int}$}}
{\mbox{$\mathit{p}\Leq \mathit{q}$}}  
{Test for equality. }

\operator {\mbox{$\mathit{int}$}}
{\mbox{$\mathit{p}\Lass{!}\mathit{q}$}}  
{Test for inequality. }



{\bf I/O Operators}\\

\operator {\mbox{$\mathit{ostream}\&$}}
{\mbox{$\mathit{ostream}\&\ \mathit{O}\ \ll\ \mathit{object}\ \mathit{x}$}}
{writes the object \mbox{$\mathit{x}$} to output stream $O$.}

\operator {\mbox{$\mathit{istream}\&$}}
{\mbox{$\mathit{istream}\&\ \mathit{I}\ \gg\ \mathit{object}\&\ \mathit{x}$}}  
{reads an object from input stream $I$ into variable \mbox{$\mathit{x}$}.}




\newpage
\input extract/point.tex
\newpage
\input extract/segment.tex
\newpage
\input extract/ray.tex
\newpage
\input extract/line.tex
\newpage
\input extract/polygon.tex
\newpage
\input extract/circle.tex
\newpage
\input extract/rat_point
\newpage
\input extract/rat_segment
\newpage
\input extract/rat_ray.tex
\newpage
\input extract/rat_line
\newpage
\input extract/rat_polygon
\newpage
\input extract/rat_circle
\newpage
\input extract/plane_alg.tex
\newpage
