判断多边形为顺时针或者逆时针

CGAL的Polygon函数提供了判断多边形点序列顺序的函数，直接返回多边形是否为顺时针或者逆时针。

template<class Traits_P, class Container_P = std::vector<typename Traits_P::Point_2>>
Orientation CGAL::Polygon_2< Traits_P, Container_P >::orientation()	const

下面实现一个检测多边形的点序列顺序是否为逆时针，如果为非逆时针，则旋转点顺序为逆时针。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <list>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Point_2<K> Point;
typedef CGAL::Polygon_2<K> Polygon_2;
typedef Polygon_2::Vertex_iterator VertexIterator;
typedef Polygon_2::Edge_const_iterator EdgeIterator;

int main() {
  Polygon_2 outQ;
  outQ.push_back(Point_2 (250, 150));
  outQ.push_back(Point_2 (400, 150));
  outQ.push_back(Point_2 (400, 500));
  outQ.push_back(Point_2 (250, 500));
  if (outQ.orientation() != CGAL::COUNTERCLOCKWISE) {
      outQ.reverse_orientation();
  }

  return 0;
}

判断多边形是否为简单多边形

上述多边形点顺序检测需要一个先决条件：Polygon必须为简单多边形。什么是简单多边形，引用百度百科的解释如下：

定义一：周界不自交的多边形。

定义二：满足如下条件的多边形：

1）顶点与顶点不重合。

2）顶点不在边上。

定义三：边与边不相交的多边形。

Polygon也提供了检测多边形是否为简单多边形的方法。

bool is_simple () const

简单多边形又分为凸多边形和凹多边形。

bool is_convex () const

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;

int main() {
  Point points[] = { Point(0,0), Point(5.1,0), Point(1,1), Point(0.5,6)};
  Polygon_2 pgn(points, points+4);
  // check if the polygon is simple.
  std::cout << "The polygon is " <<
    (pgn.is_simple() ? "" : "not ") << "simple." << std::endl;
  // check if the polygon is convex
  std::cout << "The polygon is " <<
    (pgn.is_convex() ? "" : "not ") << "convex." << endl;
  return 0;
}

参考材料

https://doc.cgal.org/latest/Polygon/classCGAL_1_1Polygon__2.html

https://baike.baidu.com/item/%E7%AE%80%E5%8D%95%E5%A4%9A%E8%BE%B9%E5%BD%A2