void
offset(const Slic3r::Polygons &polygons, ClipperLib::Paths* retval, const float delta,
    ClipperLib::JoinType joinType, double miterLimit)
{
    PROFILE_FUNC();
    // read input
    ClipperLib::Paths input;
    Slic3rMultiPoints_to_ClipperPaths(polygons, &input);
    
    // scale input
    scaleClipperPolygons(input);
    
    // perform offset
    ClipperLib::ClipperOffset co;
    if (joinType == jtRound) {
        co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
    } else {
        co.MiterLimit = miterLimit;
    }
    {
        PROFILE_BLOCK(offset_AddPaths);
        co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
    }
    {
        PROFILE_BLOCK(offset_Execute);
        co.Execute(*retval, delta * float(CLIPPER_OFFSET_SCALE));
    }
    
    // unscale output
    unscaleClipperPolygons(*retval);
}

ClipperLib::Paths
_offset(const Polygons &polygons, const float delta,
    double scale, ClipperLib::JoinType joinType, double miterLimit)
{
    // read input
    ClipperLib::Paths input = Slic3rMultiPoints_to_ClipperPaths(polygons);
    
    // scale input
    scaleClipperPolygons(input, scale);
    
    // perform offset
    ClipperLib::ClipperOffset co;
    if (joinType == jtRound) {
        co.ArcTolerance = miterLimit;
    } else {
        co.MiterLimit = miterLimit;
    }
    co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
    ClipperLib::Paths retval;
    co.Execute(retval, (delta*scale));
    
    // unscale output
    scaleClipperPolygons(retval, 1/scale);
    return retval;
}

    void build(utymap::meshing::Polygon& polygon)
    {
        ClipperLib::ClipperOffset offset;
        ClipperLib::Path path;
        path.reserve(polygon.points.size() / 2);

        auto lastPointIndex = polygon.points.size() - 2;
        double min = std::numeric_limits<double>::max();
        for (std::size_t i = 0; i < polygon.points.size(); i += 2) {
            auto nextIndex = i == lastPointIndex ? 0 : i + 2;

            utymap::meshing::Vector2 v1(polygon.points[i], polygon.points[i + 1]);
            utymap::meshing::Vector2 v2(polygon.points[nextIndex], polygon.points[nextIndex + 1]);

            min = std::min(min, utymap::meshing::Vector2::distance(v1, v2));

            path.push_back(ClipperLib::IntPoint(static_cast<ClipperLib::cInt>(v1.x * Scale), 
                                                static_cast<ClipperLib::cInt>(v1.y * Scale)));
        }

        offset.AddPath(path, ClipperLib::JoinType::jtMiter, ClipperLib::EndType::etClosedPolygon);

        ClipperLib::Paths solution;
        // NOTE: use minimal side value as reference for offsetting.
        offset.Execute(solution, -(min / 10) * Scale);

        // NOTE: this is unexpected result for algorithm below, fallback to flat roof.
        if (solution.size() != 1 || solution[0].size() != path.size()) {
            return FlatRoofBuilder::build(polygon);
        }

        buildMansardShape(polygon, solution[0], findFirstIndex(solution[0][0], polygon));
    }

Vector<Vector2> expand(const Vector<Vector2> &points, const Rect2i &rect, float epsilon = 2.0) {
	int size = points.size();
	ERR_FAIL_COND_V(size < 2, Vector<Vector2>());

	ClipperLib::Path subj;
	ClipperLib::PolyTree solution;
	ClipperLib::PolyTree out;

	for (int i = 0; i < points.size(); i++) {

		subj << ClipperLib::IntPoint(points[i].x * PRECISION, points[i].y * PRECISION);
	}
	ClipperLib::ClipperOffset co;
	co.AddPath(subj, ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
	co.Execute(solution, epsilon * PRECISION);

	ClipperLib::PolyNode *p = solution.GetFirst();

	ERR_FAIL_COND_V(!p, points);

	while (p->IsHole()) {
		p = p->GetNext();
	}

	//turn the result into simply polygon (AKA, fix overlap)

	//clamp into the specified rect
	ClipperLib::Clipper cl;
	cl.StrictlySimple(true);
	cl.AddPath(p->Contour, ClipperLib::ptSubject, true);
	//create the clipping rect
	ClipperLib::Path clamp;
	clamp.push_back(ClipperLib::IntPoint(0, 0));
	clamp.push_back(ClipperLib::IntPoint(rect.size.width * PRECISION, 0));
	clamp.push_back(ClipperLib::IntPoint(rect.size.width * PRECISION, rect.size.height * PRECISION));
	clamp.push_back(ClipperLib::IntPoint(0, rect.size.height * PRECISION));
	cl.AddPath(clamp, ClipperLib::ptClip, true);
	cl.Execute(ClipperLib::ctIntersection, out);

	Vector<Vector2> outPoints;
	ClipperLib::PolyNode *p2 = out.GetFirst();
	ERR_FAIL_COND_V(!p2, points);

	while (p2->IsHole()) {
		p2 = p2->GetNext();
	}

	int lasti = p2->Contour.size() - 1;
	Vector2 prev = Vector2(p2->Contour[lasti].X / PRECISION, p2->Contour[lasti].Y / PRECISION);
	for (unsigned int i = 0; i < p2->Contour.size(); i++) {

		Vector2 cur = Vector2(p2->Contour[i].X / PRECISION, p2->Contour[i].Y / PRECISION);
		if (cur.distance_to(prev) > 0.5) {
			outPoints.push_back(cur);
			prev = cur;
		}
	}
	return outPoints;
}

std::vector<Vec2> AutoPolygon::expand(const std::vector<Vec2>& points, const cocos2d::Rect &rect, const float& epsilon)
{
    auto size = points.size();
    // if there are less than 3 points, then we have nothing
    if(size<3)
    {
        log("AUTOPOLYGON: cannot expand points for %s with less than 3 points, e: %f", _filename.c_str(), epsilon);
        return std::vector<Vec2>();
    }
    ClipperLib::Path subj;
    ClipperLib::PolyTree solution;
    ClipperLib::PolyTree out;
    for(std::vector<Vec2>::const_iterator it = points.begin(); it<points.end(); it++)
    {
        subj << ClipperLib::IntPoint(it-> x* PRECISION, it->y * PRECISION);
    }
    ClipperLib::ClipperOffset co;
    co.AddPath(subj, ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
    co.Execute(solution, epsilon * PRECISION);
    
    ClipperLib::PolyNode* p = solution.GetFirst();
    if(!p)
    {
        log("AUTOPOLYGON: Clipper failed to expand the points");
        return points;
    }
    while(p->IsHole()){
        p = p->GetNext();
    }

    //turn the result into simply polygon (AKA, fix overlap)
    
    //clamp into the specified rect
    ClipperLib::Clipper cl;
    cl.StrictlySimple(true);
    cl.AddPath(p->Contour, ClipperLib::ptSubject, true);
    //create the clipping rect
    ClipperLib::Path clamp;
    clamp.push_back(ClipperLib::IntPoint(0, 0));
    clamp.push_back(ClipperLib::IntPoint(rect.size.width/_scaleFactor * PRECISION, 0));
    clamp.push_back(ClipperLib::IntPoint(rect.size.width/_scaleFactor * PRECISION, rect.size.height/_scaleFactor * PRECISION));
    clamp.push_back(ClipperLib::IntPoint(0, rect.size.height/_scaleFactor * PRECISION));
    cl.AddPath(clamp, ClipperLib::ptClip, true);
    cl.Execute(ClipperLib::ctIntersection, out);
    
    std::vector<Vec2> outPoints;
    ClipperLib::PolyNode* p2 = out.GetFirst();
    while(p2->IsHole()){
        p2 = p2->GetNext();
    }
    auto end = p2->Contour.end();
    for(std::vector<ClipperLib::IntPoint>::const_iterator pt = p2->Contour.begin(); pt < end; pt++)
    {
        outPoints.push_back(Vec2(pt->X/PRECISION, pt->Y/PRECISION));
    }
    return outPoints;
}

void safety_offset(ClipperLib::Paths* paths)
{
    // scale input
    scaleClipperPolygons(*paths, CLIPPER_OFFSET_SCALE);
    
    // perform offset (delta = scale 1e-05)
    ClipperLib::ClipperOffset co;
    co.MiterLimit = 2;
    co.AddPaths(*paths, ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
    co.Execute(*paths, 10.0 * CLIPPER_OFFSET_SCALE);
    
    // unscale output
    scaleClipperPolygons(*paths, 1.0/CLIPPER_OFFSET_SCALE);
}

void safety_offset(ClipperLib::Paths* paths)
{
    PROFILE_FUNC();

    // scale input
    scaleClipperPolygons(*paths);
    
    // perform offset (delta = scale 1e-05)
    ClipperLib::ClipperOffset co;
#ifdef CLIPPER_UTILS_DEBUG
	if (clipper_export_enabled) {
		static int iRun = 0;
		export_clipper_input_polygons_bin(debug_out_path("safety_offset-polygons-%d", ++iRun).c_str(), *paths, ClipperLib::Paths());
	}
#endif /* CLIPPER_UTILS_DEBUG */
    ClipperLib::Paths out;
    for (size_t i = 0; i < paths->size(); ++ i) {
        ClipperLib::Path &path = (*paths)[i];
		co.Clear();
        co.MiterLimit = 2;
        bool ccw = ClipperLib::Orientation(path);
        if (! ccw)
            std::reverse(path.begin(), path.end());
        {
            PROFILE_BLOCK(safety_offset_AddPaths);
            co.AddPath((*paths)[i], ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
        }
        {
            PROFILE_BLOCK(safety_offset_Execute);
            // offset outside by 10um
            ClipperLib::Paths out_this;
            co.Execute(out_this, ccw ? 10.f * float(CLIPPER_OFFSET_SCALE) : -10.f * float(CLIPPER_OFFSET_SCALE));
            if (! ccw) {
                // Reverse the resulting contours once again.
                for (ClipperLib::Paths::iterator it = out_this.begin(); it != out_this.end(); ++ it)
                    std::reverse(it->begin(), it->end());
            }
            if (out.empty())
                out = std::move(out_this);
            else
                std::move(std::begin(out_this), std::end(out_this), std::back_inserter(out));
        }
    }
    *paths = std::move(out);
    
    // unscale output
    unscaleClipperPolygons(*paths);
}

geo::Ring<Vector> Environment::inflate(geo::Ring<Vector> const& ring, int inflateRadius) {
	ClipperLib::Path subj;
  	ClipperLib::Paths solution;
  	for (Vector const& v : ring)
  		subj << ClipperLib::IntPoint((int)v.x, (int)v.y);
    ClipperLib::ClipperOffset co;
	co.AddPath(subj, ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
	co.Execute(solution, inflateRadius);
	#ifdef DEBUG
		assert(solution.size() == 1);
	#endif
	Ring ans;
	for (ClipperLib::IntPoint const& v : solution[0])
		ans.push_back(Vector(v.X, v.Y));
	geo::correct(ans);
	return ans;
}

void safety_offset(ClipperLib::Paths* &subject)
{
    // scale input
    scaleClipperPolygons(*subject, CLIPPER_OFFSET_SCALE);
    
    // perform offset (delta = scale 1e-05)
    ClipperLib::Paths* retval = new ClipperLib::Paths();
    ClipperLib::ClipperOffset co;
    co.MiterLimit = 2;
    co.AddPaths(*subject, ClipperLib::jtMiter, ClipperLib::etClosedPolygon);
    co.Execute(*retval, 10.0 * CLIPPER_OFFSET_SCALE);
    
    // unscale output
    scaleClipperPolygons(*retval, 1.0/CLIPPER_OFFSET_SCALE);
    
    // delete original data and switch pointer
    delete subject;
    subject = retval;
}

TriangleMesh2D TriangulatePolyline(const Path2D& path, float offset) {
  // clipper only works with integer points
  ClipperLib::Path scaled_path = UScalePathDiaToClipper(path);

  // inflate
  ClipperLib::ClipperOffset co;
  co.AddPath(scaled_path, ClipperLib::JoinType::jtMiter,
             ClipperLib::EndType::etOpenButt);
  ClipperLib::Paths inflated;
  // inflate by input amount.
  co.Execute(inflated, offset * kUScale);

  // one out path
  // for now, we do not allow the holes to appear in the inflated path
  // maybe we allow this later using union
  // assert(inflated.size() == 1 && "inflated path has holes");
  std::vector<Vector2f> pts = DScalePathClipperToDia(inflated[0]);
  return DelaunaySweepline(pts, std::vector<Path2D>());
}

ClipperLib::Paths _offset(ClipperLib::Paths &&input, ClipperLib::EndType endType, const float delta, ClipperLib::JoinType joinType, double miterLimit)
{
    // scale input
    scaleClipperPolygons(input);
    
    // perform offset
    ClipperLib::ClipperOffset co;
    if (joinType == jtRound)
        co.ArcTolerance = miterLimit;
    else
        co.MiterLimit = miterLimit;
    float delta_scaled = delta * float(CLIPPER_OFFSET_SCALE);
    co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
    co.AddPaths(input, joinType, endType);
    ClipperLib::Paths retval;
    co.Execute(retval, delta_scaled);
    
    // unscale output
    unscaleClipperPolygons(retval);
    return retval;
}

void
offset2(const Slic3r::Polygons &polygons, ClipperLib::Paths &retval, const float delta1,
    const float delta2, const double scale, const ClipperLib::JoinType joinType, const double miterLimit)
{
    // read input
    ClipperLib::Paths input;
    Slic3rMultiPoints_to_ClipperPaths(polygons, input);
    
    // scale input
    scaleClipperPolygons(input, scale);
    
    // prepare ClipperOffset object
    ClipperLib::ClipperOffset co;
    if (joinType == jtRound) {
        co.ArcTolerance = miterLimit;
    } else {
        co.MiterLimit = miterLimit;
    }
    
    // perform first offset
    ClipperLib::Paths output1;
    co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
    co.Execute(output1, (delta1*scale));
    
    // perform second offset
    co.Clear();
    co.AddPaths(output1, joinType, ClipperLib::etClosedPolygon);
    co.Execute(retval, (delta2*scale));
    
    // unscale output
    scaleClipperPolygons(retval, 1/scale);
}

void
offset2(const Slic3r::Polygons &polygons, ClipperLib::Paths* retval, const float delta1,
    const float delta2, const ClipperLib::JoinType joinType, const double miterLimit)
{
    if (delta1 * delta2 >= 0) {
        // Both deltas are the same signum
        offset(polygons, retval, delta1 + delta2, joinType, miterLimit);
        return;
    }
#ifdef CLIPPER_UTILS_DEBUG
    BoundingBox bbox = get_extents(polygons);
    coordf_t stroke_width = scale_(0.005);
    static int iRun = 0;
    ++ iRun;
    bool flipY = false;
    SVG svg(debug_out_path("offset2-%d.svg", iRun), bbox, scale_(1.), flipY);
    for (Slic3r::Polygons::const_iterator it = polygons.begin(); it != polygons.end(); ++ it)
        svg.draw(it->lines(), "gray", stroke_width);
#endif /* CLIPPER_UTILS_DEBUG */

    // read input
    ClipperLib::Paths input;
    Slic3rMultiPoints_to_ClipperPaths(polygons, &input);
    
    // scale input
    scaleClipperPolygons(input);
    
    // prepare ClipperOffset object
    ClipperLib::ClipperOffset co;
    if (joinType == jtRound) {
        co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
    } else {
        co.MiterLimit = miterLimit;
    }
    
    // perform first offset
    ClipperLib::Paths output1;
    co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
    co.Execute(output1, delta1 * float(CLIPPER_OFFSET_SCALE));
#ifdef CLIPPER_UTILS_DEBUG
    svg.draw(output1, 1. / double(CLIPPER_OFFSET_SCALE), "red", stroke_width);
#endif /* CLIPPER_UTILS_DEBUG */
    
    // perform second offset
    co.Clear();
    co.AddPaths(output1, joinType, ClipperLib::etClosedPolygon);
    co.Execute(*retval, delta2 * float(CLIPPER_OFFSET_SCALE));
#ifdef CLIPPER_UTILS_DEBUG
    svg.draw(*retval, 1. / double(CLIPPER_OFFSET_SCALE), "green", stroke_width);
#endif /* CLIPPER_UTILS_DEBUG */

    // unscale output
    unscaleClipperPolygons(*retval);
}

ClipperLib::Paths
_offset2(const Polygons &polygons, const float delta1, const float delta2,
    const ClipperLib::JoinType joinType, const double miterLimit)
{
    // read input
    ClipperLib::Paths input = Slic3rMultiPoints_to_ClipperPaths(polygons);
    
    // scale input
    scaleClipperPolygons(input);
    
    // prepare ClipperOffset object
    ClipperLib::ClipperOffset co;
    if (joinType == jtRound) {
        co.ArcTolerance = miterLimit;
    } else {
        co.MiterLimit = miterLimit;
    }
    float delta_scaled1 = delta1 * float(CLIPPER_OFFSET_SCALE);
    float delta_scaled2 = delta2 * float(CLIPPER_OFFSET_SCALE);
    co.ShortestEdgeLength = double(std::max(std::abs(delta_scaled1), std::abs(delta_scaled2)) * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR);
    
    // perform first offset
    ClipperLib::Paths output1;
    co.AddPaths(input, joinType, ClipperLib::etClosedPolygon);
    co.Execute(output1, delta_scaled1);
    
    // perform second offset
    co.Clear();
    co.AddPaths(output1, joinType, ClipperLib::etClosedPolygon);
    ClipperLib::Paths retval;
    co.Execute(retval, delta_scaled2);
    
    // unscale output
    unscaleClipperPolygons(retval);
    return retval;
}

// This is a safe variant of the polygon offset, tailored for a single ExPolygon:
// a single polygon with multiple non-overlapping holes.
// Each contour and hole is offsetted separately, then the holes are subtracted from the outer contours.
void offset(const Slic3r::ExPolygons &expolygons, ClipperLib::Paths* retval, const float delta,
    ClipperLib::JoinType joinType, double miterLimit)
{
//    printf("new ExPolygon offset\n");
    const float delta_scaled = delta * float(CLIPPER_OFFSET_SCALE);
    ClipperLib::Paths contours;
    ClipperLib::Paths holes;
    contours.reserve(expolygons.size());
    {
        size_t n_holes = 0;
        for (size_t i = 0; i < expolygons.size(); ++ i)
            n_holes += expolygons[i].holes.size();
        holes.reserve(n_holes);
    }

    for (Slic3r::ExPolygons::const_iterator it_expoly = expolygons.begin(); it_expoly != expolygons.end(); ++ it_expoly) {
        // 1) Offset the outer contour.
        {
            ClipperLib::Path input;
            Slic3rMultiPoint_to_ClipperPath(it_expoly->contour, &input);
            scaleClipperPolygon(input);
            ClipperLib::ClipperOffset co;
            if (joinType == jtRound)
                co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
            else
                co.MiterLimit = miterLimit;
            co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
            ClipperLib::Paths out;
            co.Execute(out, delta_scaled);
            contours.insert(contours.end(), out.begin(), out.end());
        }

        // 2) Offset the holes one by one, collect the results.
        {
            for (Polygons::const_iterator it_hole = it_expoly->holes.begin(); it_hole != it_expoly->holes.end(); ++ it_hole) {
                ClipperLib::Path input;
                Slic3rMultiPoint_to_ClipperPath_reversed(*it_hole, &input);
                scaleClipperPolygon(input);
                ClipperLib::ClipperOffset co;
                if (joinType == jtRound)
                    co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
                else
                    co.MiterLimit = miterLimit;
                co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
                ClipperLib::Paths out;
                co.Execute(out, - delta_scaled);
                holes.insert(holes.end(), out.begin(), out.end());
            }
        }
    }

    // 3) Subtract holes from the contours.
    ClipperLib::Paths output;
    {
        ClipperLib::Clipper clipper;
        clipper.Clear();
        clipper.AddPaths(contours, ClipperLib::ptSubject, true);
        clipper.AddPaths(holes, ClipperLib::ptClip, true);
        clipper.Execute(ClipperLib::ctDifference, *retval, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
    }
    
    // 4) Unscale the output.
    unscaleClipperPolygons(*retval);
}