Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Planar Map

Introduction

In this chapter we introduce the planar map. A planar map is derived from the topological map with additional geometric considerations and functionalities (e.g., point location). In this section we briefly review the geometric concepts added in the planar map, the combinatorial concepts were reviewed in Chapter , ``Topological Map''.

\paragraphCurve: We will use the term curve to describe the image of a continuous $1-1$ mapping into the plane of any one of the following: the closed unit interval (arc), the open unit interval (unbounded curve), or the unit circle (closed curve). In all cases a curve is non self-intersecting.

\paragraph $x$ -Monotone curve: We say that a curve $c$ is $x$ -monotone if $c$ either intersects any vertical line in at most one point, or $c$ is a vertical segment.

\paragraphPlanar subdivision (planar map): A planar subdivision (or planar map) is an embedding of a planar

topological map $T$ into the plane, such that each arc of $T$ is embedded as a bounded $x$ -monotone curve. The image of a node of $T$ is a vertex, and the image of an arc is an edge. In this embedding no

edge intersects another edge's interior.

A face of the subdivision is a maximal connected region of the plane that does not contain any vertex or edge. We consider a face to be open, and its boundary is formed by vertices and edges of the subdivision.

Planar Map

Class declaration of CGAL_Planar_map_2<Dcel,Traits>.

Class declaration of Vertex.

Class declaration of Halfedge.

Class declaration of Face.

begin of advanced section

Point Location Strategies

The planar map users can define which algorithm to use in the point location queries. This is done with a point location class passed to the map in the constructor. The class passed should be derived from the base class CGAL_Pm_point_location_base which is a pure virtual base class that defines the interface between the algorithm implemented by the users and the planar map. This follows the known strategy pattern [GHJV95]. The indirection overhead due to the virtual functions is negligible since the optimal point location algorithms (e.g., the one implemented in our default strategy) take

Θ(log n)

time.

We have derived two concrete classes for point location strategies which are presented at Section and Section [ref:PL_sec:naive].

Class declaration of CGAL_Pm_point_location_base<Planar_map>.

Default Point Location Strategy

The CGAL_Pm_default_point_location<Planar_map> class implements the incremental randomized algorithm introduced by Mulmuley [Mul90] as presented by Seidel [Sei91], [dBvKOS97]. It uses a trapezoidal map and a search structure to achieve an expected query time of

O(log n)

. Updating of these structures takes expected

O(log n)

time.

There is also a possibility to assure a deterministic worst-case query time of $O(log n)$ , with a preprocessing step. The trade-off is in a longer building time.

#include <CGAL/Pm_default_point_location.h>

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

The CGAL Project. 22 January, 1999.