Chapter 53
2D Search Structures

53.1   Introduction

Geometric queries are fundamental to many applications in computational geometry. The task is to maintain a dynamic set of geometric objects in such a way that certain queries can be performed efficiently. Typical examples of queries are: find out whether a given object is contained in the set, find all objects of the set lying in a given area (e.g. rectangle), find the object closest to a given point or find the pair of objects in the set lying closest to each other. Furthermore, the set should be dynamic in the sense that deletions and insertions of objects can be performed efficiently.

In computational geometry literature one can find many different data structures for maintaining sets of geometric objects. Most of them are data structures that have been developed to support a single very special kind of query operation. Examples are Voronoi diagrams for answering nearest neighbor searches, range trees for orthogonal range queries, partition trees for more general range queries, hierarchical triangulations for point location and segment trees for intersection queries ....

In many applications, different types of queries have to be performed on the same set of objects. A naive approach to this problem would use a collection of the above mentioned data structures to represent the set of objects and delegate every query operation to the corresponding structure. However, this is completely impractical since it uses too much memory and requires the maintenance of all these data structures in the presence of update operations.

Data structures that are non-optimal in theory seem to perform quite well in practice for many of these queries. For example, the Delaunay diagram turns out to be a very powerful data structure for storing dynamic sets of points under range and nearest neighbor queries. A first implementation and computational study of using Delaunay diagrams for geometric queries is described by Mehlhorn and Näher in  [MN00].

In this section we present a generic variant of a two dimensional point set data type supporting various geometric queries.

The CGAL::Point_set_2 class in this section is inherited from the two-dimensional CGAL Delaunay Triangulation data type.

The CGAL::Point_set_2 class depends on two template parameters T1 and T2. They are used as template parameters for the CGAL::Delaunay_triangulation_2 class CGAL::Point_set_2 is inherited from. T1 is a model for the geometric traits and T2 is a model for the triangulation data structure that the Delaunay triangulation expects.

The CGAL::Point_set_2 class supports the following kinds of queries:

• circular range search
• triangular range search
• isorectangular range search
• (k) nearest neighbor(s)

53.2   Examples

53.2.1   Range search operations

The following example program demonstrates the various range search operations of the two dimensional point set. First we construct a two dimensional point set $$PSet and initialize it with a few points. Then we perform circular, triangular and isorectangular range search operations on the point set.

rs_example.C :

// file: examples/Point_set_2/rs_example.C

#include <CGAL/Cartesian.h>
#include <list>
#include <CGAL/Point_set_2.h>

typedef CGAL::Cartesian<double>     K;

typedef CGAL::Point_set_2<K>::Vertex_handle  Vertex_handle;
typedef CGAL::Point_2<K>                         Point;

int main()
{
  CGAL::Point_set_2<K> PSet;
  std::list<Point> Lr;
  
  Point p1(12,14);
  Point p2(-12,14);  
  Point p3(2,11);
  Point p4(5,6);
  Point p5(6.7,3.8);
  Point p6(11,20);
  Point p7(-5,6);  
  Point p8(12,0);
  Point p9(4,31);
  Point p10(-10,-10); 
 
  Lr.push_back(p1); Lr.push_back(p2); Lr.push_back(p3);
  Lr.push_back(p4); Lr.push_back(p5); Lr.push_back(p6);
  Lr.push_back(p7); Lr.push_back(p8); Lr.push_back(p9);
  Lr.push_back(p10); 

  PSet.insert(Lr.begin(),Lr.end()); 

  std::cout << "circular range search !\n";  
  CGAL::Circle_2<K> rc(p5,p6);

  std::list<Vertex_handle> LV;
  PSet.range_search(rc, std::back_inserter(LV));

  std::list<Vertex_handle>::const_iterator it;
  for (it=LV.begin();it != LV.end(); it++)
     std::cout << (*it)->point() << "\n";      
 
  std::cout << "triangular range search !\n";    
  
  LV.clear();
  PSet.range_search(p1,p2,p3, std::back_inserter(LV));
  for (it=LV.begin();it != LV.end(); it++)
     std::cout << (*it)->point() << "\n";    
  LV.clear();
 
  std::cout << "isorectangular range search !\n";
  Point pt1=p10; 
  Point pt3=p3; 
  Point pt2 = Point(pt3.x(),pt1.y());
  Point pt4 = Point(pt1.x(),pt3.y());
  
  PSet.range_search(pt1,pt2,pt3,pt4, std::back_inserter(LV));
  for (it=LV.begin();it != LV.end(); it++)
    std::cout << (*it)->point() << "\n"; 
  return 0;
}