Authors: Matthias Bäsken

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 [1].

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

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

The Point_set_2 class depends on two template parameters T1 and T2. They are used as template parameters for the Delaunay_triangulation_2 class 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 Point_set_2 class supports the following kinds of queries:

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

For details about the running times see [1].

Example: Range Search

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.

File Point_set_2/range_search.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Point_set_2.h>
#include <list>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
 
typedef CGAL::Point_set_2<K>::Vertex_handle  Vertex_handle;
typedef K::Point_2                           Point_2;
 
int main()
{
  CGAL::Point_set_2<K> PSet;
  std::list<Point_2> Lr;
 
  Point_2 p1(12,14);
  Point_2 p2(-12,14);
  Point_2 p3(2,11);
  Point_2 p4(5,6);
  Point_2 p5(6.7,3.8);
  Point_2 p6(11,20);
  Point_2 p7(-5,6);
  Point_2 p8(12,0);
  Point_2 p9(4,31);
  Point_2 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_2 pt1=p10;
  Point_2 pt3=p3;
  Point_2 pt2 = Point_2(pt3.x(),pt1.y());
  Point_2 pt4 = Point_2(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;
}