ClipperLib::Paths Clipper::toClipper(const std::vector<ofPolyline>& polylines,
                                     ClipperLib::cInt scale)
{
    ClipperLib::Paths paths;
    for (auto& polyline: polylines) paths.push_back(toClipper(polyline, scale));
    return paths;
}

void BooleanTool::pathObjectToPolygons(
        const PathObject* object,
        ClipperLib::Paths& polygons,
        PolyMap& polymap)
{
	object->update();
	
	polygons.reserve(polygons.size() + object->parts().size());
	
	for (const auto& part : object->parts())
	{
		const PathCoordVector& path_coords = part.path_coords;
		auto path_coords_end = path_coords.size();
		if (part.isClosed())
			--path_coords_end;
		
		ClipperLib::Path polygon;
		for (auto i = 0u; i < path_coords_end; ++i)
		{
			auto point = MapCoord { path_coords[i].pos };
			polygon.push_back(ClipperLib::IntPoint(point.nativeX(), point.nativeY()));
			polymap.insertMulti(polygon.back(), std::make_pair(&part, &path_coords[i]));
		}
		
		bool orientation = Orientation(polygon);
		if ( (&part == &object->parts().front()) != orientation )
		{
			std::reverse(polygon.begin(), polygon.end());
		}
		
		// Push_back shall move the polygon.
		static_assert(std::is_nothrow_move_constructible<ClipperLib::Path>::value, "ClipperLib::Path must be nothrow move constructible");
		polygons.push_back(polygon);
	}
}

ClipperLib::Paths Slic3rMultiPoints_to_ClipperPaths(const Polylines &input)
{
    ClipperLib::Paths retval;
    for (Polylines::const_iterator it = input.begin(); it != input.end(); ++it)
        retval.emplace_back(Slic3rMultiPoint_to_ClipperPath(*it));
    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));
    }

ClipperLib::Paths ClipperHelpers::convert(
    const QVector<Path>&  paths,
    const PositiveLength& maxArcTolerance) noexcept {
  ClipperLib::Paths p;
  p.reserve(paths.size());
  foreach (const Path& path, paths) {
    p.push_back(convert(path, maxArcTolerance));
  }

T
ClipperPaths_to_Slic3rMultiPoints(const ClipperLib::Paths &input)
{
    T retval;
    for (ClipperLib::Paths::const_iterator it = input.begin(); it != input.end(); ++it)
        retval.push_back(ClipperPath_to_Slic3rMultiPoint<typename T::value_type>(*it));
    return retval;
}

void scaleClipperPolygons(ClipperLib::Paths &polygons)
{
    PROFILE_FUNC();
    for (ClipperLib::Paths::iterator it = polygons.begin(); it != polygons.end(); ++it)
        for (ClipperLib::Path::iterator pit = (*it).begin(); pit != (*it).end(); ++pit) {
            pit->X <<= CLIPPER_OFFSET_POWER_OF_2;
            pit->Y <<= CLIPPER_OFFSET_POWER_OF_2;
        }
}

void
scaleClipperPolygons(ClipperLib::Paths &polygons, const double scale)
{
    for (ClipperLib::Paths::iterator it = polygons.begin(); it != polygons.end(); ++it) {
        for (ClipperLib::Path::iterator pit = (*it).begin(); pit != (*it).end(); ++pit) {
            (*pit).X *= scale;
            (*pit).Y *= scale;
        }
    }
}

void unscaleClipperPolygons(ClipperLib::Paths &polygons)
{
    PROFILE_FUNC();
    for (ClipperLib::Paths::iterator it = polygons.begin(); it != polygons.end(); ++it)
        for (ClipperLib::Path::iterator pit = (*it).begin(); pit != (*it).end(); ++pit) {
            pit->X += CLIPPER_OFFSET_SCALE_ROUNDING_DELTA;
            pit->Y += CLIPPER_OFFSET_SCALE_ROUNDING_DELTA;
            pit->X >>= CLIPPER_OFFSET_POWER_OF_2;
            pit->Y >>= CLIPPER_OFFSET_POWER_OF_2;
        }
}

void
ClipperPaths_to_Slic3rMultiPoints(const ClipperLib::Paths &input, T* output)
{
    PROFILE_FUNC();
    output->clear();
    output->reserve(input.size());
    for (ClipperLib::Paths::const_iterator it = input.begin(); it != input.end(); ++it) {
        typename T::value_type p;
        ClipperPath_to_Slic3rMultiPoint(*it, &p);
        output->push_back(p);
    }
}

void Grasp_Calculator::double_polygon_to_path(DPolygon2D double_polygon, ClipperLib::Paths &int_polygon)
{
    ClipperLib::cInt factor = 100000;
    ClipperLib::Path int_poly;
    int_polygon.clear();
    for (std::vector<DoublePoint2D>::iterator p2d = double_polygon.begin(); p2d != double_polygon.end(); ++p2d)
    {
        ClipperLib::IntPoint p;
        p.X = (ClipperLib::cInt)(factor * p2d->x);
        p.Y = (ClipperLib::cInt)(factor * p2d->y);
        int_poly.push_back(p);
    }
    int_polygon.push_back(int_poly);
}

std::vector<polygon> polygon::from(const ClipperLib::Paths& paths, base_int maxDenom)
{
	std::vector<polygon> ret;
	for(auto iter = paths.begin(); iter != paths.end(); iter++)
	{
		ret.push_back(polygon());
		auto& polyRef = ret.back();
		for(auto point = iter->begin(); point != iter->end(); point++)
		{
			polyRef.vertexes.push_back(vec2d(int_frac(point->X, maxDenom), int_frac(point->Y, maxDenom)));
		}
	}
	return ret;
}

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);
}

	DLL_PUBLIC void CDECL execute_offset(ClipperLib::ClipperOffset *ptr, double delta,
																			void* outputArray, void(*append)(void* outputArray, size_t polyIndex, ClipperLib::IntPoint point)) {
		ClipperLib::Paths paths = ClipperLib::Paths();

		try {
			ptr->Execute(paths, delta);
		} catch(ClipperLib::clipperException e) {
			printf(e.what());
		}

		for (size_t i = 0; i < paths.size(); i++) {
			for (auto &point: paths[i]) {
				append(outputArray, i, point);
			}
		}
	}

// Set the objects (defined by contour points) to be models in the world and scene.
void World::setObjectsToBeModeled(const std::vector<std::vector<cv::Point>> contours) {

    int contourSize = (int)contours.size();
    for(int i = 0; i < contourSize; i++ )
    {
        std::vector<cv::Point> currentShape = contours[i];
        int numOfPoints = (int)currentShape.size();

        b2Vec2 * vertices = new b2Vec2[numOfPoints];
        ClipperLib::Paths* polygons = new ClipperLib::Paths();
        ClipperLib::Path polygon;

        for (int j = 0; j < numOfPoints; j++)
        {
            vertices[j].x = currentShape[j].x / PTM_RATIO;
            vertices[j].y = currentShape[j].y / PTM_RATIO;

            //cv::line(m_scene, currentShape[j], currentShape[(j + 1) % numOfPoints], cv::Scalar(0,0,255));
            //std::cout << "[" << vertices[j].x << "," <<vertices[j].y << "]" << std::endl;

            polygon.push_back(ClipperLib::IntPoint(currentShape[j].x, currentShape[j].y));
        }

        b2BodyDef objectBodyDef;
        objectBodyDef.type = b2_staticBody;

        b2Body *objectBody = m_world->CreateBody(&objectBodyDef);
        objectBody->SetUserData(polygons);

        polygons->push_back(polygon);

        b2EdgeShape objectEdgeShape;
        b2FixtureDef objectShapeDef;
        objectShapeDef.shape = &objectEdgeShape;

        for (int j = 0; j < numOfPoints - 1; j++)
        {
            objectEdgeShape.Set(vertices[j], vertices[j+1]);
            objectBody->CreateFixture(&objectShapeDef);
        }

        objectEdgeShape.Set(vertices[numOfPoints - 1], vertices[0]);
        objectBody->CreateFixture(&objectShapeDef);
        m_objectBodies.push_back(objectBody);
        delete[] vertices;
    }
}

QVector<Path> ClipperHelpers::convert(const ClipperLib::Paths& paths) noexcept {
  QVector<Path> p;
  p.reserve(paths.size());
  for (const ClipperLib::Path& path : paths) {
    p.append(convert(path));
  }
  return p;
}

	DLL_PUBLIC void CDECL add_offset_paths(ClipperLib::ClipperOffset *ptr, ClipperLib::IntPoint** paths, size_t* path_counts,
																				size_t count, ClipperLib::JoinType joinType, ClipperLib::EndType endType) {
		ClipperLib::Paths vs = ClipperLib::Paths();
		for(size_t i = 0; i < count; i++) {
			auto it = vs.emplace(vs.end());

			for(size_t j = 0; j < path_counts[i]; j++) {
				it->emplace(it->end(), paths[i][j].X, paths[i][j].Y);
			}
		}

		try {
			ptr->AddPaths(vs, joinType, endType);
		} catch(ClipperLib::clipperException e) {
			printf(e.what());
		}
	}

// 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.
ClipperLib::Paths _offset(const Slic3r::ExPolygon &expolygon, const float delta,
    ClipperLib::JoinType joinType, double miterLimit)
{
//    printf("new ExPolygon offset\n");
    // 1) Offset the outer contour.
    const float delta_scaled = delta * float(CLIPPER_OFFSET_SCALE);
    ClipperLib::Paths contours;
    {
        ClipperLib::Path input = Slic3rMultiPoint_to_ClipperPath(expolygon.contour);
        scaleClipperPolygon(input);
        ClipperLib::ClipperOffset co;
        if (joinType == jtRound)
            co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
        else
            co.MiterLimit = miterLimit;
        co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
        co.AddPath(input, joinType, ClipperLib::etClosedPolygon);
        co.Execute(contours, delta_scaled);
    }

    // 2) Offset the holes one by one, collect the results.
    ClipperLib::Paths holes;
    {
        holes.reserve(expolygon.holes.size());
        for (Polygons::const_iterator it_hole = expolygon.holes.begin(); it_hole != expolygon.holes.end(); ++ it_hole) {
            ClipperLib::Path input = Slic3rMultiPoint_to_ClipperPath_reversed(*it_hole);
            scaleClipperPolygon(input);
            ClipperLib::ClipperOffset co;
            if (joinType == jtRound)
                co.ArcTolerance = miterLimit * double(CLIPPER_OFFSET_SCALE);
            else
                co.MiterLimit = miterLimit;
            co.ShortestEdgeLength = double(std::abs(delta_scaled * CLIPPER_OFFSET_SHORTEST_EDGE_FACTOR));
            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;
    if (holes.empty()) {
        output = std::move(contours);
    } else {
        ClipperLib::Clipper clipper;
        clipper.Clear();
        clipper.AddPaths(contours, ClipperLib::ptSubject, true);
        clipper.AddPaths(holes, ClipperLib::ptClip, true);
        clipper.Execute(ClipperLib::ctDifference, output, ClipperLib::pftNonZero, ClipperLib::pftNonZero);
    }
    
    // 4) Unscale the output.
    unscaleClipperPolygons(output);
    return output;
}

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 ElementGeometryClipper::visitArea(const Area& area)
{
    ClipperLib::Path areaShape;
    PointLocation pointLocation = setPath(quadKeyBbox_, area, areaShape);
    // 1. all geometry inside current quadkey: no need to truncate.
    if (pointLocation == PointLocation::AllInside) {
        callback_(area, quadKey_);
        return;
    }

    // 2. all geometry outside: skip
    if (pointLocation == PointLocation::AllOutside) {
        return;
    }

    ClipperLib::Paths solution;
    clipper_.AddPath(areaShape, ClipperLib::ptSubject, true);
    clipper_.AddPath(createPathFromBoundingBox(), ClipperLib::ptClip, true);
    clipper_.Execute(ClipperLib::ctIntersection, solution);
    clipper_.Clear();

    // 3. way intersects border only once: store a copy with clipped geometry
    if (solution.size() == 1) {
        Area clippedArea;
        setData(clippedArea, area, solution[0]);
        callback_(clippedArea, quadKey_);
    }
        // 4. in this case, result should be stored as relation (collection of areas)
    else {
        Relation relation;
        relation.id = area.id;
        relation.tags = area.tags;
        relation.elements.reserve(solution.size());
        for (auto it = solution.begin(); it != solution.end(); ++it) {
            auto clippedArea = std::make_shared<Area> ();
            clippedArea->id = area.id;
            setCoordinates(*clippedArea, *it);
            relation.elements.push_back(clippedArea);
        }
        callback_(relation, quadKey_);
    }
}