poly_utils.h

Go to the documentation of this file.

#ifndef POLYGON_H
#define POLYGON_H

#include <data/types.h>
#include <poly/types.h>
#include <poly/triangulation.h>

#include <iterator>
#include <boost/unordered_map.hpp>

# define CGAL_HEADER_ONLY 1
# define CGAL_NO_GMP 1
//#define CGAL_NO_PRECONDITIONS 1
//#define CGAL_NO_POSTCONDITIONS 1
#include <CGAL/Polygon_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/partition_2.h>

namespace frechet { namespace poly {

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;

class CgalPoint: public CGAL::Point_2<Kernel>
{
public:
    typedef CGAL::Point_2<Kernel> super;
    int i;
    mutable bool erase;

    CgalPoint();

    CgalPoint(const QPointF& p, int i=-1);
    //
    CgalPoint(double x, double y, int i=-1);

    CgalPoint& operator= (const QPointF& p);

    operator QPointF() const;
};

struct PolygonTraits: public Kernel {
    typedef frechet::poly::CgalPoint Point_2;
};

typedef CGAL::Polygon_2<PolygonTraits> CgalPolygon;
typedef std::list<CgalPolygon> CgalPolygonList;

struct PartitionTraits: public CGAL::Partition_traits_2<PolygonTraits> {
    typedef frechet::poly::CgalPoint Point_2;
    typedef frechet::poly::CgalPolygon Polygon_2;
};

class PolygonUtilities
{
private:
    CgalPolygon cgp;
    CgalPolygonList convex;
public:
    enum DecompositionAlgorithm {
        APPROX_GREENE,  
        APPROX_HERTEL,  
        OPTIMAL_GREENE  
    };
public:
    PolygonUtilities();
    PolygonUtilities(const Curve& p);

    //bool is_closed() const;
    bool is_simple() const;
    bool is_convex() const;
    bool is_counter_clockwise();

    //int vertexes() const;
    //int edges() const;

    //void revert();

    //  @return numer of convex parts
    int decompose(DecompositionAlgorithm algo, bool verify);

    int partition(Partition& partition) const;

    int simplify();

    void findReflexVertices(Polygon& poly, double tolerance=0.0);

    //  erstellt ein Fan-Triangulierung mehrerer (konvexer!) Polygone
    void fanTriangulate(Triangulation& tri) const;


private:
    bool assertStrictlySorted(const CgalPolygon&);
    static bool create1Diagonal(int u, int v, int n, Partition& partition);

    bool simplify(CgalPolygon& poly);
    void fanTriangulate(const CgalPolygon& poly, Triangulation& tri) const;
    static bool is_reflex_vertex(const CgalPolygon::Vertex_circulator& p, double precision=0.0);
};

std::ostream& operator<< (std::ostream& out, const frechet::poly::CgalPolygon& poly);
std::ostream& operator<< (std::ostream& out, const frechet::poly::CgalPolygonList& polys);


}} //   namespace frechet::poly


#endif // POLYGON_H