User Manual

Authors

Panagiotis Cheilaris, Sandeep Kumar Dey, Evanthia Papadopoulou

This chapter describes the algorithm and the geometric traits for constructing the segment Delaunay graph under the \( L_{\infty} \) distance. The traits also contain methods to draw the edges of the dual of the segment Delaunay graph under the \( L_{\infty} \) distance, i.e., the segment Voronoi diagram under the \( L_{\infty} \) distance. The \( L_{\infty} \) algorithm and traits rely on the segment Delaunay graph algorithm and traits under the Euclidean (or \( L_{2} \)) distance.

Segment Voronoi diagrams in the \( L_{\infty} \) metric have applications in VLSI design [3], [1].

In Section Definitions we give some definitions. In Section Software Design we explain the design of the algorithm and traits.

Figure 49.1 The \( L_{\infty} \) segment Voronoi diagram for a set of weakly (left) and strongly (right) intersecting sites.

Definitions

A pair of segment sites is called weakly intersecting if they have a single common point and this common point does not lie in the interior of any of the two sites. A pair of segment sites is called strongly intersecting if they intersect and they either have more than one common point or their common point lies in the interior of at least one of the two sites. We call a set of segment sites weakly (resp. strongly) intersecting if all its pairs are weakly (resp. strongly) intersecting or non-intersecting. See figure Figure 49.1.

Given two points \( p=(p_x,p_y) \), \( q=(q_x,q_y) \) in the plane, their \( L_{\infty} \) distance is

\[ d_{\infty}(p,q) = \max(|p_x-q_x|,|p_y-q_y|). \]

It is not difficult to see that the geometric locus of points at an equal fixed \( L_{\infty} \) distance \( r \) from a fixed point \( c \) is the axis-parallel square with center \( c \) and side length \( 2r \) (the analog in \( L_2 \) is a circle with center \( c \) and diameter \( 2r \)).

Bisectors and 1-Dimensionalization

If we assume general position of sites, then the \( L_{\infty} \) bisectors between two points or between a point and a segment are polygonal chains; see figure Figure 49.2 for examples. This is in contrast with the \( L_{2} \) Voronoi diagram in which the bisector between a point and a segment is a parabolic arc. In the \( L_{\infty} \) Voronoi diagram, if the coordinates of the input sites are rational, then the coordinates of the vertices of the diagram are also rational, which is not true for the \( L_{2} \) diagram. For more details on \( L_{\infty} \) bisectors and the diagram, see [1].

Figure 49.2 The \( L_{\infty} \) bisectors between two points and between a segment and a point.

One very important difference in the \( L_{\infty} \) setting (in comparison to the \( L_{2} \) setting) is that in some special non-general position cases the \( L_{\infty} \) bisector between two sites can be 2-dimensional. Since this creates problems when drawing the diagram, we resort to a 1-dimensionalization of these bisectors, by assigning portions of two-dimensional regions of a bisector to the two sites of the bisector. Moreover, this simplification of the diagram is acceptable in the VLSI applications, where the \( L_{\infty} \) diagram is employed [3].

If two different points \( p \), \( q \) share one coordinate, then their \( L_{\infty} \) bisector is 2-dimensional as shown in Figure 49.3. In this special case, we 1-dimensionalize the bisector, by taking instead the Euclidean bisector of the two points.

Figure 49.3 The \( L_{\infty} \) bisector between two points with the same \( y \) coordinate and its 1-dimensionalization.

Similarly, the bisector between the interior of an axis-parallel segment and one of its endpoints is also 2-dimensional as shown in Figure 49.4. We 1-dimensionalize this bisector by taking instead the line passing through the endpoint that is perpendicular to the segment.

Figure 49.4 The \( L_{\infty} \) bisector between a vertical segment and one of its endpoints and its 1-dimensionalization.

Software Design

In general, the software design of the algorithms and traits for the \( L_{\infty} \) segment Delaunay graph rely on the corresponding algorithms and traits for the \( L_{2} \) Segment Delaunay graph. We implement the \( L_{\infty} \) classes as subclasses of corresponding \( L_{2} \) classes from the package 2D Segment Delaunay Graphs. The names of the \( L_{\infty} \) classes contain an additional _Linf after graph, in comparison with the corresponding \( L_{2} \) classes. For more details, see [1].

The order of complexity of the construction of the \( L_{\infty} \) diagram is the same as the one of the \( L_{2} \) diagram and thus we refer the end user to [2] for complexity analysis.

Segment Delaunay Graph

The \( L_{\infty} \) segment Delaunay graph class template Segment_Delaunay_graph_Linf_2<SegmentDelaunayGraphLinfTraits_2,SegmentDelaunayGraphDataStructure_2> is derived from the class template Segment_Delaunay_graph_2. In the \( L_{\infty} \) class template, a few methods that are used when inserting a point in the interior of an existing segment are overridden.

Segment Delaunay Graph Traits

As in the case of \( L_{2} \), the geometric predicates are quite elaborate and we do not bother the end user with details. Our implementation reuses the \( L_{2} \) traits, wherever possible, but there are extensive differences. We support geometric and arithmetic filtering, as the \( L_{2} \) predicates do. For more details on these filtering techniques, see Section The Geometric Traits of the segment Delaunay graph package manual.

In analogy with the \( L_{2} \) setting, there are four models of the SegmentDelaunayGraphLinfTraits_2 concept, two of which support strongly intersecting sites (Segment_Delaunay_graph_Linf_traits_2, Segment_Delaunay_graph_Linf_filtered_traits_2) and two of which support sites without intersections (Segment_Delaunay_graph_Linf_traits_without_intersections_2, Segment_Delaunay_graph_Linf_filtered_traits_without_intersections_2). Refer to Subsection Optimizing Memory Allocation of the segment Delaunay graph package manual, which explains when to use each of these traits.

Segment Delaunay Graph Hierarchy

The Segment_Delaunay_graph_Linf_hierarchy_2 class is equivalent to the Segment_Delaunay_graph_hierarchy_2, but it uses the Segment_Delaunay_graph_Linf_2 class in each level of the hierarchy instead of Segment_Delaunay_graph_2. For a comparison of the performance of the plain graph class and the hierarchy class, we refer the end user to Section The Segment Delaunay Graph Hierarchy of the segment Delaunay graph package manual.

Obtaining the Voronoi Diagram from the Delaunay Graph

Class Voronoi_diagram_2 from the Voronoi diagram adaptor package can be used to obtain the \( L_{\infty} \) segment Voronoi diagram from the \( L_{\infty} \) segment Delaunay graph (or hierarchy).

Examples

The following examples show the usage of the \( L_{\infty} \) algorithm and traits. They are similar to the examples in the \( L_{2} \) segment Delaunay graph package.

First Example using the Filtered Traits

The following example shows how to use the segment Delaunay graph filtered traits mechanism. In addition it shows how to use a few of the iterators provided by the Segment_Delaunay_graph_Linf_2 class in order to count a few site-related quantities.
File Segment_Delaunay_graph_Linf_2/sdg-count-sites-linf.cpp

// standard includes
#include <iostream>
#include <fstream>
#include <cassert>

// define the input kernel
#include <CGAL/Simple_cartesian.h>
typedef CGAL::Simple_cartesian<double>     CK;

// typedefs for the traits and the algorithm
#include <CGAL/Segment_Delaunay_graph_Linf_filtered_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_Linf_2.h>

typedef CGAL::Segment_Delaunay_graph_Linf_filtered_traits_2<
          CK,CGAL::Field_with_sqrt_tag>  Gt;

typedef CGAL::Segment_Delaunay_graph_Linf_2<Gt>      SDG2;

using namespace std;

int main( int argc, char *argv[] ) {
  if ( ! (( argc == 1 ) || (argc == 2)) ) {
    std::cout <<"usage: "<< argv[0] <<" [filename]\n";
  }

  ifstream ifs( (argc == 1) ? "data/sitesx.cin" : argv[1] );
  assert( ifs );

  SDG2          sdg;
  SDG2::Site_2  site;

  while ( ifs >> site ) { sdg.insert( site ); }

  ifs.close();

  assert( sdg.is_valid(true, 1) );
  cout << endl << endl;

  // print the number of input and output sites
  cout << "# of input sites : " << sdg.number_of_input_sites() << endl;
  cout << "# of output sites: " << sdg.number_of_output_sites() << endl;

  unsigned int n_ipt(0), n_iseg(0), n_opt(0), n_oseg(0), n_ptx(0);

  // count the number of input points and input segments
  SDG2::Input_sites_iterator iit;
  for (iit = sdg.input_sites_begin(); iit != sdg.input_sites_end(); ++iit)
    {
      if ( iit->is_point() ) { n_ipt++; } else { n_iseg++; }
    }

  // count the number of output points and output segments, as well
  // as the number of points that are points of intersection of pairs
  // of strongly intersecting sites
  SDG2::Output_sites_iterator oit;
  for (oit = sdg.output_sites_begin(); oit != sdg.output_sites_end(); ++oit)
    {
      if ( oit->is_segment() ) { n_oseg++; } else {
        n_opt++;
        if ( !oit->is_input() ) { n_ptx++; }
      }
    }

  cout << endl << "# of input segments:  " << n_iseg << endl;
  cout << "# of input points:    " << n_ipt << endl << endl;
  cout << "# of output segments: " << n_oseg << endl;
  cout << "# of output points:   " << n_opt << endl << endl;
  cout << "# of intersection points: " << n_ptx << endl;

  return 0;
}

Using Spatial Sorting to Speed up Insertion

If you have a rather large input, you better use an insertion function that uses the spatial sorting of your input (end) points. Note that the functions insert_points or insert_segments can be used if your input is only composed of points or segments.
File Segment_Delaunay_graph_Linf_2/sdg-fast-sp-linf.cpp

// standard includes
#include <iostream>
#include <fstream>
#include <cassert>

// example that uses the filtered traits,
// the segment Delaunay graph and the spatial sorting

// choose the kernel
#include <CGAL/Simple_cartesian.h>

typedef CGAL::Simple_cartesian<double> K;

// typedefs for the traits and the algorithm
#include <CGAL/Segment_Delaunay_graph_Linf_2.h>
#include <CGAL/Segment_Delaunay_graph_Linf_filtered_traits_2.h>

typedef CGAL::Segment_Delaunay_graph_Linf_filtered_traits_without_intersections_2<K> Gt;

typedef CGAL::Segment_Delaunay_graph_Linf_2<Gt>  SDG2;


int main()
{
  std::ifstream ifs("data/sites.cin");
  assert( ifs );

  SDG2          sdg;
  SDG2::Site_2  site;

  std::vector<SDG2::Site_2> sites;
  // read the sites
  while ( ifs >> site ) {
    sites.push_back(site);
  }

  //insert the sites all at once using spatial sorting to speed the insertion
  sdg.insert( sites.begin(), sites.end(),CGAL::Tag_true() );

  // validate the segment Delaunay graph
  assert( sdg.is_valid(true, 1) );

  return 0;
}

Delaunay Graph of a Polygon

This example shows how to efficiently compute the Delaunay graph of a simple polygon using the spatial sorting to speed up the insertion.
File Segment_Delaunay_graph_Linf_2/sdg-fast-sp-polygon-linf.cpp

// standard includes
#include <iostream>
#include <fstream>
#include <cassert>

// example that uses the filtered traits,
// the segment Delaunay graph and the spatial sorting

// choose the kernel
#include <CGAL/Simple_cartesian.h>

typedef CGAL::Simple_cartesian<double> K;

// typedefs for the traits and the algorithm
#include <CGAL/Segment_Delaunay_graph_Linf_2.h>
#include <CGAL/Segment_Delaunay_graph_Linf_filtered_traits_2.h>

typedef CGAL::Segment_Delaunay_graph_Linf_filtered_traits_without_intersections_2<K> Gt;
typedef CGAL::Segment_Delaunay_graph_Linf_2<Gt>  SDG2;


int main()
{
  std::ifstream ifs("data/sites.cin");
  assert( ifs );

  //polygon points
  std::vector<Gt::Point_2> points;
  //segments of the polygon as a pair of point indices
  std::vector<std::pair<std::size_t,std::size_t> > indices;

  SDG2::Site_2 site;
  //read a close polygon given by its segments
  // s x0 y0 x1 y1
  // s x1 y1 x2 y2
  // ...
  // s xn yn x0 y0
  ifs >> site;
  assert( site.is_segment() );
  points.push_back( site.source_of_supporting_site() );

  std::size_t k=0;
  while ( ifs >> site ) {
    assert( site.is_segment() );
    points.push_back( site.source_of_supporting_site() );
    indices.push_back( std::make_pair(k, k+1) );
    ++k;
  }
  indices.push_back( std::make_pair(k, 0) );
  ifs.close();

  SDG2          sdg;

  //insert the polygon segments all at once using spatial sorting to speed the insertion
  sdg.insert_segments( points.begin(), points.end(), indices.begin(), indices.end() );

  // validate the segment Delaunay graph
  assert( sdg.is_valid(true, 1) );

  return 0;
}

Using the Hierarchy for Faster Location

The following example shows how to use the segment Delaunay graph hierarchy along with the filtered traits class that supports intersecting sites. The hierarchy should be preferred when the size of the input is large: Experiments suggest that the hierarchy is faster than the plain segment Delaunay graph when the size of the input exceeds 1000 sites.
File Segment_Delaunay_graph_Linf_2/sdg-filtered-traits-linf.cpp

// standard includes
#include <iostream>
#include <fstream>
#include <cassert>

// example that uses the filtered traits and
// the segment Delaunay graph hierarchy

// choose the kernel
#include <CGAL/Simple_cartesian.h>

typedef CGAL::Simple_cartesian<double> Rep;

// typedefs for the traits and the algorithm
#include <CGAL/Segment_Delaunay_graph_Linf_hierarchy_2.h>
#include <CGAL/Segment_Delaunay_graph_Linf_filtered_traits_2.h>

typedef CGAL::Segment_Delaunay_graph_Linf_filtered_traits_2<Rep> Gt;

typedef CGAL::Segment_Delaunay_graph_Linf_hierarchy_2<Gt>  SDG2;


int main( int argc, char *argv[] )
{
  if ( ! (( argc == 1 ) || (argc == 2)) ) {
    std::cout <<"usage: "<< argv[0] <<" [filename]\n";
  }

  std::ifstream ifs( (argc == 1) ? "data/sites.cin" : argv[1] );
  assert( ifs );

  SDG2          sdg;
  SDG2::Site_2  site;

  // read the sites and insert them in the segment Delaunay graph
  while ( ifs >> site ) {
    sdg.insert(site);
  }

  // validate the segment Delaunay graph
  assert( sdg.is_valid(true, 1) );

  return 0;
}

Voronoi Edges

The following example demonstrates how to recover the defining sites for the edges of the Voronoi diagram (which are the duals of the edges of the segment Delaunay graph computed).
File Segment_Delaunay_graph_Linf_2/sdg-voronoi-edges-linf.cpp

// standard includes
#include <iostream>
#include <fstream>
#include <cassert>
#include <string>

// define the kernel
#include <CGAL/Simple_cartesian.h>
#include <CGAL/Filtered_kernel.h>

typedef CGAL::Simple_cartesian<double>    CK;
typedef CGAL::Filtered_kernel<CK>         Kernel;

// typedefs for the traits and the algorithm
#include <CGAL/Segment_Delaunay_graph_Linf_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_Linf_2.h>

typedef CGAL::Segment_Delaunay_graph_Linf_traits_2<Kernel>  Gt;
typedef CGAL::Segment_Delaunay_graph_Linf_2<Gt>             SDG2;

using namespace std;

int main( int argc, char *argv[] ) {
  if ( ! (( argc == 1 ) || (argc == 2)) ) {
    std::cout <<"usage: "<< argv[0] <<" [filename]\n";
  }

  ifstream ifs( (argc == 1) ? "data/sites2.cin" : argv[1] );
  assert( ifs );

  SDG2          sdg;
  SDG2::Site_2  site;

  // read the sites from the stream and insert them in the diagram
  while ( ifs >> site ) {
    sdg.insert( site );
    CGAL_SDG_DEBUG( sdg.file_output_verbose(std::cout); );
    CGAL_assertion( sdg.is_valid(false, 1) );
  }

  ifs.close();


  std::cout << "About to validate diagram ..." << std::endl;

  // validate the diagram
  assert( sdg.is_valid(false, 1) );
  cout << endl << endl;

  std::cout << "Diagram validated." << std::endl;

  /*
  // now walk through the non-infinite edges of the segment Delaunay
  // graphs (which are dual to the edges in the Voronoi diagram) and
  // print the sites defining each Voronoi edge.
  //
  // Each oriented Voronoi edge (horizontal segment in the figure
  // below) is defined by four sites A, B, C and D.
  //
  //     \                     /
  //      \         B         /
  //       \                 /
  //     C  -----------------  D
  //       /                 \
  //      /         A         \
  //     /                     \
  //
  // The sites A and B define the (oriented) bisector on which the
  // edge lies whereas the sites C and D, along with A and B define
  // the two endpoints of the edge. These endpoints are the Voronoi
  // vertices of the triples A, B, C and B, A, D.
  // If one of these vertices is the vertex at infinity the string
  // "infinite vertex" is printed; the corresponding Voronoi edge is
  // actually a stright-line or parabolic ray.
  // The sites below are printed in the order A, B, C, D.
  */

  string inf_vertex("infinite vertex");
  char vid[] = {'A', 'B', 'C', 'D'};

  SDG2::Finite_edges_iterator eit = sdg.finite_edges_begin();
  for (int k = 1; eit != sdg.finite_edges_end(); ++eit, ++k) {
    SDG2::Edge e = *eit;
    // get the vertices defining the Voronoi edge
    SDG2::Vertex_handle v[] = { e.first->vertex( sdg.ccw(e.second) ),
                                e.first->vertex( sdg.cw(e.second) ),
                                e.first->vertex( e.second ),
                                sdg.tds().mirror_vertex(e.first, e.second) };

    cout << "--- Edge " << k << " ---" << endl;
    for (int i = 0; i < 4; i++) {
      // check if the vertex is the vertex at infinity; if yes, print
      // the corresponding string, otherwise print the site
      if ( sdg.is_infinite(v[i]) ) {
        cout << vid[i] << ": " << inf_vertex << endl;
      } else {
        cout << vid[i] << ": " << v[i]->site() << endl;
      }
    }
    cout << endl;
  }

  return 0;
}