CGAL: выпуклая оболочка точек с информацией

У меня есть вектор 2D-точек (N элементов) на плоскости. Я хочу сделать выпуклую оболочку этих точек. После этого я хочу получить векторный индекс каждой вершины в выпуклой оболочке, как мне это сделать?

Я знаю, что есть такая возможность для триангуляции с использованием vector<pair<Point_2, unsigned> >, но когда я использую парную точку для создания выпуклой оболочки, это выдает кучу ошибок. Это связанный фрагмент кода, который я использую:

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <CGAL/convex_hull_traits_2.h>

using namespace std;

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef pair<Point_2, unsigned> Paired;
typedef CGAL::convex_hull_traits_2<Paired> ch_traits;

typedef vector<Paired> Vector;

int main()
{
    Vector points;
    Vector result;

    for (int i = 0; i < 5; i++)
         points.push_back(make_pair(Point_2(i, i), i));
    CGAL::convex_hull_2( points.begin(), points.end(), back_inserter(result), const Traits &ch_traits );

  return 0;
}

c++ cgal stl convex-hull
person user252935    schedule 28.04.2017    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вам необходимо предоставить модель класса признаков ConvexHullTraits, типом пары является ваш тип точки. На практике это довольно просто, вам просто нужна структура, содержащая все функторы, а операторы просто направляются в функтор класса признаков CGAL, используя pair::first.

Вот простой пример:

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <CGAL/convex_hull_traits_2.h>

#include <boost/foreach.hpp>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::pair<Point_2, unsigned> Point_with_info;

template <class F>
struct Forward_functor
  : public F
{
  template <class Point_2>
  bool operator() (const Point_2& p, const Point_2& q) const
  {
    return static_cast<const F*>(this)->operator()(p.first, q.first);
  }

  template <class Point_2>
  bool operator() (const Point_2& p, const Point_2& q, const Point_2& r) const
  {
    return static_cast<const F*>(this)->operator()(p.first, q.first, r.first);
  }

  template <class Point_2>
  bool operator() (const Point_2& p, const Point_2& q, const Point_2& r, const Point_2& s) const
  {
    return static_cast<const F*>(this)->operator()(p.first, q.first, r.first, s.first);
  }
};

struct CH_traits_for_point_with_info
{
  typedef Point_with_info Point_2;
  typedef CGAL::Convex_hull_traits_2<K> Base;
  typedef Forward_functor<Base::Less_xy_2> Less_xy_2;
  typedef Forward_functor<Base::Less_yx_2> Less_yx_2;
  typedef Forward_functor<Base::Less_signed_distance_to_line_2> Less_signed_distance_to_line_2;
  typedef Forward_functor<Base::Less_rotate_ccw_2> Less_rotate_ccw_2;
  typedef Forward_functor<Base::Left_turn_2> Left_turn_2;
  typedef Forward_functor<Base::Equal_2> Equal_2;

  struct Orientation_2
  {
    CGAL::Orientation
    operator()(const Point_2& p, const Point_2& q, const Point_2& r) const
    {
      return Base::Orientation_2()(p.first, q.first, r.first);
    }
  };

  Equal_2 equal_2_object () const
  {
    return Equal_2();
  }

  Less_xy_2 less_xy_2_object () const
  {
    return Less_xy_2();
  }

  Less_yx_2 less_yx_2_object () const
  {
    return Less_yx_2();
  }

  Less_signed_distance_to_line_2 less_signed_distance_to_line_2_object () const
  {
    return Less_signed_distance_to_line_2();
  }

  Less_rotate_ccw_2 less_rotate_ccw_2_object () const
  {
    return Less_rotate_ccw_2();
  }

  Left_turn_2 left_turn_2_object () const
  {
    return Left_turn_2();
  }

  Orientation_2 orientation_2_object () const
  {
    return Orientation_2();
  }
};

int main()
{
  std::vector<Point_with_info> input_points;
  std::vector<Point_with_info> result;

  input_points.push_back( Point_with_info(Point_2(0,0), 0) );
  input_points.push_back( Point_with_info(Point_2(1,0), 1) );
  input_points.push_back( Point_with_info(Point_2(0,1), 2) );
  input_points.push_back( Point_with_info(Point_2(0.25,0.25), 3) );

  CGAL::convex_hull_2(input_points.begin(), input_points.end(),
                      back_inserter(result), CH_traits_for_point_with_info() );

  BOOST_FOREACH(const Point_with_info& p, result)
  {
    std::cout << p.first << " - " << p.second << "\n";
  }

  return 0;
}

Вот более сложный пример, когда точки не копируются, а алгоритм работает с индексами точек:

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
#include <CGAL/convex_hull_traits_2.h>

#include <boost/foreach.hpp>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;


template <class F>
struct Forward_functor
  : public F
{
  const std::vector<Point_2>& points;

  Forward_functor(const std::vector<Point_2>& points)
    : points(points)
  {}

  template <class Id>
  bool operator() (const Id& p, const Id& q) const
  {
    return static_cast<const F*>(this)->operator()(points[p], points[q]);
  }

  template <class Id>
  bool operator() (const Id& p, const Id& q, const Id& r) const
  {
    return static_cast<const F*>(this)->operator()(points[p], points[q], points[r]);
  }

  template <class Id>
  bool operator() (const Id& p, const Id& q, const Id& r, const Id& s) const
  {
    return static_cast<const F*>(this)->operator()(points[p], points[q], points[r], points[s]);
  }
};

struct CH_traits_for_point_with_info
{
  const std::vector<K::Point_2>& points;

  CH_traits_for_point_with_info(const std::vector<K::Point_2>& points)
    : points(points)
  {}

  typedef unsigned Point_2;
  typedef CGAL::Convex_hull_traits_2<K> Base;
  typedef Forward_functor<Base::Less_xy_2> Less_xy_2;
  typedef Forward_functor<Base::Less_yx_2> Less_yx_2;
  typedef Forward_functor<Base::Less_signed_distance_to_line_2> Less_signed_distance_to_line_2;
  typedef Forward_functor<Base::Less_rotate_ccw_2> Less_rotate_ccw_2;
  typedef Forward_functor<Base::Left_turn_2> Left_turn_2;
  typedef Forward_functor<Base::Equal_2> Equal_2;

  struct Orientation_2
  {
    const std::vector<K::Point_2>& points;

    Orientation_2(const std::vector<K::Point_2>& points)
      : points(points)
    {}

    CGAL::Orientation
    operator()(Point_2 p, Point_2 q, Point_2 r) const
    {
      return Base::Orientation_2()(points[p], points[q], points[r]);
    }
  };

  Equal_2 equal_2_object () const
  {
    return Equal_2(points);
  }

  Less_xy_2 less_xy_2_object () const
  {
    return Less_xy_2(points);
  }

  Less_yx_2 less_yx_2_object () const
  {
    return Less_yx_2(points);
  }

  Less_signed_distance_to_line_2 less_signed_distance_to_line_2_object () const
  {
    return Less_signed_distance_to_line_2(points);
  }

  Less_rotate_ccw_2 less_rotate_ccw_2_object () const
  {
    return Less_rotate_ccw_2(points);
  }

  Left_turn_2 left_turn_2_object () const
  {
    return Left_turn_2(points);
  }

  Orientation_2 orientation_2_object () const
  {
    return Orientation_2(points);
  }
};

int main()
{
  std::vector<Point_2> input_points;
  std::vector<unsigned> ids;
  std::vector<unsigned> result;

  input_points.push_back( Point_2(0,0) );
  input_points.push_back( Point_2(0,1) );
  input_points.push_back( Point_2(1,0) );
  input_points.push_back( Point_2(0.25,0.25) );

  ids.push_back(0);
  ids.push_back(1);
  ids.push_back(2);
  ids.push_back(3);

  CGAL::convex_hull_2(ids.begin(), ids.end(),
                      back_inserter(result), CH_traits_for_point_with_info(input_points) );

  BOOST_FOREACH(unsigned i, result)
  {
    std::cout << input_points[i] << " - " << i << "\n";
  }

  return 0;
}
person sloriot    schedule 02.05.2017
comment
Я обновил вопрос. Я не очень хорошо знаком с STL, поэтому не могу понять ответ. Однако я читал о функторах, которые пригодятся, когда функция используется в сочетании с алгоритмами STL. Но я до сих пор не знаю, как это сделать. - person user252935; 10.05.2017
comment
Если возможно, приведите мне несколько примеров того, как это сделать. @sloriot - person user252935; 10.05.2017
comment
Есть ли способ сделать это без структуры и функтора? - person Alec Jacobson; 28.03.2019
comment
@AlecJacobson Что ты имеешь в виду? Используя синтаксис C++11, мы можем сделать его меньше, если это то, что вам нужно. - person sloriot; 28.03.2019
comment
Я думаю, я надеюсь, что есть способ сделать это без всего шаблона. Позже я прибегнул к простому определению точек, потому что это две строки в libigl, а не 75+ строк структур / функторов в CGAL для прикрепления индексов к точкам. - person Alec Jacobson; 28.03.2019
comment
Работа выполнена в 3D, но не в 2D. Я открыл проблему. - person sloriot; 28.03.2019
comment
Я просто положил его в PR, то есть пример и заголовочный файл. Если вы возьмете два файла, которые я создал для PR, вам даже не придется ждать следующего релиза. - person Andreas Fabri; 03.04.2019