ポリゴンの髭を取り除く

　標準に無い変形アルゴリズムを晒してみようと思います。

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 前方の要素検索位置
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] ２項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( pred( *first, *next ) )  return first;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 前方の要素検索位置
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist = std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next = first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next = last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( *first == *next )  return first;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 後方の要素検索位置
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_find_later(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] ２項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( pred( *first, *next ) )  return next;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 後方の要素検索位置
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_find_later(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( *first == *next )  return next;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の INTERVAL 要素間隔バージョン
    @retval イテレータ（要素検索位置）
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_rotate_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] ２項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER result  =  interval_adjacent_find( interval, first, last, pred );
    if( result != last )  return result;
    return interval_adjacent_find_later( dist - interval, first, last, pred );
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の INTERVAL 要素間隔バージョン
    @retval イテレータ（要素検索位置）
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_rotate_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER result  =  interval_adjacent_find( interval, first, last );
    if( result != last )  return result;
    return interval_adjacent_find_later( dist - interval, first, last );
  }

何に使うかというと、---ABA--- みたいな構成のポリゴンは、髭のように変な辺が飛び出しているので、それを消去するのに使います。--ABCBA--みたいなパターンもあるので、--ABA-- を消去しても油断できません。地道に再帰で消し去ります。

  //! 単純な連続重複があるか調べる
  /*!
    @retval true 重複あり
    @retval false 重複なし
  */
  template <typename T>
  bool check_duplicate( const vector<T>& sec ) {
    return (std::adjacent_find( sec.begin(), sec.end() ) != sec.end());
  }

  //! 単純な連続重複点を除去する
  /*!
    @note 先頭と末尾は連続としない
  */
  template <typename T>
  void deduce_duplicate( vector<T>& sec ) {
    vector<T>::iterator f  =  std::adjacent_find( sec.begin(), sec.end() );
    while( f != sec.end() ) {
      sec.erase( f );
      f  =  std::adjacent_find( sec.begin(), sec.end() );
    }
  }

  //! 単純な連続重複があるか調べる
  /*!
    @retval true 重複あり
    @retval false 重複なし
  */
  template <typename T>
  bool check_closed_duplicate( const vector<T>& sec ) {
    if( sec.size() < 3 )  throw std::exception();
    return check_duplicate( sec ) || (*(sec.begin()) == *(sec.rbegin()));
  }

  //! 単純な連続重複点を除去する
  /*!
    @note 先頭と末尾を連続とする
  */
  template <typename T>
  void deduce_closed_duplicate( vector<T>& sec ) {
    if( sec.size() < 3 )  throw std::exception();
    deduce_duplicate( sec );
    if( *(sec.begin()) == *(sec.rbegin()) )  sec.pop_back();
  }

  //! ABAタイプの無駄な尾を除去する
  /*!
    @note ポリラインに使用する
  */
  template <typename T>
  void deduce_tail( vector<T>& sec ) {
    vector<T>::iterator f  =    interval_adjacent_find( 2, sec.begin(), sec.end() );
    while( f != sec.end() ) {
      vector<T>::iterator g  =  f;
      ++g;  sec.erase( g );  sec.erase( f );
      f  =    interval_adjacent_find( 2, sec.begin(), sec.end() );
    }
  }

  //! ABAタイプの無駄な尾を除去する
  /*!
    @note ポリゴンに使用する
  */
  template <typename T>
  void deduce_closed_tail( vector<T>& sec ) {
    vector<T>::iterator f  =    interval_adjacent_rotate_find( 2, sec.begin(), sec.end() );
    while( f != sec.end() ) {
      vector<T>::iterator g  =  f;
      ++g;
      if( g == sec.end() ) {
        sec.erase( f );  sec.erase( sec.begin() );
      } else {
        sec.erase( g );  sec.erase( f );
      }
      f  =    interval_adjacent_rotate_find( 2, sec.begin(), sec.end() );
    }
  }

あんま、おもしろくないですかね。