CGAL AlphaShape2算法提取有序邊界

在檢視“CGAL AlphaShape算法提取有序邊界”相關部落格（例：https://blog.csdn.net/kw123472/article/details/122176426?spm=1001.2014.3001.5501）後發現很多人不知道怎麼從CGAL提取的邊界散點中提取按順序排列的邊界集合，進而導緻新增了“對無序散點進行有序排列”的算法需求，其實CGAL本身就提供了有序的先驗資訊；

官網執行個體代碼：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Alpha_shape_2.h>
#include <CGAL/Alpha_shape_vertex_base_2.h>
#include <CGAL/Alpha_shape_face_base_2.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/algorithm.h>
#include <fstream>
#include <iostream>
#include <list>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel  K;
typedef K::FT                                                FT;
typedef K::Point_2                                           Point;
typedef K::Segment_2                                         Segment;
typedef CGAL::Alpha_shape_vertex_base_2<K>                   Vb;
typedef CGAL::Alpha_shape_face_base_2<K>                     Fb;
typedef CGAL::Triangulation_data_structure_2<Vb,Fb>          Tds;
typedef CGAL::Delaunay_triangulation_2<K,Tds>                Triangulation_2;
typedef CGAL::Alpha_shape_2<Triangulation_2>                 Alpha_shape_2;
typedef Alpha_shape_2::Alpha_shape_edges_iterator            Alpha_shape_edges_iterator;
template <class OutputIterator>
void alpha_edges( const Alpha_shape_2& A, OutputIterator out)
{
  Alpha_shape_edges_iterator it = A.alpha_shape_edges_begin(),
                             end = A.alpha_shape_edges_end();
  for( ; it!=end; ++it)
    *out++ = A.segment(*it);
}
template <class OutputIterator>
bool file_input(OutputIterator out)
{
  std::ifstream is("data/fin", std::ios::in);
  if(is.fail())
  {
    std::cerr << "unable to open file for input" << std::endl;
    return false;
  }
  int n;
  is >> n;
  std::cout << "Reading " << n << " points from file" << std::endl;
  std::copy_n(std::istream_iterator<Point>(is), n, out);
  return true;
}
// Reads a list of points and returns a list of segments
// corresponding to the Alpha shape.
int main()
{
  std::list<Point> points;
  if(! file_input(std::back_inserter(points)))
    return -1;
  Alpha_shape_2 A(points.begin(), points.end(),
                  FT(10000),
                  Alpha_shape_2::GENERAL);
  std::vector<Segment> segments;
  alpha_edges(A, std::back_inserter(segments));
  std::cout << "Alpha Shape computed" << std::endl;
  std::cout << segments.size() << " alpha shape edges" << std::endl;
  std::cout << "Optimal alpha: " << *A.find_optimal_alpha(1)<<std::endl;
  return 0;
}
           

Alpha shape傳回的結果都存在segments這個集合裡面，通過觀察Segment結構體後會發現，這是一個線段，其中存在兩個點，線段起點和終點，其實邊界順序就已經知道了；

僞代碼如下：

struct point2{
double x;
double y;
}

std::vector<point2> hull;
std::vector<bool> bUse;
bUse.resize(segments.size(),false);
point2 lastPoint;
bool pair =true;
while(pair){
pair=false;
for(int =0;i<segments.size();i++){
if(bUse[i])continue;
point2 begin =point2(segments[i].vector(0).x,segments[i].vector(0).y);
point2 end =point2(segments[i].vector(1).x,segments[i].vector(1).y);
if(i==0){
bUse[i]=true;
hull.push_back(begin);
hull.push_back(end);
lastPoint =end;
pair =true;
break;
}
if(abs(begin.x-lastPoint.x)<0.00001&&abs(begin.y-lastPoint.y)<0.00001){
bUse[i]=true;
hull.push_back(end);
lastPoint =end;
pair =true;
break;
}
if(abs(end.x-lastPoint.x)<0.00001&&abs(end.y-lastPoint.y)<0.00001){
bUse[i]=true;
hull.push_back(begin);
lastPoint =begin;
pair =true;
break;
}
}
}
           

大緻意思就是周遊所有線段将首尾相連，最後得到的hull向量即有序的點集；（純手撸代碼，如有錯誤還望包涵）
           

再論“對無序散點進行有序排列”的算法，目前看到最多的是以下政策：

– 先計算所有點的重心，再計算每個點與重心點的極角，進行排序；

這樣做對凸多邊形有用，但是對于凹多邊形，用重心和頂點連線計算的正切值，貌似不一定是有序的！

例如"S"型點集，重心則在外部；

若有好的方法希望不吝賜教；