User Manual

Authors

Andreas Fabri and Laurent Saboret

A Short Introduction to the Boost Property Maps Library

The Boost Property Map Library consists mainly of interface specifications in the form of concepts. These interface specifications are intended for use by implementors of generic libraries in communicating requirements on template parameters to their users. In particular, the Boost Property Map concepts define a general purpose interface for mapping key objects to corresponding value objects, thereby hiding the details of how the mapping is implemented from algorithms. The implementation of types fulfilling the property map interface is up to the client of the algorithm to provide.

The Boost Property Map Library also contains a few adaptors that convert commonly used data-structures that implement a mapping operation, such as builtin arrays (pointers), iterators, and std::map, to have the property map interface.

Free functions get and put allow getting and putting information through a property map. The data themselves may be stored in the element, or they may be stored in an external data structure, or they may be computed on the fly. This is an "implementation detail" of the particular property map.

Property maps in the Boost manuals: http://www.boost.org/libs/property_map/doc/property_map.html

CGAL and Boost Property Maps

Some algorithms in CGAL take as input parameters iterator ranges and property maps to access information attached to elements of the sequence.

For example, the algorithms of chapters Point Set Processing and Poisson Surface Reconstruction take as input parameters iterator ranges and property maps to access each point's position and normal. Position and normal might be represented in various ways, e.g., as a class derived from the CGAL point class, or as a std::pair<Point_3<K>, Vector_3<K> >, or as a boost::tuple<..,Point_3<K>, ..., Vector_3<K> >.

This component provides property maps to support these cases:

• Identity_property_map<T>
• First_of_pair_property_map<Pair> and Second_of_pair_property_map<Pair>
• Nth_of_tuple_property_map<N, Tuple>
• Dereference_property_map<T>

Example with Identity_property_map

The following example reads a point set and removes 5% of the points. It uses Identity_property_map<Point_3> as position property map.
File Point_set_processing_3/remove_outliers_example.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/property_map.h>
#include <CGAL/compute_average_spacing.h>
#include <CGAL/remove_outliers.h>
#include <CGAL/IO/read_xyz_points.h>

#include <vector>
#include <fstream>
#include <iostream>

// types
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;

int main(int argc, char*argv[])
{
  const char* fname = (argc>1)?argv[1]:"data/oni.xyz";
  // Reads a .xyz point set file in points[].
  // The Identity_property_map property map can be omitted here as it is the default value.
  std::vector<Point> points;
  std::ifstream stream(fname);
  if (!stream ||
      !CGAL::read_xyz_points(stream, std::back_inserter(points),
                             CGAL::Identity_property_map<Point>()))
  {
    std::cerr << "Error: cannot read file " << fname << std::endl;
    return EXIT_FAILURE;
  }

  // Removes outliers using erase-remove idiom.
  // The Identity_property_map property map can be omitted here as it is the default value.
  const int nb_neighbors = 24; // considers 24 nearest neighbor points

  // Estimate scale of the point set with average spacing
  const double average_spacing = CGAL::compute_average_spacing<CGAL::Sequential_tag>
    (points.begin(), points.end(), nb_neighbors);

  // FIRST OPTION //
  // I don't know the ratio of outliers present in the point set
  std::vector<Point>::iterator first_to_remove
    = CGAL::remove_outliers(points.begin(), points.end(),
                            CGAL::Identity_property_map<Point>(),
                            nb_neighbors,
                            100.,                  // No limit on the number of outliers to remove
                            2. * average_spacing); // Point with distance above 2*average_spacing are considered outliers


  std::cerr << (100. * std::distance(first_to_remove, points.end()) / (double)(points.size()))
            << "% of the points are considered outliers when using a distance threshold of "
            << 2. * average_spacing << std::endl;
  

  // SECOND OPTION //
  // I know the ratio of outliers present in the point set
  const double removed_percentage = 5.0; // percentage of points to remove

  points.erase(CGAL::remove_outliers(points.begin(), points.end(),
                                     CGAL::Identity_property_map<Point>(),
                                     nb_neighbors,
                                     removed_percentage, // Minimum percentage to remove
                                     0.), // No distance threshold (can be omitted)
               points.end());

  // Optional: after erase(), use Scott Meyer's "swap trick" to trim excess capacity
  std::vector<Point>(points).swap(points);

  return EXIT_SUCCESS;
}

Example with Pairs

The following example reads a point set from an input file and writes it to a file, both in the xyz format. Position and normal are stored in pairs and accessed through property maps.
File Point_set_processing_3/read_write_xyz_point_set_example.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/property_map.h>
#include <CGAL/IO/read_xyz_points.h>
#include <CGAL/IO/write_xyz_points.h>

#include <utility> // defines std::pair
#include <vector>
#include <fstream>
#include <iostream>

// types
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
typedef Kernel::Vector_3 Vector;

// Point with normal vector stored as a std::pair.
typedef std::pair<Point, Vector> Pwn;

int main(int argc, char*argv[])
{
  const char* fname = (argc>1)?argv[1]:"data/oni.xyz";
    // Reads a .xyz point set file in points[].
    // Note: read_xyz_points_and_normals() requires an output iterator
    // over points and as well as property maps to access each
    // point position and normal.
    std::vector<Pwn> points;
    std::ifstream in(fname);
    if (!in ||
        !CGAL::read_xyz_points_and_normals(
            in,std::back_inserter(points),
            CGAL::First_of_pair_property_map<Pwn>(),
            CGAL::Second_of_pair_property_map<Pwn>()))
    {
      std::cerr << "Error: cannot read file " << fname << std::endl;
      return EXIT_FAILURE;
    }

    // Saves point set.
    // Note: write_xyz_points_and_normals() requires an output iterator
    // over points as well as property maps to access each
    // point position and normal.
    std::ofstream out("oni_copy.xyz");
    if (!out ||
        !CGAL::write_xyz_points_and_normals(
            out, points.begin(), points.end(),
            CGAL::First_of_pair_property_map<Pwn>(),
            CGAL::Second_of_pair_property_map<Pwn>()))
    {
      return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

Example with Tuples

The following example reads a point set in the xyz format and computes the average spacing. Index, position and color are stored in a tuple and accessed through property maps.
File Point_set_processing_3/average_spacing_example.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/compute_average_spacing.h>
#include <CGAL/IO/read_xyz_points.h>

#include <vector>
#include <fstream>
#include <boost/tuple/tuple.hpp>

// Types
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::FT FT;
typedef Kernel::Point_3 Point;

// Data type := index, followed by the point, followed by three integers that
// define the Red Green Blue color of the point.
typedef boost::tuple<int, Point, int, int, int> IndexedPointWithColorTuple;

// Concurrency
#ifdef CGAL_LINKED_WITH_TBB
typedef CGAL::Parallel_tag Concurrency_tag;
#else
typedef CGAL::Sequential_tag Concurrency_tag;
#endif


int main(int argc, char*argv[])
{
    const char* fname = (argc>1)?argv[1]:"data/sphere_20k.xyz";
    // Reads a .xyz point set file in points.
    // As the point is the second element of the tuple (that is with index 1)
    // we use a property map that accesses the 1st element of the tuple.
    
    std::vector<IndexedPointWithColorTuple> points;
    std::ifstream stream(fname);
    if (!stream ||
        !CGAL::read_xyz_points(
            stream, std::back_inserter(points),
            CGAL::Nth_of_tuple_property_map<1,IndexedPointWithColorTuple>()))
    {
      std::cerr << "Error: cannot read file " << fname << std::endl;
      return EXIT_FAILURE;
    }

    // Initialize index and RGB color fields in tuple.
    // As the index and RGB color are respectively the first and third-fifth elements
    // of the tuple we use a get function from the property map that accesses the 0
    // and 2-4th elements of the tuple.
    for(unsigned int i = 0; i < points.size(); i++)
    {
      points[i].get<0>() = i;   // set index value of tuple to i

      points[i].get<2>() = 0;   // set RGB color to black
      points[i].get<3>() = 0;
      points[i].get<4>() = 0;
    }

    // Computes average spacing.
    const unsigned int nb_neighbors = 6; // 1 ring
    FT average_spacing = CGAL::compute_average_spacing<Concurrency_tag>(
                            points.begin(), points.end(),
                            CGAL::Nth_of_tuple_property_map<1,IndexedPointWithColorTuple>(),
                            nb_neighbors);
    std::cout << "Average spacing: " << average_spacing << std::endl;

    return EXIT_SUCCESS;
}