Chapter 20
2D Arrangements

Ron Wein, Efi Fogel, Baruch Zukerman, and Dan Halperin

Table of Contents

20.1   Introduction

Given a set $$ of planar curves, the arrangement $$() is the subdivision of the plane into zero-dimensional, one-dimensional and two-dimensional cells, called vertices, edges and faces, respectively induced by the curves in $$. Arrangements are ubiquitous in the computational-geometry literature and have many applications; see, e.g., [AS00, Hal04].

The curves in $$ can intersect each other (a single curve may also be self-intersecting or may be comprised of several disconnected branches) and are not necessarily $$x-monotone.¹ We construct a collection $$'' of $$x-monotone subcurves that are pairwise disjoint in their interiors in two steps as follows. First, we decompose each curve in $$ into maximal $$x-monotone subcurves (and possibly isolated points), obtaining the collection $$'. Note that an $$x-monotone curve cannot be self-intersecting. Then, we decompose each curve in $$' into maximal connected subcurves not intersecting any other curve (or point) in $$'. The collection $$'' may also contain isolated points, if the curves of $$ contain such points. The arrangement induced by the collection $$'' can be conveniently embedded as a planar graph, whose vertices are associated with curve endpoints or with isolated points, and whose edges are associated with subcurves. It is easy to see that $$() = (''). This graph can be represented using a doubly-connected edge list data-structure (DCEL for short), which consists of containers of vertices, edges and faces and maintains the incidence relations among these objects.

The main idea behind the DCEL data-structure is to represent each edge using a pair of directed halfedges, one going from the $$xy-lexicographically smaller (left) endpoint of the curve toward its the $$xy-lexicographically larger (right) endpoint, and the other, known as its twin halfedge, going in the opposite direction. As each halfedge is directed, we say it has a source vertex and a target vertex. Halfedges are used to separate faces, and to connect vertices (with the exception of isolated vertices, which are unconnected).

If a vertex $$v is the target of a halfedge $$e, we say that $$v and $$e are incident to each other. The halfedges incident to a vertex $$v form a circular list oriented in a clockwise order around this vertex. (An isolated vertex has no incident halfedges.)

Each halfedge $$e stores a pointer to its incident face, which is the face lying to its left. Moreover, every halfedge is followed by another halfedge sharing the same incident face, such that the target vertex of the halfedge is the same as the source vertex of the next halfedge. The halfedges are therefore connected in circular lists, and form chains, such that all edges of a chain are incident to the same face and wind along its boundary. We call such a chain a connected component of the boundary (or CCB for short).

The unique CCB of halfedges winding in a counterclockwise orientation along a face boundary is referred to as the outer CCB of the face. For the time being let us consider only arrangements of bounded curves, such that exactly one unbounded face exists in every arrangement. The unbounded face does not have an outer boundary. Any other connected component of the boundary of the face is called a hole (or inner CCB), and can be represented as a circular chain of halfedges winding in a clockwise orientation around it. Note that a hole does not necessarily correspond to a single face, as it may have no area, or alternatively it may consist of several connected faces. Every face can have several holes contained in its interior (or no holes at all). In addition, every face may contain isolated vertices in its interior. See Figure 20.1 for an illustration of the various DCEL features. For more details on the DCEL data structure see [dBvKOS00, Chapter 2].

The rest of this chapter is organized as follows: In Section 20.2 we review in detail the interface of the Arrangement_2 class-template, which is the central component in the arrangement package. In Section 20.3 we show how queries on an arrangement can be issued. In Section 20.4 we review some important free (global) functions that operate on arrangements, the most important ones being the free insertion-functions. Section 20.6 contains detailed descriptions of the various geometric traits classes included in the arrangement package. Using these traits classes it is possible to construct arrangements of different families of curves. In Section 20.7 we review the notification mechanism that allows external classes to keep track of the changes that an arrangement instance goes through. Section 20.8 explains how to extend the DCEL records, to store extra data with them, and to efficiently update this data. In Section 20.9 we introduce the fundamental operation of overlaying two arrangements. Section 20.10 describes the Arrangement_with_history_2 class-template that extends the arrangement by storing additional history records with its curves. Finally, in Section 20.11 we review the arrangement input/output functions.

20.2   The Main Arrangement Class

The class Arrangement_2<Traits,Dcel> is the main class in the arrangement package. It is used to represent planar arrangements and provides the interface needed to construct them, traverse them, and maintain them. An arrangement is defined by a geometric traits class that determines the family of planar curves that form the arrangement, and a DCEL class, which represents the topological structure of the planar subdivision. It supplies a minimal set of geometric operations (predicates and constructions) required to construct and maintain the arrangement and to operate on it.

The design of the arrangement package is guided by the need to separate between the representation of the arrangements and the various geometric algorithms that operate on them, and by the need to separate between the topological and geometric aspects of the planar subdivision. The separation is exhibited by the two template parameters of the Arrangement_2 template:

• The Traits template-parameter should be instantiated with a model of the ArrangementBasicTraits_2 concept. The traits class defines the types of $$x-monotone curves and two-dimensional points, X_monotone_curve_2 and Point_2 respectively, and supports basic geometric predicates on them.

  In the first sections of this chapter we always use Arr_segment_traits_2 as our traits class, to construct arrangements of line segments. However, the arrangement package contains several other traits classes that can handle also polylines (continuous piecewise-linear curves), conic arcs, and arcs of rational functions. We exemplify the usage of these traits classes in Section 20.6.

• The Dcel template-parameter should be instantiated with a class that is a model of the ArrangementDcel concept. The value of this parameter is Arr_default_dcel<Traits> by default. However, in many applications it is necessary to extend the DCEL features; see Section 20.8 for further explanations and examples.

20.2.1   A Simple Program

#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Quotient.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

typedef CGAL::Quotient<CGAL::MP_Float>     Number_type;
typedef CGAL::Cartesian<Number_type>       Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef Traits_2::Point_2                  Point_2;
typedef Traits_2::X_monotone_curve_2       Segment_2;
typedef CGAL::Arrangement_2<Traits_2>      Arrangement_2;

int main()
{
  Arrangement_2   arr;
  Segment_2       cv[3];
  Point_2         p1 (0, 0), p2 (0, 4), p3 (4, 0);
 
  cv[0] = Segment_2 (p1, p2);
  cv[1] = Segment_2 (p2, p3);
  cv[2] = Segment_2 (p3, p1);
  CGAL::insert_curves (arr, &cv[0], &cv[3]);

  return (0);
}

20.2.2   Traversing the Arrangement

The simplest and most fundamental arrangement operations are the various traversal methods, which allow users to systematically go over the relevant features of the arrangement at hand.

As mentioned above, the arrangement is represented as a DCEL, which stores three containers of vertices, halfedges and faces. Thus, the Arrangement_2 class supplies iterators for these containers. For example, the methods vertices_begin() and vertices_end() return Arrangement_2::Vertex_iterator objects that define the valid range of arrangement vertices. The value type of this iterator is Arrangement_2::Vertex. Moreover, the vertex-iterator type is equivalent to Arrangement_2::Vertex_handle, which serves as a pointer to a vertex. As we show next, all functions related to arrangement features accept handle types as input parameters and return handle types as their output.

In addition to the iterators for arrangement vertices, halfedges and faces, the arrangement class also provides edges_begin() and edges_end() that return Arrangement_2::Edge_iterator objects for traversing the arrangement edges. Note that the value type of this iterator is Arrangement_2::Halfedge, representing one of the twin halfedges that represent the edge.

All iterator, circulator² and handle types also have non-mutable (const) counterparts. These non-mutable iterators are useful to traverse an arrangement without changing it. For example, the arrangement has a non-constant member function called vertices_begin() that returns a Vertex_iterator object and another const member function that returns a Vertex_const_iterator object. In fact, all methods listed in this section that return an iterator, a circulator or a handle have non-mutable counterparts. It should be noted that, for example, Vertex_handle can be readily converted into a Vertex_const_handle, but not vice-verse.

Conversion of a non-mutable handle to a corresponding mutable handle are nevertheless possible, and can be performed using the static function Arrangement_2::non_const_handle() (see, e.g., Section 20.3.1). There are three variant of this function, one for each type of handle.

Traversal Methods for an Arrangement Vertex

A vertex is always associated with a geometric entity, namely with a Point_2 object, which can be obtained by the point() method of the Vertex class nested within Arrangement_2.

The is_isolated() method determines whether a vertex is isolated or not. Recall that the halfedges incident to a non-isolated vertex, namely the halfedges that share a common target vertex, form a circular list around this vertex. The incident_halfedges() method returns a circulator of type Arrangement_2::Halfedge_around_vertex_circulator that enables the traversal of this circular list in a clockwise direction. The value type of this circulator is Halfedge.

The following function prints all the neighbors of a given arrangement vertex (assuming that the Point_2 type can be inserted into the standard output using the << operator). The arrangement type is the same as in the simple example above.

void print_neighboring_vertices (Arrangement_2::Vertex_const_handle v)
{
  if (v->is_isolated()) {
    std::cout << "The vertex (" << v->point() << ") is isolated" << std::endl;
    return;
  }

  Arrangement_2::Halfedge_around_vertex_const_circulator first, curr;
  first = curr = v->incident_halfedges();

  std::cout << "The neighbors of the vertex (" << v->point() << ") are:";
  do {
    // Note that the current halfedge is directed from u to v:
    Arrangement_2::Vertex_const_handle u = curr->source();
    std::cout << " (" << u->point() << ")";
  } while (++curr != first);
  std::cout << std::endl;
}

In case of an isolated vertex, it is possible to obtain the face that contains this vertex using the face() method.

Traversal Methods for an Arrangement Halfedge

Each arrangement edge, realized as a pair of twin halfedges, is associated with an X_monotone_curve_2 object, which can be obtained by the curve() method of the Halfedge class nested in the Arrangement_2 class.

The source() and target() methods return handles to the halfedge source and target vertices respectively. We can obtain a handle to the twin halfedge using the twin() method. From the definition of halfedges, it follows that if he is a halfedge handle, then:

• he->curve() is equivalent to he->twin()->curve(),
• he->source() is equivalent to he->twin()->target(), and
• he->target() is equivalent to he->twin()->source().

Every halfedge has an incident face that lies to its left, which can be obtained by the face() method. Recall that a halfedge is always one link in a connected chain of halfedges that share the same incident face, known as a CCB. The prev() and next() methods return handles to the previous and next halfedges in the CCB respectively.

As the CCB is a circular list of halfedges, it is only natural to traverse it using a circulator. The ccb() method returns a Arrangement_2::Ccb_halfedge_circulator object for the halfedges along the CCB.

The function print_ccb() listed below prints all $$x-monotone curves along a given CCB (assuming that the Point_2 and the X_monotone_curve_2 types can be inserted into the standard output using the << operator).

void print_ccb (Arrangement_2::Ccb_halfedge_const_circulator circ)
{
  Ccb_halfedge_const_circulator curr = circ;
  std::cout << "(" << curr->source()->point() << ")";
  do {
    Arrangement_2::Halfedge_const_handle he = curr->handle();
    std::cout << "   [" << he->curve() << "]   "
              << "(" << he->target()->point() << ")";
  } while (++curr != circ);
  std::cout << std::endl;
}

Traversal Methods for an Arrangement Face

An arrangement of bounded curves always has a single unbounded face. The function unbounded_face() returns a handle to this face. (Note that an empty arrangement contains nothing but the unbounded face.)

Given a Face object, we can use the is_unbounded() method to determine whether it is unbounded. Bounded faces have an outer CCB, and the outer_ccb() method returns a circulator for the halfedges along this CCB. Note that the halfedges along this CCB wind in a counterclockwise orientation around the outer boundary of the face.

A face can also contain disconnected components in its interior, namely holes and isolated vertices:

• The holes_begin() and holes_end() methods return Arrangement_2::Hole_iterator iterators that define the range of holes inside the face. The value type of this iterator is Ccb_halfedge_circulator, defining the CCB that winds in a clockwise orientation around a hole.
• The isolated_vertices_begin() and isolated_vertices_end() methods return Arrangement_2::Isolated_vertex_iterator iterators that define the range of isolated vertices inside the face. The value type of this iterator is Vertex.

The function print_face() listed below prints the outer and inner boundaries of a given face, using the function print_ccb(), which was introduced in the previous subsection.

void print_face (Arrangement_2::Face_const_handle f)
{
  // Print the outer boundary.
  if (f->is_unbounded())
    std::cout << "Unbounded face. " << std::endl;
  else {
    std::cout << "Outer boundary: ";
    print_ccb (f->outer_ccb());
  }

  // Print the boundary of each of the holes.
  Arrangement_2::Hole_const_iterator hi;
  int                                 index = 1;
  for (hi = f->holes_begin(); hi != f->holes_end(); ++hi, ++index) {
    std::cout << "    Hole #" << index << ": ";
    print_ccb (*hi);
  }

  // Print the isolated vertices.
  Arrangement_2::Isolated_vertex_const_iterator iv;
  for (iv = f->isolated_vertices_begin(), index = 1;
       iv != f->isolated_vertices_end(); ++iv, ++index)
  {
    std::cout << "    Isolated vertex #" << index << ": "
              << "(" << iv->point() << ")" << std::endl;
  }
}

Additional Example

The function listed below prints the current setting of a given arrangement. This concludes the preview of the various traversal methods.³

void print_arrangement (const Arrangement_2& arr)
{
  // Print the arrangement vertices.
  Vertex_const_iterator vit;
  std::cout << arr.number_of_vertices() << " vertices:" << std::endl;
  for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {
    std::cout << "(" << vit->point() << ")";
    if (vit->is_isolated())
      std::cout << " - Isolated." << std::endl;
    else
      std::cout << " - degree " << vit->degree() << std::endl;
  }

  // Print the arrangement edges.
  Edge_const_iterator eit;
  std::cout << arr.number_of_edges() << " edges:" << std::endl;
  for (eit = arr.edges_begin(); eit != arr.edges_end(); ++eit)
    std::cout << "[" << eit->curve() << "]" << std::endl;

  // Print the arrangement faces.
  Face_const_iterator fit;
  std::cout << arr.number_of_faces() << " faces:" << std::endl;
  for (fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
    print_face (fit);
}

20.2.3   Modifying the Arrangement

In this section we review the various member functions of the Arrangement_2 class that allow users to modify the topological structure of the arrangement by introducing new edges or vertices, modifying them, or removing them.

The arrangement member-functions that insert new curves into the arrangement, thus enabling the construction of a planar subdivision, are rather specialized, as they require a-priori knowledge on the location of the inserted curve. Indeed, for most purposes it is more convenient to construct an arrangement using the free (global) insertion-functions.

Inserting Non-Intersecting $$x-Monotone Curves

The most important functions that allow users to modify the arrangement, and perhaps the most frequently used ones, are the specialized insertion functions of $$x-monotone curves whose interior is disjoint from any other curve in the existing arrangement and do not contain any vertex of the arrangement. In addition, these function require that the location of the curve in the arrangement is known.

The motivation behind these rather harsh restrictions on the nature of the inserted curves is the decoupling of the topological arrangement representation from the various algorithms that operate on it. While the insertion of an $$x-monotone curve whose interior is disjoint from all existing arrangement features is quite straightforward (as we show next), inserting curves that intersect with the curves already inserted into the arrangement is much more complicated and requires the application of non-trivial geometric algorithms. These insertion operations are therefore implemented as free functions that operate on the arrangement and the inserted curve(s); see Section 20.4 for more details and examples.⁴

When an $$x-monotone curve is inserted into an existing arrangement, such that the interior of this curve is disjoint from any arrangement feature, only the following three scenarios are possible, depending on the status of the endpoints of the inserted subcurve:

1. In case both curve endpoints do not correspond to any existing arrangement vertex we have to create two new vertices corresponding to the curve endpoints and connect them using a pair of twin halfedges. This halfedge pair initiates a new hole inside the face that contains the curve in its interior.
2. If exactly one endpoint corresponds to an existing arrangement vertex (we distinguish between a vertex that corresponds to the left endpoint of the inserted curve and a vertex corresponding to its right endpoint), we have to create a new vertex that corresponds to the other endpoint of the curve and to connect the two vertices by a pair of twin halfedges that form an ``antenna'' emanating from the boundary of an existing connected component (note that if the existing vertex used to be isolated, this operation is actually equivalent to forming a new hole inside the face that contains this vertex).

3. If both endpoints correspond to existing arrangement vertices, we connect these vertices using a pair of twin halfedges. (If one or both vertices are isolated this case reduces to one of the two previous cases respectively.) The two following subcases may occur:
   • Two disconnected components are merged into a single connected component (as is the case with the segment $$s₁ in the figure to the left).
   • A new face is created, a face that splits from an existing arrangement face. In this case we also have to examine the holes and isolated vertices in the existing face and move the relevant ones inside the new face (as is the case with the segment $$s₂ in the figure to the left).

The Arrangement_2 class offers insertion functions named insert_in_face_interior(), insert_from_left_vertex(), insert_from_right_vertex() and insert_at_vertices() that perform the special insertion procedures listed above. The first function accepts an $$x-monotone curve $$c and an arrangement face $$f that contains this curve in its interior. The other functions accept an $$x-monotone curve $$c and handles to the existing vertices that correspond to the curve endpoint(s). Each of the four functions returns a handle to one of the twin halfedges that have been created, where:

• insert_in_face_interior(c, f) returns a halfedge directed from the vertex corresponding to the left endpoint of c toward the vertex corresponding to its right endpoint.
• insert_from_left_vertex(c, v) and insert_from_right_vertex(c, v) returns a halfedge whose source is the vertex $$v that and whose target is the new vertex that has just been created.
• insert_at_vertices(c, v1, v2) returns a halfedge directed from $$v₁ to $$v₂.

The following program demonstrates the usage of the four insertion functions. It creates an arrangement of five line segments, as depicted in Figure 20.3.⁵ As the arrangement is very simple, we use the simple Cartesian kernel of CGAL with integer coordinates for the segment endpoints. We also use the Arr_segment_traits_2 class that enables the efficient maintenance of arrangements of line segments; see more details on this traits class in Section 20.6. This example, as many others in this chapter, uses some print-utility functions from the file print_arr.h; these functions are also listed in Section 20.2.2.

File: examples/Arrangement_2/edge_insertion.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/IO/Arr_iostream.h>

#include "arr_print.h"

typedef int                                           Number_type;
typedef CGAL::Simple_cartesian<Number_type>           Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef Traits_2::X_monotone_curve_2                  Segment_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef Arrangement_2::Vertex_handle                  Vertex_handle;
typedef Arrangement_2::Halfedge_handle                Halfedge_handle;

int main ()
{
  Arrangement_2   arr;

  Segment_2       s1 (Point_2 (1, 3), Point_2 (3, 5));
  Segment_2       s2 (Point_2 (3, 5), Point_2 (5, 3));
  Segment_2       s3 (Point_2 (5, 3), Point_2 (3, 1));
  Segment_2       s4 (Point_2 (3, 1), Point_2 (1, 3));
  Segment_2       s5 (Point_2 (1, 3), Point_2 (5, 3));

  Halfedge_handle e1 = arr.insert_in_face_interior (s1, arr.unbounded_face());
  Vertex_handle   v1 = e1->source();
  Vertex_handle   v2 = e1->target();
  Halfedge_handle e2 = arr.insert_from_left_vertex (s2, v2);
  Vertex_handle   v3 = e2->target();
  Halfedge_handle e3 = arr.insert_from_right_vertex (s3, v3);
  Vertex_handle   v4 = e3->target();
  Halfedge_handle e4 = arr.insert_at_vertices (s4, v4, v1);
  Halfedge_handle e5 = arr.insert_at_vertices (s5, v1, v3);

  print_arrangement (arr);
  return (0);
}

Observe that the first line segment is inserted in the interior of the unbounded face. The other line segments are inserted using the vertices created by the insertion of previous segments. The resulting arrangement consists of three faces, where the two bounded faces form together a hole in the unbounded face.

Manipulating Isolated Vertices

Isolated points are in general simpler geometric entities than curves and indeed the member functions that manipulate them are easier to understand.

The function insert_in_face_interior(p, f) inserts an isolated point $$p, located in the interior of a given face $$f, into the arrangement and returns a handle to the arrangement vertex it has created and associated with $$p. Naturally, this function has a precondition that $$p is really an isolated point, namely it does not coincide with any existing arrangement vertex and does not lie on any edge. As mentioned in Section 20.2.2, it is possible to obtain the face containing an isolated vertex handle $$v by calling v->face().

The function remove_isolated_vertex(v) receives a handle to an isolated vertex and removes it from the arrangement.

The following program demonstrates the usage of the arrangement member-functions for manipulating isolated vertices. It first inserts three isolated vertices located inside the unbounded face, then it inserts four line segments that form a rectangular hole inside the unbounded face (see Figure 20.4 for an illustration). Finally, it traverses the vertices and removes those isolated vertices that are still contained in the unbounded face ($$u₂ and $$u₃ in this case):

File: examples/Arrangement_2/isolated_vertices.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

#include "arr_print.h"

typedef int                                           Number_type;
typedef CGAL::Simple_cartesian<Number_type>           Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef Traits_2::X_monotone_curve_2                  Segment_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef Arrangement_2::Vertex_handle                  Vertex_handle;
typedef Arrangement_2::Halfedge_handle                Halfedge_handle;
typedef Arrangement_2::Face_handle                    Face_handle;

int main ()
{
  Arrangement_2   arr;

  // Insert some isolated points:
  Face_handle     uf = arr.unbounded_face();
  Vertex_handle   u1 = arr.insert_in_face_interior (Point_2 (3, 3), uf);
  Vertex_handle   u2 = arr.insert_in_face_interior (Point_2 (1, 5), uf);
  Vertex_handle   u3 = arr.insert_in_face_interior (Point_2 (5, 5), uf);

  // Insert four segments that form a rectangular face:
  Segment_2       s1 (Point_2 (1, 3), Point_2 (3, 5));
  Segment_2       s2 (Point_2 (3, 5), Point_2 (5, 3));
  Segment_2       s3 (Point_2 (5, 3), Point_2 (3, 1));
  Segment_2       s4 (Point_2 (3, 1), Point_2 (1, 3));

  Halfedge_handle e1 = arr.insert_in_face_interior (s1, uf);
  Vertex_handle   v1 = e1->source();
  Vertex_handle   v2 = e1->target();
  Halfedge_handle e2 = arr.insert_from_left_vertex (s2, v2);
  Vertex_handle   v3 = e2->target();
  Halfedge_handle e3 = arr.insert_from_right_vertex (s3, v3);
  Vertex_handle   v4 = e3->target();
  Halfedge_handle e4 = arr.insert_at_vertices (s4, v4, v1);

  // Remove the isolated vertices located in the unbounded face.
  Arrangement_2::Vertex_iterator        curr_v, next_v;

  for (curr_v = arr.vertices_begin();
       curr_v != arr.vertices_end(); curr_v = next_v)
  {
    // Store an iterator to the next vertex (as we may delete curr_v and
    // invalidate the iterator).
    next_v = curr_v;
    ++next_v;

    if (curr_v->is_isolated() && curr_v->face() == uf)
      arr.remove_isolated_vertex (curr_v);
  }

  print_arrangement (arr);
  return (0);
}

Manipulating Halfedges

In the previous subsection we showed how to introduce new isolated vertices in the arrangement. But how does one create a vertex that lies on an existing arrangement edge (more precisely, on an $$x-monotone curve that is associated with an arrangement edge)?

It should be noted that such an operation involves the splitting of a curve at a given point in its interior, while the traits class used by Arrangement_2 does not necessarily have the ability to perform such a split operation. However, if users have the ability to split an $$x-monotone curve into two at a given point $$p (this is usually the case when employing a more sophisticated traits class; see Section 20.6 for more details) they can use the split_edge(e, c1, c2) function, were $$c₁ and $$c₂ are the two subcurves resulting from splitting the $$x-monotone curve associated with the halfedge $$e at some point (call it $$p) in its interior. The function splits the halfedge pair into two pairs, both incident to a new vertex $$v associated with $$p, and returns a handle to a halfedge whose source equals $$e's source vertex and whose target is the new vertex $$v.

The reverse operation is also possible. Suppose that we have a vertex $$v of degree $$2, whose two incident halfedges, $$e₁ and $$e₂, are associated with the curves $$c₁ and $$c₂. Suppose further that it is possible to merge these two curves into a single continuous $$x-monotone curve $$c. Calling merge_edge(e1, e2, c) will merge the two edges into a single edge associated with the curve $$c, essentially removing the vertex $$v from the arrangement.

Finally, the function remove_edge(e) removes the edge $$e from the arrangement. Note that this operation is the reverse of an insertion operation, so it may cause a connected component to split into two, or two faces to merge into one, or a hole to disappear. By default, if the removal of e causes one of its end-vertices to become isolated, we remove this vertex as well. However, users can control this behavior and choose to keep the isolated vertices by supplying additional Boolean flags to remove_edge() indicating whether the source and the target vertices are to be removed should they become isolated.

In the following example program we show how the edge-manipulation functions can be used. The program works in three steps, as demonstrated in Figure 20.5. Note that here we still stick to integer coordinates, but as we work on a larger scale we use an unbounded integer number-type (in this case, the Gmpz type taken from the GMP library) instead of the built-in int type.⁶ In case the GMP library is not installed (as indicated by the CGAL_USE_GMP flag defined in CGAL/basic.h), we use MP_Float, a number-type included in CGAL's support library that is capable of storing floating-point numbers with unbounded mantissa. We also use the standard Cartesian kernel of CGAL as our kernel. This is recommended when the kernel is instantiated with a more complex number type, as we demonstrate in other examples in this chapter.

File: examples/Arrangement_2/edge_manipulation.cpp

#include <CGAL/basic.h>

#ifdef CGAL_USE_GMP
  #include <CGAL/Gmpz.h>
  typedef CGAL::Gmpz                                    Number_type;
#else
  #include <CGAL/MP_Float.h>
  typedef CGAL::MP_Float                                Number_type;
#endif

#include <CGAL/Cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

#include "arr_print.h"

typedef CGAL::Cartesian<Number_type>                  Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef Traits_2::X_monotone_curve_2                  Segment_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef Arrangement_2::Vertex_handle                  Vertex_handle;
typedef Arrangement_2::Halfedge_handle                Halfedge_handle;

int main ()
{
  // Step (a) - construct a triangular face.
  Arrangement_2   arr;

  Segment_2       s1 (Point_2 (667, 1000), Point_2 (4000, 5000));
  Segment_2       s2 (Point_2 (4000, 0), Point_2 (4000, 5000));
  Segment_2       s3 (Point_2 (667, 1000), Point_2 (4000, 0));

  Halfedge_handle e1 = arr.insert_in_face_interior (s1, arr.unbounded_face());
  Vertex_handle   v1 = e1->source();
  Vertex_handle   v2 = e1->target();
  Halfedge_handle e2 = arr.insert_from_right_vertex (s2, v2);
  Vertex_handle   v3 = e2->target();
  Halfedge_handle e3 = arr.insert_at_vertices (s3, v3, v1);

  // Step (b) - create additional two faces inside the triangle.
  Point_2         p1 (4000, 3666), p2 (4000, 1000);
  Segment_2       s4 (Point_2 (4000, 5000), p1);
  Segment_2       s5 (p1, p2);
  Segment_2       s6 (Point_2 (4000, 0), p2);

  Halfedge_handle e4 = arr.split_edge (e2, s4,
                                       Segment_2 (Point_2 (4000, 0), p1));
  Vertex_handle   w1 = e4->target();
  Halfedge_handle e5 = arr.split_edge (e4->next(), s5, s6);
  Vertex_handle   w2 = e5->target();
  Halfedge_handle e6 = e5->next();

  Segment_2       s7 (p1, Point_2 (3000, 2666));
  Segment_2       s8 (p2, Point_2 (3000, 1333));
  Segment_2       s9 (Point_2 (3000, 2666), Point_2 (2000, 1666));
  Segment_2       s10 (Point_2 (3000, 1333), Point_2 (2000, 1666));
  Segment_2       s11 (Point_2 (3000, 1333), Point_2 (3000, 2666));

  Halfedge_handle e7 = arr.insert_from_right_vertex (s7, w1);
  Vertex_handle   v4 = e7->target();
  Halfedge_handle e8 = arr.insert_from_right_vertex (s8, w2);
  Vertex_handle   v5 = e8->target();
  Vertex_handle   v6 = arr.insert_in_face_interior (Point_2 (2000, 1666),
                                                    e8->face());

  arr.insert_at_vertices (s9, v4, v6);
  arr.insert_at_vertices (s10, v5, v6);
  arr.insert_at_vertices (s11, v4, v5);

  // Step (c) - remove and merge faces to form a single hole in the traingle.
  arr.remove_edge (e7);
  arr.remove_edge (e8);

  e5 = arr.merge_edge (e5, e6, Segment_2 (e5->source()->point(),
                                          e6->target()->point()));
  e2 = arr.merge_edge (e4, e5, s2);

  print_arrangement (arr);
  return (0);
}

Note how we use the halfedge handles returned from split_edge() and merge_edge(). Also note the insertion of the isolated vertex $$v₆ located inside the triangular face (the incident face of $$e₇). This vertex seizes from being isolated, as it is gets connected to other vertices.

In this context, we should mention the two member functions modify_vertex(v, p), which sets $$p to be the point associated with the vertex $$v, and modify_edge(e, c), which sets $$c to be the $$x-monotone curve associated with the halfedge $$e. These functions have preconditions that $$p is geometrically equivalent to v->point() and $$c is equivalent to e->curve() (i.e., the two curves have the same graph), respectively, to avoid the invalidation of the geometric structure of the arrangement. At a first glance it may seen as these two functions are of little use. However, we should keep in mind that there may be extraneous data (probably non-geometric) associated with the point objects or with the curve objects, as defined by the traits class. With these two functions we can modify this data; see more details in Section 20.6.

In addition, we can use these functions to replace a geometric object (a point or a curve) with an equivalent object that has a more compact representation. For example, we can replace the point $$((20)/(40), (99)/(33)) associated with some vertex $$v, by $$((1)/(2), 3).

advanced

Advanced Insertion Functions

Assume that the specialized insertion function insert_from_left_vertex(c,v) is invoked for a curve $$c, whose left endpoint is already associated with a non-isolated vertex $$v. Namely, $$v has already several incident halfedges. It is necessary in this case to locate the exact place for the new halfedge mapped to the inserted new curve $$c in the circular list of halfedges incident to $$v. More precisely, it is sufficient to locate one of the halfedges pred directed toward $$v such that $$c is located between pred and pred->next() in clockwise order around $$v, in order to complete the insertion (see Figure 20.2 for an illustration). This may take $$O(d) time where $$d is the degree of the vertex. However, if the halfedge pred is known in advance, the insertion can be carried out in constant time.

The Arrangement_2 class provides the advanced versions of the specialized insertion functions for a curve $$c - namely we have insert_from_left_vertex(c,pred) and insert_from_right_vertex(c,pred) that accept a halfedge pred as specified above, instead of a vertex $$v. These functions are more efficient, as they take constant time and do not perform any geometric operations. Thus, they should be used when the halfedge pred is known. In case that the vertex $$v is isolated or that the predecessor halfedge for the new inserted curve is not known, the simpler versions of these insertion functions should be used.

Similarly, there exist two overrides of the insert_at_vertices() function: One that accept the two predecessor halfedges around the two vertices $$v₁ and $$v₂ that correspond to the curve endpoints, and one that accepts a handle for one vertex and a predecessor halfedge around the other vertex.

Figure 20.6:  An arrangement of line segments, as constructed in special_edge_insertion.cpp. Note that $$p₀ is initially inserted as an isolated point and later on connected to the other four vertices.

The following program shows how to construct the arrangement depicted in Figure 20.6 using the specialized insertion functions that accept predecessor halfedges:

File: examples/Arrangement_2/special_edge_insertion.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>

#include "arr_print.h"

typedef int                                           Number_type;
typedef CGAL::Simple_cartesian<Number_type>           Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef Traits_2::X_monotone_curve_2                  Segment_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef Arrangement_2::Vertex_handle                  Vertex_handle;
typedef Arrangement_2::Halfedge_handle                Halfedge_handle;

int main ()
{
  Arrangement_2   arr;

  Point_2         p0 (3, 3);
  Point_2         p1 (1, 3), p2 (3, 5), p3 (5, 3), p4 (3, 1);
  Segment_2       s1 (p1, p2);
  Segment_2       s2 (p2, p3);
  Segment_2       s3 (p3, p4);
  Segment_2       s4 (p4, p1);
  Segment_2       s5 (p1, p0);
  Segment_2       s6 (p0, p3);
  Segment_2       s7 (p4, p0);
  Segment_2       s8 (p0, p2);

  Vertex_handle   v0 = arr.insert_in_face_interior (p0, arr.unbounded_face());
  Halfedge_handle e1 = arr.insert_in_face_interior (s1, arr.unbounded_face());
  Halfedge_handle e2 = arr.insert_from_left_vertex (s2, e1);
  Halfedge_handle e3 = arr.insert_from_right_vertex (s3, e2);
  Halfedge_handle e4 = arr.insert_at_vertices (s4, e3, e1->twin());
  Halfedge_handle e5 = arr.insert_at_vertices (s5, e1->twin(), v0);
  Halfedge_handle e6 = arr.insert_at_vertices (s6, e5, e3->twin());
  Halfedge_handle e7 = arr.insert_at_vertices (s7, e4->twin(), e6->twin());
  Halfedge_handle e8 = arr.insert_at_vertices (s8, e5, e2->twin());

  print_arrangement (arr);
  return (0);
}

It is possible to perform even more refined operations on an Arrangement_2 instance given specific topological information. As most of these operations are very fragile and perform no precondition testing on their input in order to gain efficiency, they are not included in the public interface of the arrangement class. Instead, the Arr_accessor<Arrangement> class allows access to these internal arrangement operations - see more details in the Reference Manual.

advanced

20.3   Issuing Queries on an Arrangement

One of the most important query types defined on arrangements is the point-location query: Given a point, find the arrangement cell that contains it. Typically, the result of a point-location query is one of the arrangement faces, but in degenerate situations the query point can be located on an edge or coincide with a vertex.

Point-location queries are not only common in many applications, they also play an important role in the free insertion-functions (see Section 20.4). Therefore, it is crucial to have the ability to answer such queries effectively for any arrangement instance.

20.3.1   Point-Location Queries

The arrangement package includes several classes (more precisely, class templates parameterized by an arrangement class) that model the ArrangementPointLocation_2 concept. Namely, they all have a member function called locate(q) that accepts a query point $$q and result with a CGAL Object that wraps a handle to the arrangement cell containing the query point. This object can be assigned to either a Face_const_handle, Halfedge_const_handle or a Vertex_const_handle, depending on whether the query point is located inside a face, on an edge or on a vertex.

Note that the handles returned by the locate() functions are const (non-mutable) handles. If necessary, such handles may be casted to mutable handles using the static functions Arrangement_2::non_const_handle() provided by the arrangement class.

An instance of any point-location class must be attached to an Arrangement_2 instance so we can use it to issue point-location queries. This attachment can be performed when the point-location instance is constructed, or at a later time, using the init(arr) method, where arr is the attached Arrangement_2 instance. In this chapter we always use the first option.

The following function template, which can be found in the example file point_location_utils.h, accepts a point-location object (whose type can be any of the models to the ArrangementPointLocation_2 concept) and a query point, and prints out the result of the point-location query for the given point. Observe how we use the function CGAL::assign() is order to cast the resulting CGAL::Object into a handle to an arrangement feature. The point-location object pl is assumed to be already associated with an arrangement:

template <class PointLocation>
void point_location_query
        (const PointLocation& pl,
         const typename PointLocation::Arrangement_2::Point_2& q)
{
  // Perform the point-location query.
  CGAL::Object obj = pl.locate (q);

  // Print the result.
  typedef typename PointLocation::Arrangement_2  Arrangement_2;

  typename Arrangement_2::Vertex_const_handle    v;
  typename Arrangement_2::Halfedge_const_handle  e;
  typename Arrangement_2::Face_const_handle      f;

  std::cout << "The point " << q << " is located ";
  if (CGAL::assign (f, obj)) {
    // q is located inside a face:
    if (f->is_unbounded())
      std::cout << "inside the unbounded face." << std::endl;
    else
      std::cout << "inside a bounded face." << std::endl;
  }
  else if (CGAL::assign (e, obj)) {
    // q is located on an edge:
    std::cout << "on an edge: " << e->curve() << std::endl;
  }
  else if (CGAL::assign (v, obj)) {
    // q is located on a vertex:
    if (v->is_isolated())
      std::cout << "on an isolated vertex: " << v->point() << std::endl;
    else
      std::cout << "on a vertex: " << v->point() << std::endl;
  }
  else {
    CGAL_assertion_msg (false, "Invalid object.");
  }
}

Choosing a Point-Location Strategy

Each of the various point-location classes employs a different algorithm or strategy⁷ for answering queries:

• Arr_naive_point_location<Arrangement> locates the query point naively, by exhaustively scanning all arrangement cells.
• Arr_walk_along_a_line_point_location<Arrangement> simulates a traversal, in reverse order, along an imaginary vertical ray emanating from the query point: It starts from the unbounded face of the arrangement and moves downward toward the query point until locating the arrangement cell containing it.
• Arr_landmarks_point_location<Arrangement,Generator> uses a set of ``landmark'' points whose location in the arrangement is known. Given a query point, it uses a KD-tree to find the nearest landmark and then traverses the straight line segment connecting this landmark to the query point.

  There are various ways to select the landmark set in the arrangement, determined by the Generator template parameter. By default, the generator class Arr_landmarks_vertices_generator is used and the arrangement vertices are the selected landmarks, but other landmark generators, such as sampling random points or choosing points on a grid, are also available; see the Reference Manual for more details.

• Arr_trapezoid_ric_point_location<Arrangement> implements Mulmuley's point-location algorithm [Mul90] (see also [dBvKOS00, Chapter 6]). The arrangement faces are decomposed into simpler cells of constant complexity known as pseudo-trapezoids and a search-structure (a directed acyclic graph) is constructed on top of these cells, allowing to locate the pseudo-trapezoid (hence the arrangement cell) containing a query point in expected logarithmic time.

The main advantage of the first two strategies is that they do not require any extra data, so the respective classes just store a pointer to an arrangement object and operate directly on it. Attaching such point-location objects to an existing arrangement has virtually no running-time cost at all, but the query time is linear in the size of the arrangement (the performance of the ``walk'' strategy is much better in practice, but its worst-case performance is linear). Using these strategies is therefore recommended only when a relatively small number of point-location queries are issued by the application, or when the arrangement is constantly changing (i.e., changes in the arrangement structure are more frequent than point-location queries).

On the other hand, the landmarks and the trapezoid RIC strategies require auxiliary data structures on top of the arrangement, which they need to construct once they are attached to an arrangement object and need to keep up-to-date as this arrangement changes. The data structures needed by both strategies can be constructed in $$O(N log$$N) time (where $$N is the overall number of edges in the arrangement), but the construction needed by the landmark algorithm is in practice significantly faster. In addition, although both resulting data structures are asymptotically linear in size, the KD-tree that the landmark algorithm stores needs significantly less memory. We note that Mulmuley's algorithm guarantees a logarithmic query time, while the query time for the landmark strategy is only logarithmic on average - and we may have scenarios where the query time can be linear. In practice however, the query times of both strategies are competitive. For a detailed experimental comparison, see [HH05]

The main drawback in the current implementation of the landmark strategy, compared to the trapezoidal RIC strategy, is that while the updating the auxiliary data structures related to the trapezoidal decomposition is done very efficiently, the KD-tree maintained by the landmark algorithm needs to be frequently rebuilt as the arrangement changes. In addition, using the landmark point-location class adds some extra requirement from the traits class (that is, the traits class should be a model of a refined concept ArrangementLandmarkTraits_2; see Section 20.6 for the details). However, most built-in traits classes that come with the CGAL public release support these extra operations.

It is therefore recommended to use the Arr_landmarks_point_location class when the application frequently issues point-location queries on an arrangement that only seldom changes. If the arrangement is more dynamic and is frequently going through changes, the Arr_trapezoid_ric_point_location class should be the selected point-location strategy.

An Example

The following program constructs a simple arrangement of five line segments that form a pentagonal face, with a single isolated vertex in its interior, as depicted in Figure 20.7 (the arrangement construction is performed by the function construct_segment_arr() whose listing is omitted here and can be found in point_location_utils.h). It then employs the naive and the landmark strategies to issue several point-location queries on this arrangement:

File: examples/Arrangement_2/point_location.cpp

#include <CGAL/Simple_cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_naive_point_location.h>
#include <CGAL/Arr_landmarks_point_location.h>

#include "point_location_utils.h"

typedef int                                           Number_type;
typedef CGAL::Simple_cartesian<Number_type>           Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef CGAL::Arr_naive_point_location<Arrangement_2>      Naive_pl;
typedef CGAL::Arr_landmarks_point_location<Arrangement_2>  Landmarks_pl;

int main ()
{
  // Construct the arrangement.
  Arrangement_2    arr;
  Naive_pl         naive_pl (arr);
  Landmarks_pl     landmarks_pl;

  construct_segments_arr (arr);

  // Perform some point-location queries using the naive strategy.
  Point_2          q1 (1, 4);
  Point_2          q2 (4, 3);
  Point_2          q3 (6, 3);

  point_location_query (naive_pl, q1);
  point_location_query (naive_pl, q2);
  point_location_query (naive_pl, q3);

  // Attach the landmarks object to the arrangement and perform queries.
  Point_2          q4 (3, 2);
  Point_2          q5 (5, 2);
  Point_2          q6 (1, 0);

  landmarks_pl.attach (arr);

  point_location_query (landmarks_pl, q4);
  point_location_query (landmarks_pl, q5);
  point_location_query (landmarks_pl, q6);

  return (0);
}

Note that the program uses the auxiliary point_location_query() function template to nicely print the result of each query. This function can be found in the header file point_location_utils.h.

20.3.2   Vertical Ray Shooting

Another important query issued on arrangements is the vertical ray-shooting query: Given a query point, which arrangement feature do we encounter if we shoot a vertical ray emanating upward (or downward) from this point? In the general case the ray hits an edge, but it is possible that it hits a vertex, or that the arrangement does not have any feature lying directly above (or below) the query point.

All point-location classes listed in the previous section are also models of the ArrangementVerticalRayShoot_2 concept. That is, they all have member functions called ray_shoot_up(q) and ray_shoot_down(q) that accept a query point $$q and output a CGAL Object. This can be assigned to either a Halfedge_const_handle or to a Vertex_const_handle. Alternatively, the returned value is a Face_const_handle for the unbounded face of the arrangement, in case there is no edge or vertex lying directly above (or below) $$q.

The following function template, vertical_ray_shooting_query(), which also located in the header file point_location_utils.h, accepts a vertical ray-shooting object, whose type can be any of the models to the ArrangementVerticalRayShoot_2 concept and prints out the result of the upward vertical ray-shooting operations from a given query point. The ray-shooting object vrs is assumed to be already associated with an arrangement:

template <class VerticalRayShoot>
void vertical_ray_shooting_query
    (const VerticalRayShoot& vrs,
     const typename VerticalRayShoot::Arrangement_2::Point_2& q)
{
  // Perform the point-location query.
  CGAL::Object    obj = vrs.ray_shoot_up (q);

  // Print the result.
  typedef typename VerticalRayShoot::Arrangement_2  Arrangement_2;

  typename Arrangement_2::Vertex_const_handle    v;
  typename Arrangement_2::Halfedge_const_handle  e;
  typename Arrangement_2::Face_const_handle      f;

  std::cout << "Shooting up from " << q << " : "; 
  if (CGAL::assign (e, obj)) {
    // We hit an edge:
    std::cout << "hit an edge: " << e->curve() << std::endl;
  }
  else if (CGAL::assign (v, obj)) {
    // We hit a vertex:
    if (v->is_isolated())
      std::cout << "hit an isolated vertex: " << v->point() << std::endl;
    else
      std::cout << "hit a vertex: " << v->point() << std::endl;
  }
  else if (CGAL::assign (f, obj)) {
    // We did not hit anything:
    CGAL_assertion (f->is_unbounded());
    
    std::cout << "hit nothing." << std::endl; 
  }
  else {
    CGAL_assertion_msg (false, "Invalid object.");
  }
}

The following program uses the auxiliary function listed above to perform vertical ray-shooting queries on an arrangement. The arrangement and the query points are exactly the same as in point_location.cpp (see Figure 20.7):

File: examples/Arrangement_2/vertical_ray_shooting.cpp

#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <CGAL/Arr_trapezoid_ric_point_location.h>

#include "point_location_utils.h"

typedef CGAL::MP_Float                                Number_type;
typedef CGAL::Cartesian<Number_type>                  Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef CGAL::Arr_walk_along_line_point_location<Arrangement_2>  Walk_pl;
typedef CGAL::Arr_trapezoid_ric_point_location<Arrangement_2>    Trap_pl;

int main ()
{
  // Construct the arrangement.
  Arrangement_2    arr;
  Walk_pl          walk_pl (arr);
  Trap_pl          trap_pl;

  construct_segments_arr (arr);

  // Perform some vertical ray-shooting queries using the walk strategy.
  Point_2          q1 (1, 4);
  Point_2          q2 (4, 3);
  Point_2          q3 (6, 3);

  vertical_ray_shooting_query (walk_pl, q1);
  vertical_ray_shooting_query (walk_pl, q2);
  vertical_ray_shooting_query (walk_pl, q3);

  // Attach the trapezoid-RIC object to the arrangement and perform queries.
  Point_2          q4 (3, 2);
  Point_2          q5 (5, 2);
  Point_2          q6 (1, 0);

  trap_pl.attach (arr);
  vertical_ray_shooting_query (trap_pl, q4);
  vertical_ray_shooting_query (trap_pl, q5);
  vertical_ray_shooting_query (trap_pl, q6);

  return (0);
}

The number type we use in this example is CGAL's built-in MP_Float type which is a floating-point number with an unbounded mantissa and a 32-bit exponent. It supports construction from an integer or from a machine float or double and performs additions, subtractions and multiplications in an exact number.

20.3.3   Batched Point-Location

Suppose that at a given moment our application has to issue a relatively large number $$m of point-location queries on a specific arrangement instance. It is possible of course to define a point-location object and to issue separate queries on the arrangement. However, as explained in Section 20.3.1, choosing a simple point-location strategy (either the naive or the walk strategy) means inefficient queries, while the more sophisticated strategies need to construct auxiliary structures that incur considerable overhead in running time.

On the other hand, the arrangement package includes a free locate() function that accepts an arrangement a range of query points as its input and sweeps through the arrangement to locate all query points in one pass. The function outputs the query results as pairs, where each pair is comprised of a query point and a CGAL Object that represents the cell containing the point (see Section 20.3.1). The output pairs are sorted in increasing $$xy-lexicographical order of the query point.

The batched point-location operation can be performed in $$O((m+N)log$$(m+N)) time, where $$N is the number of edges in the arrangement. This means that when the number $$m of point-location queries is of the same order of magnitude as $$N, this operation is more efficient than issuing separate queries. This suggestion is also backed up by experimental results. Moreover, the batched point-location operation is also advantageous as it does not have to construct and maintain additional data structures.

The following program issues a batched point-location query, which is essentially equivalent to the six separate queries performed in point_location.cpp (see Section 20.3.1):

File: examples/Arrangement_2/batched_point_location.cpp

#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_batched_point_location.h>
#include <list>

#include "point_location_utils.h"

typedef CGAL::MP_Float                                Number_type;
typedef CGAL::Cartesian<Number_type>                  Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef std::pair<Point_2, CGAL::Object>              Query_result;

int main ()
{
  // Construct the arrangement.
  Arrangement_2    arr;

  construct_segments_arr (arr);

  // Perform a batched point-location query.
  std::list<Point_2>       query_points;
  std::list<Query_result>  results;

  query_points.push_back (Point_2 (1, 4));
  query_points.push_back (Point_2 (4, 3));
  query_points.push_back (Point_2 (6, 3));
  query_points.push_back (Point_2 (3, 2));
  query_points.push_back (Point_2 (5, 2));
  query_points.push_back (Point_2 (1, 0));

  locate (arr, query_points.begin(), query_points.end(),
	  std::back_inserter (results));

  // Print the results.
  std::list<Query_result>::const_iterator  res_iter;
  Arrangement_2::Vertex_const_handle       v;
  Arrangement_2::Halfedge_const_handle     e;
  Arrangement_2::Face_const_handle         f;

  for (res_iter = results.begin(); res_iter != results.end(); ++res_iter)
  {
    std::cout << "The point (" << res_iter->first << ") is located ";
    if (CGAL::assign (f, res_iter->second))
    {
      // The current qeury point is located inside a face:
      if (f->is_unbounded())
        std::cout << "inside the unbounded face." << std::endl;
      else
        std::cout << "inside a bounded face." << std::endl;
    }
    else if (CGAL::assign (e, res_iter->second))
    {
      // The current qeury point is located on an edge:
      std::cout << "on an edge: " << e->curve() << std::endl;
    }
    else if (CGAL::assign (v, res_iter->second))
    {
      // The current qeury point is located on a vertex:
      if (v->is_isolated())
        std::cout << "on an isolated vertex: " << v->point() << std::endl;
      else
        std::cout << "on a vertex: " << v->point() << std::endl;
    }
  }

  return (0);
}

20.4   Free Functions in the Arrangement Package

In Section 20.2 we reviewed in details the Arrangement_2 class, which represents two-dimensional subdivisions induced by planar curves, and mentioned that its interface is minimal in the sense that the member functions hardly perform any geometric algorithms and are mainly used for maintaining the topological structure of the subdivision. In this section we explain how to utilize the free (global) functions that operate on arrangements. The implementation of these operations typically require non-trivial geometric algorithms or load some extra requirements on the traits class.

20.4.1   Incremental Insertion Functions

Inserting Non-Intersecting Curves

In Section 20.2 we explained how to construct arrangements of $$x-monotone curves that are pairwise disjoint in their interior, when the location of the segment endpoints in the arrangement is known. Here we relax this constraint, and allow the location of the inserted $$x-monotone curve endpoints to be arbitrary, as it may be unknown at the time of insertion. We retain, for the moment, the requirement that the interior of the inserted curve is disjoint from all existing arrangement edges and vertices.

The free function insert_non_intersecting_curve(arr, c, pl) inserts the $$x-monotone curve $$c into the arrangement arr, with the precondition that the interior of $$c is disjoint from all arr's existing edges and vertices. The third argument pl is a point-location object attached to the arrangement, which is used for performing the insertion. It locates both curve endpoints in the arrangement, where each endpoint is expected to either coincide with an existing vertex or lie inside a face. It is possible to invoke one of the specialized insertion functions (see Section 20.2), based on the query results, and insert $$c at its proper position.⁸ The insertion operation thus hardly requires any geometric operations on top on the ones needed to answer the point-location queries. Moreover, it is sufficient that the arrangement class is instantiated with a traits class that models the ArrangementBasicTraits_2 concept (or the ArrangementLandmarkTraits_2 concept, if the landmark point-location strategy is used), which does not have to support the computation of intersection points between curves.

The variant insert_non_intersecting_curve(arr, c) is also available. Instead of accepting a user-defined point-location object, it defines a local instance of the walk point-location class and uses it to insert the curve.

Inserting $$x-Monotone Curves

The insert_non_intersecting_curve() function is very efficient, but its preconditions on the input curves are still rather restricting. Let us assume that the arrangement is instantiated with a traits class that models the refined ArrangementXMonotoneTraits_2 concept and supports intersection computations (see Section 20.6 for the exact details). Given an $$x-monotone curve, it is sufficient to locate its left endpoint in the arrangement and to trace its zone, namely the set of arrangement features crossing the curve, until the right endpoint is reached. Each time the new curve $$c crosses an existing vertex or an edge, the curve is split into subcurves (in the latter case, we have to split the curve associated with the existing halfedge as well) and associate new edges with the resulting subcurves. Recall that an edge is represented by a pair of twin halfedges, so we split it into two halfedge pairs.

The free function insert_x_monotone_curve(arr, c, pl) performs this insertion operation. It accepts an $$x-monotone curve $$c, which may intersect some of the curves already in the arrangement arr, and inserts it into the arrangement by computing its zone. Users may supply a point-location object pl, or use the default walk point-location strategy (namely, the variant insert_x_monotone_curve(arr, c) is also available). The running-time of this insertion function is proportional to the complexity of the zone of the curve $$c.

advanced

In some cases users may have a prior knowledge of the location of the left endpoint of the $$x-monotone curve c they wish to insert, so they can perform the insertion without issuing any point-location queries. This can be done by calling insert_x_monotone_curve(arr, c, obj), where obj is an object represents the location of c's left endpoint in the arrangement - namely it wraps a Vertex_const_handle, a Halfedge_const_handle or a Face_const_handle (see also Section 20.3.1).

advanced

Inserting General Curves

So far all our examples were of arrangements of line segments, where the Arrangement_2 template was instantiated with the Arr_segment_traits_2 class. In this case, the fact that insert_x_monotone_curve() accepts an $$x-monotone curve does not seem to be a restriction, as all line segments are $$x-monotone (note that we consider vertical line segments to be weakly $$x-monotone).

Suppose that we construct an arrangement of circles. A circle is obviously not $$x-monotone, so we cannot use insert_x_monotone_curve() in this case.⁹ However, it is possible to subdivide each circle into two $$x-monotone circular arcs (its upper half and its lower half) and to insert each $$x-monotone arc separately.

The free function insert_curve() requires that the traits class used by the arrangement arr to be a model of the concept ArrangementTraits_2, which refines the ArrangementXMonotoneTraits_2 concept. It has to define an additional Curve_2 type (which may differ from the X_monotone_curve_2 type), and support the subdivision of curves of this new type into $$x-monotone curves (see the exact details in Section 20.6). The insert_curve(arr, c, pl) function performs the insertion of the curve $$c, which does not need to be $$x-monotone, into the arrangement by subdividing it into $$x-monotone subcurves and inserting each one separately. Users may supply a point-location object pl, or use the default walk point-location strategy by calling insert_curve(arr, c).

Inserting Points

The arrangement class enables us to insert a point as an isolated vertex in a given face. The free function insert_point(arr, p, pl) inserts a vertex into arr that corresponds to the point p at an arbitrary location. It uses the point-location object pl to locate the point in the arrangement (by default, the walk point-location strategy is used), and acts according to the result as follows:

• If p is located inside a face, it is inserted as an isolated vertex inside this face.
• If p lies on an edge, the edge is split to create a vertex associated with p.
• Otherwise, p coincides with an existing vertex and we are done.

The arrangement arr should be instantiated with a traits class that models the ArrangementXMonotoneTraits_2 concept, as the insertion operation may involve splitting curves.

An Example

The program below constructs an arrangement of intersecting line-segments. We know that $$s₁ and $$s₂ do not intersect, so we use insert_non_intersecting_curve() to insert them into the empty arrangement. The rest of the segments are inserted using insert_x_monotone_curve() or insert_curve(), which are equivalent in case of line segments. The resulting arrangement consists of $$13 vertices, $$16 edges, and $$5 faces, as can be seen in Figure 20.8.

In the earlier examples, all arrangement vertices corresponded to segment endpoints. In this example we have additional vertices that correspond to intersection points between two segments. The coordinates of these intersection points are rational numbers, if the input coordinates are rational (or integer). Therefore, the Quotient<int> number type is used to represent the coordinates:

File: examples/Arrangement_2/incremental_insertion.cpp

#include <CGAL/Cartesian.h>
#include <CGAL/Quotient.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_walk_along_line_point_location.h>

#include "arr_print.h"

typedef CGAL::Quotient<int>                           Number_type;
typedef CGAL::Cartesian<Number_type>                  Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::Point_2                             Point_2;
typedef Traits_2::X_monotone_curve_2                  Segment_2;
typedef CGAL::Arrangement_2<Traits_2>                 Arrangement_2;
typedef CGAL::Arr_walk_along_line_point_location<Arrangement_2>   Walk_pl;

int main ()
{
  // Construct the arrangement of five intersecting segments.
  Arrangement_2  arr;
  Walk_pl        pl(arr);

  Segment_2      s1 (Point_2(1, 0), Point_2(2, 4));
  Segment_2      s2 (Point_2(5, 0), Point_2(5, 5));