//Copyright (c) 2018 Ultimaker B.V.
//CuraEngine is released under the terms of the AGPLv3 or higher.

#ifndef CX_UTILS_POLYGON_H
#define CX_UTILS_POLYGON_H

#include <vector>
#include <assert.h>
#include <float.h>
#include <fstream>

#include <algorithm>    // std::reverse, fill_n array
#include <limits> // int64_t.min
#include <list>

#include <initializer_list>

#include "internal/polygon/intpoint.h"
#include "internal/polygon/angledegrees.h"
#include "ccglobal/tracer.h"

#define CHECK_POLY_ACCESS
#ifdef CHECK_POLY_ACCESS
#define POLY_ASSERT(e) assert(e)
#else
#define POLY_ASSERT(e) do {} while(0)
#endif

namespace topomesh
{
    class PartsView;
    class Polygons;
    class Polygon;
    class PolygonRef;

    class ListPolyIt;

    typedef std::list<Point> ListPolygon; //!< A polygon represented by a linked list instead of a vector
    typedef std::vector<ListPolygon> ListPolygons; //!< Polygons represented by a vector of linked lists instead of a vector of vectors

    const static int clipper_init = (0);
    #define NO_INDEX (std::numeric_limits<unsigned int>::max())

    class ConstPolygonPointer;

    /*!
     * Outer polygons should be counter-clockwise,
     * inner hole polygons should be clockwise.
     * (When negative X is to the left and negative Y is downward.)
     */
    class ConstPolygonRef
    {
        friend class Polygons;
        friend class Polygon;
        friend class PolygonRef;
        friend class ConstPolygonPointer;
    protected:
        ClipperLib::Path* path;
    public:
        ConstPolygonRef(const ClipperLib::Path& polygon)
        : path(const_cast<ClipperLib::Path*>(&polygon))
        {}

        virtual ~ConstPolygonRef()
        {
        }

        bool operator==(ConstPolygonRef& other) const =delete; // polygon comparison is expensive and probably not what you want when you use the equality operator

        ConstPolygonRef& operator=(const ConstPolygonRef& other) =delete; // Cannot assign to a const object

        /*!
         * Gets the number of vertices in this polygon.
         * \return The number of vertices in this polygon.
         */
        size_t size() const;

        /*!
         * Returns whether there are any vertices in this polygon.
         * \return ``true`` if the polygon has no vertices at all, or ``false`` if
         * it does have vertices.
         */
        bool empty() const;

        const Point& operator[] (unsigned int index) const
        {
            POLY_ASSERT(index < size());
            return (*path)[index];
        }

        const ClipperLib::Path& operator*() const
        {
            return *path;
        }

        ClipperLib::Path::const_iterator begin() const
        {
            return path->begin();
        }

        ClipperLib::Path::const_iterator end() const
        {
            return path->end();
        }

        ClipperLib::Path::const_reference back() const
        {
            return path->back();
        }

        const void* data() const
        {
            return path->data();
        }


        /*!
         * On Y-axis positive upward displays, Orientation will return true if the polygon's orientation is counter-clockwise.
         *
         * from http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Functions/Orientation.htm
         */
        bool orientation() const
        {
            return ClipperLib::Orientation(*path);
        }

        Polygons offset(int distance, ClipperLib::JoinType joinType = ClipperLib::jtMiter, double miter_limit = 1.2) const;

        int64_t polygonLength() const
        {
            int64_t length = 0;
            Point p0 = (*path)[path->size()-1];
            for(unsigned int n=0; n<path->size(); n++)
            {
                Point p1 = (*path)[n];
                length += vSize(p0 - p1);
                p0 = p1;
            }
            return length;
        }

        bool shorterThan(const coord_t check_length) const;

        Point _min() const
        {
            Point ret = Point(POINT_MAX, POINT_MAX);
            for(Point p : *path)
            {
                ret.X = std::min(ret.X, p.X);
                ret.Y = std::min(ret.Y, p.Y);
            }
            return ret;
        }

        Point _max() const
        {
            Point ret = Point(POINT_MIN, POINT_MIN);
            for(Point p : *path)
            {
                ret.X = std::max(ret.X, p.X);
                ret.Y = std::max(ret.Y, p.Y);
            }
            return ret;
        }

        double area() const
        {
            return ClipperLib::Area(*path);
        }

        Point centerOfMass() const
        {
            double x = 0, y = 0;
            Point p0 = (*path)[path->size()-1];
            for(unsigned int n=0; n<path->size(); n++)
            {
                Point p1 = (*path)[n];
                double second_factor = (p0.X * p1.Y) - (p1.X * p0.Y);

                x += double(p0.X + p1.X) * second_factor;
                y += double(p0.Y + p1.Y) * second_factor;
                p0 = p1;
            }

            double area = Area(*path);

            x = x / 6 / area;
            y = y / 6 / area;

            return Point(x, y);
        }

        Point closestPointTo(Point p) const
        {
            Point ret = p;
            float bestDist = FLT_MAX;
            for(unsigned int n=0; n<path->size(); n++)
            {
                float dist = vSize2f(p - (*path)[n]);
                if (dist < bestDist)
                {
                    ret = (*path)[n];
                    bestDist = dist;
                }
            }
            return ret;
        }

        /*!
         * Check if we are inside the polygon. We do this by tracing from the point towards the positive X direction,
         * every line we cross increments the crossings counter. If we have an even number of crossings then we are not inside the polygon.
         * Care needs to be taken, if p.Y exactly matches a vertex to the right of p, then we need to count 1 intersect if the
         * outline passes vertically past; and 0 (or 2) intersections if that point on the outline is a 'top' or 'bottom' vertex.
         * The easiest way to do this is to break out two cases for increasing and decreasing Y ( from p0 to p1 ).
         * A segment is tested if pa.Y <= p.Y < pb.Y, where pa and pb are the points (from p0,p1) with smallest & largest Y.
         * When both have the same Y, no intersections are counted but there is a special test to see if the point falls
         * exactly on the line.
         * 
         * Returns false if outside, true if inside; if the point lies exactly on the border, will return 'border_result'.
         * 
         * \deprecated This function is no longer used, since the Clipper function is used by the function PolygonRef::inside(.)
         * 
         * \param p The point for which to check if it is inside this polygon
         * \param border_result What to return when the point is exactly on the border
         * \return Whether the point \p p is inside this polygon (or \p border_result when it is on the border)
         */
        bool _inside(Point p, bool border_result = false) const;

        /*!
         * Clipper function.
         * Returns false if outside, true if inside; if the point lies exactly on the border, will return 'border_result'.
         * 
         * http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Functions/PointInPolygon.htm
         */
        bool inside(Point p, bool border_result = false) const
        {
            int res = ClipperLib::PointInPolygon(p, *path);
            if (res == -1)
            {
                return border_result;
            }
            return res == 1;
        }

        /*!
         * Smooth out small perpendicular segments and store the result in \p result.
         * Smoothing is performed by removing the inner most vertex of a line segment smaller than \p remove_length
         * which has an angle with the next and previous line segment smaller than roughly 150*
         * 
         * Note that in its current implementation this function doesn't remove line segments with an angle smaller than 30*
         * Such would be the case for an N shape.
         * 
         * \param remove_length The length of the largest segment removed
         * \param result (output) The result polygon, assumed to be empty
         */
        void smooth(int remove_length, PolygonRef result) const;

        /*!
         * Smooth out sharp inner corners, by taking a shortcut which bypasses the corner
         * 
         * \param angle The maximum angle of inner corners to be smoothed out
         * \param shortcut_length The desired length of the shortcut line segment introduced (shorter shortcuts may be unavoidable)
         * \param result The resulting polygon
         */
        void smooth_outward(const AngleDegrees angle, int shortcut_length, PolygonRef result) const;

        /*!
         * Smooth out the polygon and store the result in \p result.
         * Smoothing is performed by removing vertices for which both connected line segments are smaller than \p remove_length
         * 
         * \param remove_length The length of the largest segment removed
         * \param result (output) The result polygon, assumed to be empty
         */
        void smooth2(int remove_length, PolygonRef result) const;

        /*!
         * Compute the morphological intersection between this polygon and another.
         *
         * Note that the result may consist of multiple polygons, if you have bad
         * luck.
         *
         * \param other The polygon with which to intersect this polygon.
         */
        Polygons intersection(const ConstPolygonRef& other) const;


    private:
        /*!
         * Smooth out a simple corner consisting of two linesegments.
         * 
         * Auxiliary function for \ref smooth_outward
         * 
         * \param p0 The point before the corner
         * \param p1 The corner
         * \param p2 The point after the corner
         * \param p0_it Iterator to the point before the corner
         * \param p1_it Iterator to the corner
         * \param p2_it Iterator to the point after the corner
         * \param v10 Vector from \p p1 to \p p0
         * \param v12 Vector from \p p1 to \p p2
         * \param v02 Vector from \p p0 to \p p2
         * \param shortcut_length The desired length ofthe shortcutting line
         * \param cos_angle The cosine on the angle in L 012
         */
        static void smooth_corner_simple(const Point p0, const Point p1, const Point p2, const ListPolyIt p0_it, const ListPolyIt p1_it, const ListPolyIt p2_it, const Point v10, const Point v12, const Point v02, const int64_t shortcut_length, float cos_angle);

	 /*!
         * Smooth out a complex corner where the shortcut bypasses more than two line segments
         * 
         * Auxiliary function for \ref smooth_outward
         * 
         * \warning This function might try to remove the whole polygon
         * Error code -1 means the whole polygon should be removed (which means it is a hole polygon)
         * 
         * \param p1 The corner point
         * \param[in,out] p0_it Iterator to the last point checked before \p p1 to consider cutting off
         * \param[in,out] p2_it Iterator to the last point checked after \p p1 to consider cutting off
         * \param shortcut_length The desired length ofthe shortcutting line
         * \return Whether this whole polygon whould be removed by the smoothing
         */
        static bool smooth_corner_complex(const Point p1, ListPolyIt& p0_it, ListPolyIt& p2_it, const int64_t shortcut_length);

        /*!
         * Try to take a step away from the corner point in order to take a bigger shortcut.
         * 
         * Try to take the shortcut from a place as far away from the corner as the place we are taking the shortcut to.
         * 
         * Auxiliary function for \ref smooth_outward
         * 
         * \param[in] p1 The corner point
         * \param[in] shortcut_length2 The square of the desired length ofthe shortcutting line
         * \param[in,out] p0_it Iterator to the previously checked point somewhere beyond \p p1. Updated for the next iteration.
         * \param[in,out] p2_it Iterator to the previously checked point somewhere before \p p1. Updated for the next iteration.
         * \param[in,out] forward_is_blocked Whether trying another step forward is blocked by the smoothing outward condition. Updated for the next iteration.
         * \param[in,out] backward_is_blocked Whether trying another step backward is blocked by the smoothing outward condition. Updated for the next iteration.
         * \param[in,out] forward_is_too_far Whether trying another step forward is blocked by the shortcut length condition. Updated for the next iteration.
         * \param[in,out] backward_is_too_far Whether trying another step backward is blocked by the shortcut length condition. Updated for the next iteration.
         */
        static void smooth_outward_step(const Point p1, const int64_t shortcut_length2, ListPolyIt& p0_it, ListPolyIt& p2_it, bool& forward_is_blocked, bool& backward_is_blocked, bool& forward_is_too_far, bool& backward_is_too_far);
    };


    class PolygonPointer;

    class PolygonRef : public ConstPolygonRef
    {
        friend class PolygonPointer;
    public:
        PolygonRef(ClipperLib::Path& polygon)
        : ConstPolygonRef(polygon)
        {}

        PolygonRef(const PolygonRef& other)
        : ConstPolygonRef(*other.path)
        {}

        virtual ~PolygonRef()
        {
        }

        void reserve(size_t min_size)
        {
            path->reserve(min_size);
        }

        PolygonRef& operator=(const ConstPolygonRef& other) =delete; // polygon assignment is expensive and probably not what you want when you use the assignment operator

        PolygonRef& operator=(ConstPolygonRef& other) =delete; // polygon assignment is expensive and probably not what you want when you use the assignment operator
    //     { path = other.path; return *this; }

        PolygonRef& operator=(PolygonRef&& other)
        {
            *path = std::move(*other.path);
            return *this;
        }

        Point& operator[] (unsigned int index)
        {
            POLY_ASSERT(index < size());
            return (*path)[index];
        }

        ClipperLib::Path::iterator begin()
        {
            return path->begin();
        }

        ClipperLib::Path::iterator end()
        {
            return path->end();
        }

        ClipperLib::Path::reference back()
        {
            return path->back();
        }

        void* data()
        {
            return path->data();
        }

        void add(const Point p)
        {
            path->push_back(p);
        }

        ClipperLib::Path& operator*()
        {
            return *path;
        }

        template <typename... Args>
        void emplace_back(Args&&... args)
        {
            path->emplace_back(args...);
        }

        void remove(unsigned int index)
        {
            POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max()));
            path->erase(path->begin() + index);
        }

        void clear()
        {
            path->clear();
        }

        void reverse()
        {
            ClipperLib::ReversePath(*path);
        }

        /*!
         * Translate the whole polygon in some direction.
         * 
         * \param translation The direction in which to move the polygon
         */
        void translate(Point translation)
        {
            for (Point& p : *this)
            {
                p += translation;
            }
        }

        /*! 
         * Removes consecutive line segments with same orientation and changes this polygon.
         * 
         * Removes verts which are connected to line segments which are both too small.
         * Removes verts which detour from a direct line from the previous and next vert by a too small amount.
         *
         * Criteria:
         * 1. Never remove a vertex if either of the connceted segments is larger than \p smallest_line_segment
         * 2. Never remove a vertex if the distance between that vertex and the final resulting polygon would be higher than \p allowed_error_distance
         * 3. Simplify uses a heuristic and doesn't neccesarily remove all removable vertices under the above criteria.
         * 4. But simplify may never violate these criteria.
         * 5. Unless the segments or the distance is smaller than the rounding error of 5 micron
         * 
         * \param smallest_line_segment_squared maximal squared length of removed line segments
         * \param allowed_error_distance_squared The square of the distance of the middle point to the line segment of the consecutive and previous point for which the middle point is removed
         */
        void simplify(const coord_t smallest_line_segment_squared = 100, const coord_t allowed_error_distance_squared = 25);

        void pop_back()
        { 
            path->pop_back();
        }

        /*!
         * Apply a matrix to each vertex in this polygon
         */
        void applyMatrix(const PointMatrix& matrix);
        void applyMatrix(const Point3Matrix& matrix);
    };

    class ConstPolygonPointer
    {
    protected:
        const ClipperLib::Path* path;
    public:
        ConstPolygonPointer()
        : path(nullptr)
        {}
        ConstPolygonPointer(const ConstPolygonRef* ref)
        : path(ref->path)
        {}
        ConstPolygonPointer(const ConstPolygonRef& ref)
        : path(ref.path)
        {}

        ConstPolygonRef operator*() const
        {
            assert(path);
            return ConstPolygonRef(*path);
        }
        const ClipperLib::Path* operator->() const
        {
            assert(path);
            return path;
        }

        operator bool() const
        {
            return path;
        }

        bool operator==(const ConstPolygonPointer& rhs)
        {
            return path == rhs.path;
        }
    };

    class PolygonPointer
    {
    protected:
        ClipperLib::Path* path;
    public:
        PolygonPointer()
        : path(nullptr)
        {}
        PolygonPointer(PolygonRef* ref)
        : path(ref->path)
        {}

        PolygonPointer(PolygonRef& ref)
        : path(ref.path)
        {}

        PolygonRef operator*()
        {
            assert(path);
            return PolygonRef(*path);
        }
        ClipperLib::Path* operator->()
        {
            assert(path);
            return path;
        }

        operator bool() const
        {
            return path;
        }
    };

    class Polygon : public PolygonRef
    {
        ClipperLib::Path poly;
    public:
        Polygon()
        : PolygonRef(poly)
        {
        }

        Polygon(const ConstPolygonRef& other)
        : PolygonRef(poly)
        , poly(*other.path)
        {
        }

        Polygon(const Polygon& other)
        : PolygonRef(poly)
        , poly(*other.path)
        {
        }

        Polygon(Polygon&& moved)
        : PolygonRef(poly)
        , poly(std::move(moved.poly))
        {
        }

        virtual ~Polygon()
        {
        }

        Polygon& operator=(const ConstPolygonRef& other) = delete; // copying a single polygon is generally not what you want
    //     {
    //         path = other.path;
    //         poly = *other.path;
    //         return *this;
    //     }

        Polygon& operator=(Polygon&& other) //!< move assignment
        {
            poly = std::move(other.poly);
            return *this;
        }
    };

    class PolygonsPart;

    class Polygons
    {
        friend class Polygon;
        friend class PolygonRef;
        friend class ConstPolygonRef;
    public:
        ClipperLib::Paths paths;
    public:
        void save(std::fstream& out) const;
        void load(std::fstream& in);

        unsigned int size() const
        {
            return paths.size();
        }

		ClipperLib::Paths getPaths()
		{
			return paths;
		}

		void setPaths(ClipperLib::Paths _paths)
		{
			paths = _paths;
		}

        void CleanPaths()
        {
            ClipperLib::CleanPolygons(paths);
        }

        /*!
         * Convenience function to check if the polygon has no points.
         *
         * \return `true` if the polygon has no points, or `false` if it does.
         */
        bool empty() const;

        unsigned int pointCount() const; //!< Return the amount of points in all polygons

        PolygonRef operator[] (unsigned int index)
        {
            POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max()));
            return paths[index];
        }
        ConstPolygonRef operator[] (unsigned int index) const
        {
            POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max()));
            return paths[index];
        }
        ClipperLib::Paths::iterator begin()
        {
            return paths.begin();
        }
        ClipperLib::Paths::const_iterator begin() const
        {
            return paths.begin();
        }
        ClipperLib::Paths::iterator end()
        {
            return paths.end();
        }
        ClipperLib::Paths::const_iterator end() const
        {
            return paths.end();
        }
        /*!
         * Remove a polygon from the list and move the last polygon to its place
         * 
         * \warning changes the order of the polygons!
         */
        void remove(unsigned int index)
        {
            POLY_ASSERT(index < size() && index <= static_cast<unsigned int>(std::numeric_limits<int>::max()));
            if (index < paths.size() - 1)
            {
                paths[index] = std::move(paths.back());
            }
            paths.resize(paths.size() - 1);
        }
        /*!
         * Remove a range of polygons
         */
        void erase(ClipperLib::Paths::iterator start, ClipperLib::Paths::iterator end)
        {
            paths.erase(start, end);
        }
        void clear()
        {
            paths.clear();
        }
        void deletePaths()
        {
	        ClipperLib::Paths empty;	
            paths.swap(empty);
        }
        void add(ConstPolygonRef& poly)
        {
            paths.push_back(*poly.path);
        }
        void add(const ConstPolygonRef& poly)
        {
            paths.push_back(*poly.path);
        }
        void add(Polygon&& other_poly)
        {
            paths.emplace_back(std::move(*other_poly));
        }
        void add(const Polygons& other)
        {
            std::copy(other.paths.begin(), other.paths.end(), std::back_inserter(paths));
        }
        /*!
         * Add a 'polygon' consisting of two points
         */
        void addLine(const Point from, const Point to)
        {
            paths.emplace_back(ClipperLib::Path{from, to});
        }

        template<typename... Args>
        void emplace_back(Args... args)
        {
            paths.emplace_back(args...);
        }

        PolygonRef newPoly()
        {
            paths.emplace_back();
            return PolygonRef(paths.back());
        }
        PolygonRef back()
        {
            return PolygonRef(paths.back());
        }
        ConstPolygonRef back() const
        {
            return ConstPolygonRef(paths.back());
        }

        Polygons() {}

        Polygons(const Polygons& other) { paths = other.paths; }
        Polygons(Polygons&& other) { paths = std::move(other.paths); }
        Polygons& operator=(const Polygons& other) { paths = other.paths; return *this; }
        Polygons& operator=(Polygons&& other) { paths = std::move(other.paths); return *this; }

        bool operator==(const Polygons& other) const =delete;

        /*!
         * Convert ClipperLib::PolyTree to a Polygons object,
         * which uses ClipperLib::Paths instead of ClipperLib::PolyTree
         */
        static Polygons toPolygons(ClipperLib::PolyTree& poly_tree);

        Polygons difference(const Polygons& other) const
        {
            Polygons ret;
            ClipperLib::Clipper clipper(clipper_init);
            clipper.AddPaths(paths, ClipperLib::ptSubject, true);
            clipper.AddPaths(other.paths, ClipperLib::ptClip, true);
            clipper.Execute(ClipperLib::ctDifference, ret.paths);
            return ret;
        }
        Polygons unionPolygons(const Polygons& other) const
        {
            Polygons ret;
            ClipperLib::Clipper clipper(clipper_init);
            clipper.AddPaths(paths, ClipperLib::ptSubject, true);
            clipper.AddPaths(other.paths, ClipperLib::ptSubject, true);
            clipper.Execute(ClipperLib::ctUnion, ret.paths, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
            return ret;
        }
        void optimize(const int maxPath)
        {
            size_t size = paths.size();
            if (size > maxPath)
            {
                ClipperLib::Clipper clipper(clipper_init);

                for (size_t i = 0; i < size; ++i)
                {
                    if (i == 0)
                        clipper.AddPath(paths.at(i), ClipperLib::ptClip, true);
                    else
                        clipper.AddPath(paths.at(i), ClipperLib::ptSubject, true);
                }
                clipper.Execute(ClipperLib::ctUnion, paths, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
            }
        }

        /*!
         * Union all polygons with each other (When polygons.add(polygon) has been called for overlapping polygons)
         */
        Polygons unionPolygons() const
        {
            return unionPolygons(Polygons());
        }
        Polygons intersection(const Polygons& other) const
        {
            Polygons ret;
            ClipperLib::Clipper clipper(clipper_init);
            clipper.AddPaths(paths, ClipperLib::ptSubject, true);
            clipper.AddPaths(other.paths, ClipperLib::ptClip, true);
            clipper.Execute(ClipperLib::ctIntersection, ret.paths);
            return ret;
        }

        /*!
         * Intersect polylines with this area Polygons object.
         */
        Polygons intersectionPolyLines(const Polygons& polylines) const;

        /*!
         * Clips input line segments by this Polygons.
         * \param other Input line segments to be cropped
         * \param segment_tree the resulting interior line segments
         */
        void lineSegmentIntersection(const Polygons& other, ClipperLib::PolyTree& segment_tree) const
        {
            ClipperLib::Clipper clipper(clipper_init);
            clipper.AddPaths(paths, ClipperLib::ptClip, true);
            clipper.AddPaths(other.paths, ClipperLib::ptSubject, false);
            clipper.Execute(ClipperLib::ctIntersection, segment_tree);
        }
        Polygons xorPolygons(const Polygons& other) const
        {
            Polygons ret;
            ClipperLib::Clipper clipper(clipper_init);
            clipper.AddPaths(paths, ClipperLib::ptSubject, true);
            clipper.AddPaths(other.paths, ClipperLib::ptClip, true);
            clipper.Execute(ClipperLib::ctXor, ret.paths);
            return ret;
        }

        Polygons offset(int distance, ClipperLib::JoinType joinType = ClipperLib::jtMiter, double miter_limit = 1.2) const;

        Polygons offsetPolyLine(int distance, ClipperLib::JoinType joinType = ClipperLib::jtMiter) const
        {
            Polygons ret;
            double miterLimit = 1.2;
            ClipperLib::ClipperOffset clipper(miterLimit, 10.0);
            clipper.AddPaths(paths, joinType, ClipperLib::etOpenSquare);
            clipper.MiterLimit = miterLimit;
            clipper.Execute(ret.paths, distance);
            return ret;
        }
    
        /*!
         * Check if we are inside the polygon.
         * 
         * We do this by counting the number of polygons inside which this point lies.
         * An odd number is inside, while an even number is outside.
         * 
         * Returns false if outside, true if inside; if the point lies exactly on the border, will return \p border_result.
         * 
         * \param p The point for which to check if it is inside this polygon
         * \param border_result What to return when the point is exactly on the border
         * \return Whether the point \p p is inside this polygon (or \p border_result when it is on the border)
         */
        bool inside(Point p, bool border_result = false) const;

        /*!
         * Check if we are inside the polygon. We do this by tracing from the point towards the positive X direction,
         * every line we cross increments the crossings counter. If we have an even number of crossings then we are not inside the polygon.
         * Care needs to be taken, if p.Y exactly matches a vertex to the right of p, then we need to count 1 intersect if the
         * outline passes vertically past; and 0 (or 2) intersections if that point on the outline is a 'top' or 'bottom' vertex.
         * The easiest way to do this is to break out two cases for increasing and decreasing Y ( from p0 to p1 ).
         * A segment is tested if pa.Y <= p.Y < pb.Y, where pa and pb are the points (from p0,p1) with smallest & largest Y.
         * When both have the same Y, no intersections are counted but there is a special test to see if the point falls
         * exactly on the line.
         * 
         * Returns false if outside, true if inside; if the point lies exactly on the border, will return \p border_result.
         * 
         * \deprecated This function is old and no longer used. instead use \ref Polygons::inside
         * 
         * \param p The point for which to check if it is inside this polygon
         * \param border_result What to return when the point is exactly on the border
         * \return Whether the point \p p is inside this polygon (or \p border_result when it is on the border)
         */
        bool insideOld(Point p, bool border_result = false) const;
    
        /*!
         * Find the polygon inside which point \p p resides. 
         * 
         * We do this by tracing from the point towards the positive X direction,
         * every line we cross increments the crossings counter. If we have an even number of crossings then we are not inside the polygon.
         * We then find the polygon with an uneven number of crossings which is closest to \p p.
         * 
         * If \p border_result, we return the first polygon which is exactly on \p p.
         * 
         * \param p The point for which to check in which polygon it is.
         * \param border_result Whether a point exactly on a polygon counts as inside
         * \return The index of the polygon inside which the point \p p resides
         */
        unsigned int findInside(Point p, bool border_result = false);
    
        /*!
         * Approximates the convex hull of the polygons.
         * \p extra_outset Extra offset outward
         * \return the convex hull (approximately)
         * 
         */
        Polygons approxConvexHull(int extra_outset = 0);

        /*!
         * Compute the area enclosed within the polygons (minus holes)
         * 
         * \return The area in square micron
         */
        double area() const;

        /*!
         * Smooth out small perpendicular segments
         * Smoothing is performed by removing the inner most vertex of a line segment smaller than \p remove_length
         * which has an angle with the next and previous line segment smaller than roughly 150*
         * 
         * Note that in its current implementation this function doesn't remove line segments with an angle smaller than 30*
         * Such would be the case for an N shape.
         * 
         * \param remove_length The length of the largest segment removed
         * \return The smoothed polygon
         */
        Polygons smooth(int remove_length) const;

        /*!
         * Smooth out sharp inner corners, by taking a shortcut which bypasses the corner
         * 
         * \param angle The maximum angle of inner corners to be smoothed out
         * \param shortcut_length The desired length of the shortcut line segment introduced (shorter shortcuts may be unavoidable)
         * \return The resulting polygons
         */
        Polygons smooth_outward(const AngleDegrees angle, int shortcut_length);

        Polygons smooth2(int remove_length, int min_area) const; //!< removes points connected to small lines
    
        /*!
         * Removes vertices of the polygons to make sure that they are not too high
         * resolution.
         *
         * This removes points which are connected to line segments that are shorter
         * than the `smallest_line_segment`, unless that would introduce a deviation
         * in the contour of more than `allowed_error_distance`.
         *
         * Criteria:
         * 1. Never remove a vertex if either of the connceted segments is larger than \p smallest_line_segment
         * 2. Never remove a vertex if the distance between that vertex and the final resulting polygon would be higher than \p allowed_error_distance
         * 3. Simplify uses a heuristic and doesn't neccesarily remove all removable vertices under the above criteria.
         * 4. But simplify may never violate these criteria.
         * 5. Unless the segments or the distance is smaller than the rounding error of 5 micron
         * 
         * Vertices which introduce an error of less than 5 microns are removed
         * anyway, even if the segments are longer than the smallest line segment.
         * This makes sure that (practically) colinear line segments are joined into
         * a single line segment.
         * \param smallest_line_segment Maximal length of removed line segments.
         * \param allowed_error_distance If removing a vertex introduces a deviation
         * from the original path that is more than this distance, the vertex may
         * not be removed.
         */
        void simplify(const coord_t smallest_line_segment = 10, const coord_t allowed_error_distance = 5) 
        {
            const coord_t allowed_error_distance_squared = allowed_error_distance * allowed_error_distance;
            const coord_t smallest_line_segment_squared = smallest_line_segment * smallest_line_segment;
            Polygons& thiss = *this;
            for (size_t p = 0; p < size(); p++)
            {
                thiss[p].simplify(smallest_line_segment_squared, allowed_error_distance_squared);
                if (thiss[p].size() < 3)
                {
                    remove(p);
                    p--;
                }
            }
        }

        /*!
         * Remove all but the polygons on the very outside.
         * Exclude holes and parts within holes.
         * \return the resulting polygons.
         */
        Polygons getOutsidePolygons() const;

        /*!
         * Exclude holes which have no parts inside of them.
         * \return the resulting polygons.
         */
        Polygons removeEmptyHoles() const;

        /*!
         * Return hole polygons which have no parts inside of them.
         * \return the resulting polygons.
         */
        Polygons getEmptyHoles() const;

		/*!
	 *   Save the path of the Polygons to File.
	 */
		bool saveToLocalFile(const char* filename, double scale);
		bool  loadFromLocalFile(const char* filename, double scale);

		/*!
		 * Split up the polygons into groups according to the even-odd rule.
		 * Each PolygonsPart in the result has an outline as first polygon, whereas the rest are holes.
		 */
		std::vector<PolygonsPart> splitIntoParts(bool unionAll = false) const;

        ClipperLib::PolyTree* splitIntoPolyTree(bool unionAll = false) const;

    
    private:
        /*!
         * recursive part of \ref Polygons::removeEmptyHoles and \ref Polygons::getEmptyHoles
         * \param node The node of the polygons part to process
         * \param remove_holes Whether to remove empty holes or everything but the empty holes
         * \param ret Where to store polygons which are not empty holes
         */
        void removeEmptyHoles_processPolyTreeNode(const ClipperLib::PolyNode& node, const bool remove_holes, Polygons& ret) const;
        void splitIntoParts_processPolyTreeNode(ClipperLib::PolyNode* node, std::vector<PolygonsPart>& ret) const;

        /*!
         * Convert a node from a ClipperLib::PolyTree and add it to a Polygons object,
         * which uses ClipperLib::Paths instead of ClipperLib::PolyTree
         */
        void addPolyTreeNodeRecursive(const ClipperLib::PolyNode& node);
    public:
        /*!
         * Split up the polygons into groups according to the even-odd rule.
         * Each vector in the result has the index to an outline as first index, whereas the rest are indices to holes.
         * 
         * \warning Note that this function reorders the polygons!
         */
        PartsView splitIntoPartsView(bool unionAll = false);
    private:
        void splitIntoPartsView_processPolyTreeNode(PartsView& partsView, Polygons& reordered, ClipperLib::PolyNode* node) const;
    public:
        /*!
         * Removes polygons with area smaller than \p min_area_size (note that min_area_size is in mm^2, not in micron^2).
         * Unless \p remove_holes is true, holes are not removed even if their area is below \p min_area_size.
         * However, holes that are contained within outlines whose area is below the threshold are removed though.
         */
        void removeSmallAreas(const double min_area_size, const bool remove_holes = false);

        /*!
         * Removes overlapping consecutive line segments which don't delimit a positive area.
         */
        void removeDegenerateVerts()
        {
            Polygons& thiss = *this;
            for (unsigned int poly_idx = 0; poly_idx < size(); poly_idx++)
            {
                PolygonRef poly = thiss[poly_idx];
                Polygon result;
            
                auto isDegenerate = [](Point& last, Point& now, Point& next)
                {
                    Point last_line = now - last;
                    Point next_line = next - now;
                    return dot(last_line, next_line) == -1 * vSize(last_line) * vSize(next_line);
                };
                bool isChanged = false;
                for (unsigned int idx = 0; idx < poly.size(); idx++)
                {
                    Point& last = (result.size() == 0) ? poly.back() : result.back();
                    if (idx+1 == poly.size() && result.size() == 0) { break; }
                    Point& next = (idx+1 == poly.size())? result[0] : poly[idx+1];
                    if ( isDegenerate(last, poly[idx], next) )
                    { // lines are in the opposite direction
                        // don't add vert to the result
                        isChanged = true;
                        while (result.size() > 1 && isDegenerate(result[result.size()-2], result.back(), next) )
                        {
                            result.pop_back();
                        }
                    }
                    else 
                    {
                        result.add(poly[idx]);
                    }
                }
            
                if (isChanged)
                {
                    if (result.size() > 2) 
                    {   
                        *poly = *result;
                    }
                    else 
                    {
                        thiss.remove(poly_idx);
                        poly_idx--; // effectively the next iteration has the same poly_idx (referring to a new poly which is not yet processed)
                    }
                }
            }
        }
        /*!
         * Removes the same polygons from this set (and also empty polygons).
         * Polygons are considered the same if all points lie within [same_distance] of their counterparts.
         */
        Polygons remove(const Polygons& to_be_removed, int same_distance = 0) const
        {
            Polygons result;
            for (unsigned int poly_keep_idx = 0; poly_keep_idx < size(); poly_keep_idx++)
            {
                ConstPolygonRef poly_keep = (*this)[poly_keep_idx];
                bool should_be_removed = false;
                if (poly_keep.size() > 0) 
    //             for (int hole_poly_idx = 0; hole_poly_idx < to_be_removed.size(); hole_poly_idx++)
                for (ConstPolygonRef poly_rem : to_be_removed)
                {
    //                 PolygonRef poly_rem = to_be_removed[hole_poly_idx];
                    if (poly_rem.size() != poly_keep.size() || poly_rem.size() == 0) continue;
                
                    // find closest point, supposing this point aligns the two shapes in the best way
                    int closest_point_idx = 0;
                    int smallestDist2 = -1;
                    for (unsigned int point_rem_idx = 0; point_rem_idx < poly_rem.size(); point_rem_idx++)
                    {
                        int dist2 = vSize2(poly_rem[point_rem_idx] - poly_keep[0]);
                        if (dist2 < smallestDist2 || smallestDist2 < 0)
                        {
                            smallestDist2 = dist2;
                            closest_point_idx = point_rem_idx;
                        }
                    }
                    bool poly_rem_is_poly_keep = true;
                    // compare the two polygons on all points
                    if (smallestDist2 > same_distance * same_distance)
                        continue;
                    for (unsigned int point_idx = 0; point_idx < poly_rem.size(); point_idx++)
                    {
                        int dist2 = vSize2(poly_rem[(closest_point_idx + point_idx) % poly_rem.size()] - poly_keep[point_idx]);
                        if (dist2 > same_distance * same_distance)
                        {
                            poly_rem_is_poly_keep = false;
                            break;
                        }
                    }
                    if (poly_rem_is_poly_keep)
                    {
                        should_be_removed = true;
                        break;
                    }
                }
                if (!should_be_removed)
                    result.add(poly_keep);
            
            }
            return result;
        }

        Polygons processEvenOdd() const
        {
            Polygons ret;
            ClipperLib::Clipper clipper(clipper_init);
            clipper.AddPaths(paths, ClipperLib::ptSubject, true);
            clipper.Execute(ClipperLib::ctUnion, ret.paths);
            return ret;
        }

        coord_t polygonLength() const
        {
            coord_t length = 0;
            for(unsigned int i=0; i<paths.size(); i++)
            {
                Point p0 = paths[i][paths[i].size()-1];
                for(unsigned int n=0; n<paths[i].size(); n++)
                {
                    Point p1 = paths[i][n];
                    length += vSize(p0 - p1);
                    p0 = p1;
                }
            }
            return length;
        }

        coord_t polyLineLength() const;
    
        Point min() const
        {
            Point ret = Point(POINT_MAX, POINT_MAX);
            for(const ClipperLib::Path& polygon : paths)
            {
                for(Point p : polygon)
                {
                    ret.X = std::min(ret.X, p.X);
                    ret.Y = std::min(ret.Y, p.Y);
                }
            }
            return ret;
        }
    
        Point max() const
        {
            Point ret = Point(POINT_MIN, POINT_MIN);
            for(const ClipperLib::Path& polygon : paths)
            {
                for(Point p : polygon)
                {
                    ret.X = std::max(ret.X, p.X);
                    ret.Y = std::max(ret.Y, p.Y);
                }
            }
            return ret;
        }

        void applyMatrix(const PointMatrix& matrix)
        {
            for(unsigned int i=0; i<paths.size(); i++)
            {
                for(unsigned int j=0; j<paths[i].size(); j++)
                {
                    paths[i][j] = matrix.apply(paths[i][j]);
                }
            }
        }
    };

    /*!
     * A single area with holes. The first polygon is the outline, while the rest are holes within this outline.
     * 
     * This class has little more functionality than Polygons, but serves to show that a specific instance is ordered such that the first Polygon is the outline and the rest are holes.
     */
    class PolygonsPart : public Polygons
    {
    public:
        PolygonRef outerPolygon()
        {
            return paths[0];
        }
        ConstPolygonRef outerPolygon() const
        {
            return paths[0];
        }

        /*!
         * Tests whether the given point is inside this polygon part.
         * \param p The point to test whether it is inside.
         * \param border_result If the point is exactly on the border, this will be
         * returned instead.
         */
        bool inside(Point p, bool border_result = false) const;
    };

    /*!
     * Extension of vector<vector<unsigned int>> which is similar to a vector of PolygonParts, except the base of the container is indices to polygons into the original Polygons, instead of the polygons themselves
     */
    class PartsView : public std::vector<std::vector<unsigned int>>
    {
    public:
        Polygons& polygons;
        PartsView(Polygons& polygons) : polygons(polygons) { }
        /*!
         * Get the index of the PolygonsPart of which the polygon with index \p poly_idx is part.
         * 
         * \param poly_idx The index of the polygon in \p polygons
         * \param boundary_poly_idx Optional output parameter: The index of the boundary polygon of the part in \p polygons
         * \return The PolygonsPart containing the polygon with index \p poly_idx
         */
        unsigned int getPartContaining(unsigned int poly_idx, unsigned int* boundary_poly_idx = nullptr) const;
        /*!
         * Assemble the PolygonsPart of which the polygon with index \p poly_idx is part.
         * 
         * \param poly_idx The index of the polygon in \p polygons
         * \param boundary_poly_idx Optional output parameter: The index of the boundary polygon of the part in \p polygons
         * \return The PolygonsPart containing the polygon with index \p poly_idx
         */
        PolygonsPart assemblePartContaining(unsigned int poly_idx, unsigned int* boundary_poly_idx = nullptr) const;
        /*!
         * Assemble the PolygonsPart of which the polygon with index \p poly_idx is part.
         * 
         * \param part_idx The index of the part
         * \return The PolygonsPart with index \p poly_idx
         */
        PolygonsPart assemblePart(unsigned int part_idx) const;
    };

    struct DLPLayer
    {
        ClipperLib::cInt printZ;     //!< The height at which this layer needs to be printed. Can differ from sliceZ due to the raft.
        Polygons polygons;
    };

    class DLPDataImpl
    {
    public:
        DLPDataImpl();
        ~DLPDataImpl();



        std::vector<DLPLayer> layersData;
    };

    struct LightOffCircle
    {
        ClipperLib::IntPoint point;
        ClipperLib::cInt radius = 0;
    };

    class LightOffDebugger
    {
    public:
        virtual void onIteration(const LightOffCircle& circle) = 0;
    };

    /*
    calculate the pole of the polygons,and return pole radius and pole's coordinate.
    @param polygons, the input Polygons.
    @param result, the output circle centroid.
    @param type, the algorithm selected to calculate the pole of the polygons.
    for type=0, select QUARDTER_COVER;
    for type=1, select REGIONAL_SAMPLE;
    for type=2, select POISSON_SAMPLE;
    for type=3, select INSCRIBED_CIRCLE;
    */
    ClipperLib::cInt lightOffDistance(const Polygons& polygons, Point& result, const int type = 1);

    ClipperLib::cInt lightOffDistance(const Polygons& polygons, LightOffCircle& result,
        LightOffDebugger* debugger = nullptr, ccglobal::Tracer* tracer = nullptr);
}//namespace cxutil

#endif//CX_UTILS_POLYGON_H
