Slic3r::MultiPoint Class Reference

#include <src/libslic3r/MultiPoint.hpp>

Inheritance diagram for Slic3r::MultiPoint:

Collaboration diagram for Slic3r::MultiPoint:

Public Member Functions
	MultiPoint ()=default
	MultiPoint (const MultiPoint &other)
	MultiPoint (MultiPoint &&other)
	MultiPoint (std::initializer_list< Point > list)
	MultiPoint (const Points &_points)
MultiPoint &	operator= (const MultiPoint &other)
MultiPoint &	operator= (MultiPoint &&other)
void	scale (double factor)
void	scale (double factor_x, double factor_y)
void	translate (double x, double y)
void	translate (const Point &vector)
void	rotate (double angle)
void	rotate (double cos_angle, double sin_angle)
void	rotate (double angle, const Point &center)
void	reverse ()
const Point &	front () const
const Point &	back () const
const Point &	first_point () const
size_t	size () const
bool	empty () const
bool	is_valid () const
int	find_point (const Point &point) const
int	find_point (const Point &point, const double scaled_epsilon) const
int	closest_point_index (const Point &point) const
const Point *	closest_point (const Point &point) const
BoundingBox	bounding_box () const
bool	has_duplicate_points () const
bool	remove_duplicate_points ()
void	clear ()
void	append (const Point &point)
void	append (const Points &src)
void	append (const Points::const_iterator &begin, const Points::const_iterator &end)
void	append (Points &&src)
auto	begin ()
auto	begin () const
auto	end ()
auto	end () const
auto	cbegin () const
auto	cend () const

Static Public Member Functions
static Points	douglas_peucker (const Points &points, const double tolerance)
static Points	visivalingam (const Points &pts, const double &tolerance)

Public Attributes
Points	points

Detailed Description

Constructor & Destructor Documentation

MultiPoint() [1/5]

Slic3r::MultiPoint::MultiPoint ( )

default

MultiPoint() [2/5]

Slic3r::MultiPoint::MultiPoint ( const MultiPoint &  other )

inline

: points(other.points) {}

MultiPoint() [3/5]

Slic3r::MultiPoint::MultiPoint ( MultiPoint &&  other )

inline

: points(std::move(other.points)) {}

MultiPoint() [4/5]

Slic3r::MultiPoint::MultiPoint ( std::initializer_list< Point >  list )

inline

: points(list) {}

MultiPoint() [5/5]

Slic3r::MultiPoint::MultiPoint ( const Points &  _points )

inlineexplicit

: points(_points) {}

Member Function Documentation

append() [1/4]

void Slic3r::MultiPoint::append ( const Point &  point )

inline

{ this->points.push_back(point); }

append() [2/4]

void Slic3r::MultiPoint::append ( const Points &  src )

inline

{ this->append(src.begin(), src.end()); }

References append().

Referenced by append().

Here is the call graph for this function:

Here is the caller graph for this function:

append() [3/4]

void Slic3r::MultiPoint::append ( const Points::const_iterator &  begin, const Points::const_iterator &  end  )

inline

{ this->points.insert(this->points.end(), begin, end); }

References begin(), and end().

Here is the call graph for this function:

append() [4/4]

void Slic3r::MultiPoint::append ( Points &&  src )

inline

    {
        if (this->points.empty()) {
            this->points = std::move(src);
        } else {
            this->points.insert(this->points.end(), src.begin(), src.end());
            src.clear();
        }
    }

back()

const Point & Slic3r::MultiPoint::back ( ) const

inline

{ return this->points.back(); }

Referenced by Slic3r::contour_distance(), Slic3r::cut2model(), Slic3r::improve_ordering_by_two_exchanges_with_segment_flipping(), Slic3r::make_wave(), Slic3r::makeGrid(), Slic3r::FFFTreeSupport::move_inside(), Slic3r::polylines_from_paths(), Slic3r::Arachne::removeDegenerateVerts(), Slic3r::FillLightning::Node::removeJunctionOverlap(), Slic3r::resample_polygon(), Slic3r::traverse_graph_generate_polylines(), and Slic3r::FFFSupport::tree_supports_generate_paths().

Here is the caller graph for this function:

begin() [1/2]

auto Slic3r::MultiPoint::begin ( )

inline

{ return points.begin(); }

References points.

Referenced by append(), Slic3r::contour_distance(), Slic3r::contour_distance(), Slic3r::contour_distance2(), Slic3r::EdgeGrid::Grid::create_from_m_contours(), and Slic3r::GUI::Selection::scale_to_fit_print_volume().

Here is the caller graph for this function:

begin() [2/2]

auto Slic3r::MultiPoint::begin ( ) const

inline

{ return points.begin(); }

References points.

bounding_box()

BoundingBox Slic3r::MultiPoint::bounding_box

(

)

const

{
    return BoundingBox(this->points);
}

References points.

Referenced by Slic3r::Fill3DHoneycomb::_fill_surface_single(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::FillGyroid::_fill_surface_single(), Slic3r::FillHoneycomb::_fill_surface_single(), Slic3r::FillLine::_fill_surface_single(), Slic3r::FillConcentric::_fill_surface_single(), Slic3r::Fill::_infill_direction(), Slic3r::get_extents(), Slic3r::get_extents(), Slic3r::GUI::Bed3D::init_gridlines(), Slic3r::sla::anonymous_namespace{Pad.cpp}::Intersector::intersects(), Slic3r::GUI::FillBedJob::prepare(), and Slic3r::GUI::Bed3D::set_shape().

Here is the caller graph for this function:

cbegin()

auto Slic3r::MultiPoint::cbegin ( ) const

inline

{ return points.begin(); }

References points.

cend()

auto Slic3r::MultiPoint::cend ( ) const

inline

{ return points.end();   }

References points.

clear()

void Slic3r::MultiPoint::clear ( )

inline

{ this->points.clear(); }

Referenced by Slic3r::FillAdaptive::connect_lines_using_hooks(), Slic3r::FFFTreeSupport::ensure_maximum_distance_polyline(), Slic3r::evaluate_support_arches(), Slic3r::FakeWipeTower::getFakeExtrusionPathsFromWipeTower(), Slic3r::AvoidCrossingPerimeters::init_layer(), Slic3r::Wipe::reset_path(), and Slic3r::Polyline::split_at().

Here is the caller graph for this function:

closest_point()

const Point * Slic3r::MultiPoint::closest_point ( const Point &  point ) const

inline

{ return this->points.empty() ? nullptr : &this->points[this->closest_point_index(point)]; }

References closest_point_index().

Here is the call graph for this function:

closest_point_index()

int Slic3r::MultiPoint::closest_point_index ( const Point &  point ) const

inline

                                                       {
        int idx = -1;
        if (! this->points.empty()) {
            idx = 0;
            double dist_min = (point - this->points.front()).cast<double>().norm();
            for (int i = 1; i < int(this->points.size()); ++ i) {
                double d = (this->points[i] - point).cast<double>().norm();
                if (d < dist_min) {
                    dist_min = d;
                    idx = i;
                }
            }
        }
        return idx;
    }

Referenced by closest_point(), and Slic3r::WipeTower::finish_layer().

Here is the caller graph for this function:

douglas_peucker()

Points Slic3r::MultiPoint::douglas_peucker ( const Points &  points, const double  tolerance  )

static

{
    Points result_pts;
  auto tolerance_sq = int64_t(sqr(tolerance));
    if (! pts.empty()) {
        const Point  *anchor      = &pts.front();
        size_t        anchor_idx  = 0;
        const Point  *floater     = &pts.back();
        size_t        floater_idx = pts.size() - 1;
        result_pts.reserve(pts.size());
        result_pts.emplace_back(*anchor);
        if (anchor_idx != floater_idx) {
            assert(pts.size() > 1);
            std::vector<size_t> dpStack;
            dpStack.reserve(pts.size());
            dpStack.emplace_back(floater_idx);
            for (;;) {
                int64_t max_dist_sq  = 0;
                size_t  furthest_idx = anchor_idx;
                // find point furthest from line seg created by (anchor, floater) and note it
                {
                    const Point   a = *anchor;
                    const Point   f = *floater;
                    const Vec2i64 v = (f - a).cast<int64_t>();
                    if (const int64_t l2 = v.squaredNorm(); l2 == 0) {
                        for (size_t i = anchor_idx + 1; i < floater_idx; ++ i)
                            if (int64_t dist_sq = (pts[i] - a).cast<int64_t>().squaredNorm(); dist_sq > max_dist_sq) {
                                max_dist_sq  = dist_sq;
                                furthest_idx = i;
                            }
                    } else {
                        const double dl2 = double(l2);
                        const Vec2d  dv  = v.cast<double>();
                        for (size_t i = anchor_idx + 1; i < floater_idx; ++ i) {
                            const Point   p  = pts[i];
                            const Vec2i64 va = (p  - a).template cast<int64_t>();
                            const int64_t t  = va.dot(v);
                            int64_t dist_sq;
                            if (t <= 0) {
                                dist_sq = va.squaredNorm();
                            } else if (t >= l2) {
                                dist_sq = (p - f).cast<int64_t>().squaredNorm();
                            } else {
                                const Vec2i64 w = ((double(t) / dl2) * dv).cast<int64_t>();
                                dist_sq = (w - va).squaredNorm();
                            }
                            if (dist_sq > max_dist_sq) {
                                max_dist_sq  = dist_sq;
                                furthest_idx = i;
                            }
                        }                        
                    }
                }
                // remove point if less than tolerance
                if (max_dist_sq <= tolerance_sq) {
                    result_pts.emplace_back(*floater);
                    anchor_idx = floater_idx;
                    anchor     = floater;
                    assert(dpStack.back() == floater_idx);
                    dpStack.pop_back();
                    if (dpStack.empty())
                        break;
                    floater_idx = dpStack.back();
                } else {
                    floater_idx = furthest_idx;
                    dpStack.emplace_back(floater_idx);
                }
                floater = &pts[floater_idx];
            }
        }
        assert(result_pts.front() == pts.front());
        assert(result_pts.back()  == pts.back());
 
#if 0
        {
            static int iRun = 0;
      BoundingBox bbox(pts);
      BoundingBox bbox2(result_pts);
      bbox.merge(bbox2);
            SVG svg(debug_out_path("douglas_peucker_%d.svg", iRun ++).c_str(), bbox);
            if (pts.front() == pts.back())
                svg.draw(Polygon(pts), "black");
            else
                svg.draw(Polyline(pts), "black");
            if (result_pts.front() == result_pts.back())
                svg.draw(Polygon(result_pts), "green", scale_(0.1));
            else
                svg.draw(Polyline(result_pts), "green", scale_(0.1));
        }
#endif
    }
    return result_pts;
}

References Slic3r::debug_out_path(), Slic3r::SVG::draw(), Slic3r::f(), Slic3r::l2(), Slic3r::BoundingBoxBase< PointType, APointsType >::merge(), scale_, and Slic3r::sqr().

Referenced by Slic3r::Polygon::douglas_peucker(), Slic3r::Polyline::simplify(), Slic3r::Polygon::simplify(), Slic3r::ExPolygon::simplify_p(), Slic3r::simplify_polygon_impl(), and Slic3r::Geometry::simplify_polygons().

Here is the call graph for this function:

Here is the caller graph for this function:

empty()

bool Slic3r::MultiPoint::empty ( ) const

inline

{ return points.empty(); }

References points.

Referenced by Slic3r::ExtrusionPath::collect_polylines(), Slic3r::ExtrusionMultiPath::collect_polylines(), Slic3r::ExtrusionLoop::collect_polylines(), Slic3r::Fill::connect_base_support(), Slic3r::connect_brim_lines(), Slic3r::FillAdaptive::connect_lines_using_hooks(), Slic3r::contour_distance(), Slic3r::contour_distance(), Slic3r::contour_distance2(), Slic3r::EdgeGrid::Grid::create(), Slic3r::EdgeGrid::Grid::create(), Slic3r::ExtrusionPath::empty(), Slic3r::GUI::RotoptimizeJob::finalize(), Slic3r::Print::finalize_first_layer_convex_hull(), Slic3r::FillAdaptive::Intersection::fresh(), Slic3r::Wipe::has_path(), Slic3r::Algorithm::merge_expansions_into_expolygons(), Slic3r::Voronoi::offset(), Slic3r::Arachne::simplify(), Slic3r::take_ccw_full(), Slic3r::take_ccw_limited(), Slic3r::take_cw_full(), Slic3r::take_cw_limited(), Slic3r::NSVGUtils::to_polygons(), Slic3r::AvoidCrossingPerimeters::travel_to(), Slic3r::GUI::GLCanvas3D::update_sequential_clearance(), and Slic3r::variable_offset_outer_ex().

Here is the caller graph for this function:

end() [1/2]

auto Slic3r::MultiPoint::end ( )

inline

{ return points.end();   }

References points.

Referenced by append(), Slic3r::Polyline::append(), Slic3r::contour_distance(), Slic3r::contour_distance(), Slic3r::contour_distance2(), Slic3r::EdgeGrid::Grid::create_from_m_contours(), and Slic3r::GUI::Selection::scale_to_fit_print_volume().

Here is the caller graph for this function:

end() [2/2]

auto Slic3r::MultiPoint::end ( ) const

inline

{ return points.end();   }

References points.

find_point() [1/2]

int Slic3r::MultiPoint::find_point

(

const Point &

point

)

const

{
    for (const Point &pt : this->points)
        if (pt == point)
            return int(&pt - &this->points.front());
    return -1;  // not found
}

References points.

Referenced by find_point().

Here is the caller graph for this function:

find_point() [2/2]

int Slic3r::MultiPoint::find_point	(	const Point &	point,
		const double	scaled_epsilon
	)		const

{
    if (scaled_epsilon == 0)
        return this->find_point(point);
 
    auto dist2_min = std::numeric_limits<double>::max();
    auto eps2      = scaled_epsilon * scaled_epsilon;
    int  idx_min  = -1;
    for (const Point &pt : this->points) {
        double d2 = (pt - point).cast<double>().squaredNorm();
        if (d2 < dist2_min) {
            idx_min = int(&pt - &this->points.front());
            dist2_min = d2;
        }
    }
    return dist2_min < eps2 ? idx_min : -1;
}

References find_point(), and points.

Here is the call graph for this function:

first_point()

const Point & Slic3r::MultiPoint::first_point ( ) const

inline

{ return this->front(); }

References front().

Referenced by Slic3r::connect_brim_lines(), Slic3r::Polyline::equally_spaced_points(), Slic3r::FFFSupport::LoopInterfaceProcessor::generate(), Slic3r::improve_ordering_by_two_exchanges_with_segment_flipping(), Slic3r::Polyline::is_straight(), Slic3r::need_wipe(), Slic3r::optimize_polylines_by_reversing(), and Slic3r::reconnect_polylines().

Here is the call graph for this function:

Here is the caller graph for this function:

front()

const Point & Slic3r::MultiPoint::front ( ) const

inline

{ return this->points.front(); }

Referenced by Slic3r::FFFTreeSupport::RichInterfacePlacer::add_point_as_influence_area(), Slic3r::FillAdaptive::connect_lines_using_hooks(), Slic3r::GCode::extrude_loop(), first_point(), Slic3r::inner_brim_area(), Slic3r::Algorithm::merge_expansions_into_expolygons(), Slic3r::mittered_offset_path_scaled(), libnest2d::shapelike::offset(), Slic3r::precompute_expolygon_distances(), Slic3r::GUI::MeshClipper::recalculate_triangles(), Slic3r::Arachne::WallToolPaths::stitchToolPaths(), and Slic3r::GUI::GLCanvas3D::update_sequential_clearance().

Here is the caller graph for this function:

has_duplicate_points()

bool Slic3r::MultiPoint::has_duplicate_points

(

)

const

{
    for (size_t i = 1; i < points.size(); ++i)
        if (points[i-1] == points[i])
            return true;
    return false;
}

References points.

Referenced by Slic3r::polylines_from_paths(), and Slic3r::traverse_graph_generate_polylines().

Here is the caller graph for this function:

is_valid()

bool Slic3r::MultiPoint::is_valid ( ) const

inline

{ return this->points.size() >= 2; }

Referenced by Slic3r::ExtrusionLoop::split_at(), Slic3r::ExtrusionLoop::split_at_vertex(), and Slic3r::PerimeterGenerator::thick_polyline_to_multi_path().

Here is the caller graph for this function:

operator=() [1/2]

MultiPoint & Slic3r::MultiPoint::operator= ( const MultiPoint &  other )

inline

{ points = other.points; return *this; }

References points.

operator=() [2/2]

MultiPoint & Slic3r::MultiPoint::operator= ( MultiPoint &&  other )

inline

{ points = std::move(other.points); return *this; }

References points.

remove_duplicate_points()

bool Slic3r::MultiPoint::remove_duplicate_points

(

)

{
    size_t j = 0;
    for (size_t i = 1; i < points.size(); ++i) {
        if (points[j] == points[i]) {
            // Just increase index i.
        } else {
            ++ j;
            if (j < i)
                points[j] = points[i];
        }
    }
    if (++ j < points.size()) {
        points.erase(points.begin() + j, points.end());
        return true;
    }
    return false;
}

References points.

Referenced by Slic3r::ExPolygonWithOffset::ExPolygonWithOffset(), Slic3r::_3DScene::extrusionentity_to_verts(), Slic3r::_3DScene::extrusionentity_to_verts(), Slic3r::_3DScene::extrusionentity_to_verts(), Slic3r::polylines_from_paths(), and Slic3r::traverse_graph_generate_polylines().

Here is the caller graph for this function:

reverse()

void Slic3r::MultiPoint::reverse ( )

inline

{ std::reverse(this->points.begin(), this->points.end()); }

Referenced by Slic3r::base_support_extend_infill_lines(), Slic3r::SupportSpotsGenerator::build_object_part_from_slice(), Slic3r::FFFTreeSupport::calculateMachineBorderCollision(), Slic3r::Polyline::clip_start(), Slic3r::SupportMaterialInternal::collect_bridging_perimeter_areas(), Slic3r::Fill::connect_base_support(), Slic3r::FillAdaptive::connect_lines_using_hooks(), priv::cut_surface(), Slic3r::GCode::extrude_multi_path(), Slic3r::GCode::extrude_path(), Slic3r::FFFSupport::LoopInterfaceProcessor::generate(), Slic3r::Polygon::make_clockwise(), Slic3r::Polygon::make_counter_clockwise(), Slic3r::FFFSupport::modulate_extrusion_by_overlapping_layers(), Slic3r::optimize_polylines_by_reversing(), Slic3r::reconnect_polylines(), Slic3r::ExtrusionPath::reverse(), Slic3r::take_limited(), and Slic3r::FFFSupport::tree_supports_generate_paths().

Here is the caller graph for this function:

rotate() [1/3]

void Slic3r::MultiPoint::rotate ( double  angle )

inline

{ this->rotate(cos(angle), sin(angle)); }

References Slic3r::angle(), cos(), rotate(), and sin().

Referenced by Slic3r::ExPolygonWithOffset::ExPolygonWithOffset(), Slic3r::ExPolygonWithOffset::ExPolygonWithOffset(), Slic3r::FillHoneycomb::_fill_surface_single(), Slic3r::get_arrange_poly(), Slic3r::ExPolygon::rotate(), rotate(), Slic3r::ExPolygon::rotate(), Slic3r::Print::sequential_print_horizontal_clearance_valid(), and Slic3r::ModelInstance::transform_polygon().

Here is the call graph for this function:

Here is the caller graph for this function:

rotate() [2/3]

void Slic3r::MultiPoint::rotate	(	double	angle,
		const Point &	center
	)

{
    double s = sin(angle);
    double c = cos(angle);
    for (Point &pt : points) {
        Vec2crd v(pt - center);
        pt(0) = (coord_t)round(double(center(0)) + c * v[0] - s * v[1]);
        pt(1) = (coord_t)round(double(center(1)) + c * v[1] + s * v[0]);
    }
}

References Slic3r::angle(), cos(), points, round(), and sin().

Here is the call graph for this function:

rotate() [3/3]

void Slic3r::MultiPoint::rotate	(	double	cos_angle,
		double	sin_angle
	)

{
    for (Point &pt : this->points) {
        double cur_x = double(pt(0));
        double cur_y = double(pt(1));
        pt(0) = coord_t(round(cos_angle * cur_x - sin_angle * cur_y));
        pt(1) = coord_t(round(cos_angle * cur_y + sin_angle * cur_x));
    }
}

References points, and round().

Here is the call graph for this function:

scale() [1/2]

void Slic3r::MultiPoint::scale

(

double

factor

)

{
    for (Point &pt : points)
        pt *= factor;
}

References points.

Referenced by Slic3r::FFFTreeSupport::RichInterfacePlacer::add_points_along_lines(), Slic3r::ExPolygon::scale(), Slic3r::ExPolygon::scale(), and Slic3r::ModelInstance::transform_polygon().

Here is the caller graph for this function:

scale() [2/2]

void Slic3r::MultiPoint::scale	(	double	factor_x,
		double	factor_y
	)

{
    for (Point &pt : points)
    {
    pt(0) = coord_t(pt(0) * factor_x);
    pt(1) = coord_t(pt(1) * factor_y);
    }
}

References points.

size()

size_t Slic3r::MultiPoint::size ( ) const

inline

{ return points.size(); }

Referenced by Slic3r::BuildVolume::BuildVolume(), Slic3r::GCode::_do_export(), Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::any_expolygon_contains(), Slic3r::avoid_perimeters_inner(), Slic3r::SeamPlacerImpl::calculate_polygon_angles_at_vertices(), Slic3r::Fill::connect_base_support(), Slic3r::connect_layer_slices(), Slic3r::FillAdaptive::connect_lines_using_hooks(), Slic3r::contour_distance(), Slic3r::contour_distance(), Slic3r::contour_distance2(), Slic3r::Geometry::convex_hull(), Slic3r::Geometry::convex_hull(), Slic3r::Geometry::convex_polygons_intersect(), Slic3r::create_boundary_infill_graph(), Slic3r::GUI::ImGuiWrapper::draw(), Slic3r::emit_loops_in_band(), Slic3r::FFFTreeSupport::ensure_maximum_distance_polyline(), Slic3r::expolygons_to_zpaths_shrunk(), Slic3r::find_first_different_vertex(), Slic3r::fuzzy_polygon(), priv::get_closest_point_index(), Slic3r::get_shortest_direction(), Slic3r::FillLightning::Layer::getBestGroundingLocation(), Slic3r::Geometry::rotcalip::Idx::inc(), Slic3r::BoundaryInfillGraph::interpolate_contour_point(), Slic3r::mark_boundary_segments_overlapping_infill(), Slic3r::ExtrusionPath::middle_point(), Slic3r::mittered_offset_path_scaled(), Slic3r::FFFTreeSupport::move_inside(), Slic3r::need_wipe(), Slic3r::Geometry::rotcalip::Idx::next(), Slic3r::Geometry::rotcalip::Idx::next_dir(), Slic3r::Voronoi::offset(), Slic3r::Arachne::PolygonsPointIndexSegmentLocator::operator()(), Slic3r::paths_touch(), Slic3r::polygons_match(), Slic3r::precompute_polygon_distances(), Slic3r::Geometry::rotcalip::Idx::prev_dir(), Slic3r::SeamPlacerImpl::process_perimeter_polygon(), Slic3r::GUI::MeshClipper::recalculate_triangles(), Slic3r::remove_duplicates(), Slic3r::Arachne::removeColinearEdges(), Slic3r::Arachne::removeDegenerateVerts(), Slic3r::FillLightning::Node::removeJunctionOverlap(), Slic3r::resample_polygon(), Slic3r::resample_polygon(), Slic3r::Arachne::simplify(), Slic3r::ExtrusionPath::size(), Slic3r::slice_region_by_vertical_lines(), Slic3r::smooth_compensation_banded(), Slic3r::smooth_outward(), Slic3r::smooth_outward(), Slic3r::Polyline::split_at(), Slic3r::Arachne::WallToolPaths::stitchToolPaths(), Slic3r::take(), Slic3r::take_ccw_full(), Slic3r::take_ccw_limited(), Slic3r::take_cw_full(), Slic3r::take_cw_limited(), Slic3r::take_limited(), priv::to_expoly(), Slic3r::to_polyline(), Slic3r::FFFSupport::tree_supports_generate_paths(), Slic3r::triangulate_wall(), and Slic3r::Wipe::wipe().

translate() [1/2]

void Slic3r::MultiPoint::translate

(

const Point &

vector

)

{
    for (Point &pt : points)
        pt += v;
}

References points.

translate() [2/2]

void Slic3r::MultiPoint::translate ( double  x, double  y  )

inline

{ this->translate(Point(coord_t(x), coord_t(y))); }

References translate().

Referenced by Slic3r::LinesBucket::curLines(), Slic3r::_3DScene::extrusionentity_to_verts(), Slic3r::_3DScene::extrusionentity_to_verts(), Slic3r::_3DScene::extrusionentity_to_verts(), Slic3r::get_arrange_poly(), priv::heal_dupl_inter(), Slic3r::Emboss::heal_shape(), priv::remove_self_intersections(), Slic3r::GCode::set_origin(), Slic3r::ExPolygon::translate(), translate(), Slic3r::AvoidCrossingPerimeters::travel_to(), and Slic3r::GCode::travel_to().

Here is the call graph for this function:

Here is the caller graph for this function:

visivalingam()

Points Slic3r::MultiPoint::visivalingam ( const Points &  pts, const double &  tolerance  )

static

{
    // Make sure there's enough points in "pts" to bother with simplification.
    assert(pts.size() >= 2);
     // Result object
    Points results;
     // Lambda to calculate effective area spanned by a point and its immediate 
    // successor + predecessor.
    auto effective_area = [pts](const size_t& curr_pt_idx, const size_t& prev_pt_idx, const size_t& next_pt_idx)->coordf_t {
        const Point& curr = pts[curr_pt_idx];
        const Point& prev = pts[prev_pt_idx];
        const Point& next = pts[next_pt_idx];
        // Use point objects as vector-distances
    const Vec2d curr_to_next = (next - curr).cast<double>();
    const Vec2d prev_to_next = (prev - curr).cast<double>();
        // Take cross product of these two vector distances
    return 0.50 * abs(cross2(curr_to_next, prev_to_next));
    };
     // We store the effective areas for each node
    std::vector<coordf_t> areas;
    areas.reserve(pts.size());
     // Construct the initial set of nodes. We will make a heap out of the "heap" vector using 
    // std::make_heap. node_list is used later.
    std::vector<vis_node*> node_list;
    node_list.resize(pts.size());
    std::vector<vis_node*> heap;
    heap.reserve(pts.size());
    for (size_t i = 1; i < pts.size() - 1; ++ i) {
        // Get effective area of current node.
        coordf_t area = effective_area(i, i - 1, i + 1);
        // If area is greater than some arbitrarily small value, use it.
        node_list[i] = new vis_node(i, i - 1, i + 1, area);
        heap.push_back(node_list[i]);
    }
     // Call std::make_heap, which uses the < operator by default to make "heap" into 
    // a binheap, sorted by the < operator we defind in the vis_node struct
    std::make_heap(heap.begin(), heap.end());
     // Start comparing areas. Set min_area to an outrageous value initially.
    double min_area = -std::numeric_limits<double>::max();
    while (!heap.empty()) {
         // Get current node.
        vis_node* curr = heap.front();
         // Pop node we just retrieved off the heap. pop_heap moves front element in vector
        // to the back, so we can call pop_back()
        std::pop_heap(heap.begin(), heap.end());
        heap.pop_back();
         // Sanity assert check
        assert(curr == node_list[curr->pt_idx]);
         // If the current pt'ss area is less than that of the previous pt's area
        // use the last pt's area instead. This ensures we don't elimate the current
        // point without eliminating the previous 
        min_area = std::max(min_area, curr->area);
         // Update prev
        vis_node* prev = node_list[curr->prev_idx];
        if(prev != nullptr){
            prev->next_idx = curr->next_idx;
            prev->area = effective_area(prev->pt_idx, prev->prev_idx, prev->next_idx);
            // For some reason, std::make_heap() is the fastest way to resort the heap. Probably needs testing.
            std::make_heap(heap.begin(), heap.end());
        }
         // Update next
        vis_node* next = node_list[curr->next_idx];
        if(next != nullptr){
            next->prev_idx = curr->prev_idx;
            next->area = effective_area(next->pt_idx, next->prev_idx, next->next_idx);
            std::make_heap(heap.begin(), heap.end());
        }
         areas[curr->pt_idx] = min_area;
        node_list[curr->pt_idx] = nullptr;
        delete curr;
    }
    // Clear node list and shrink_to_fit() (to free actual memory). Not necessary. Could be removed.
    node_list.clear();
    node_list.shrink_to_fit();
    // This lambda is how we test whether or not to keep a point.
    auto use_point = [areas, tolerance](const size_t& idx)->bool {
        assert(idx < areas.size());
        // Return true at front/back of path/areas
        if(idx == 0 || idx == areas.size() - 1){
            return true;
        }
        // Return true if area at idx is greater than minimum area to consider "valid"
        else{
            return areas[idx] > tolerance;
        }
    };
    // Use previously defined lambda to build results.
    for (size_t i = 0; i < pts.size(); ++i) {
        if (use_point(i)){
            results.push_back(pts[i]);
        }
    }
     // Check that results has at least two points
    assert(results.size() >= 2);
     // Return simplified vector of points
    return results;
}

References Slic3r::area(), Slic3r::vis_node::area, Slic3r::cross2(), Slic3r::vis_node::next_idx, Slic3r::vis_node::prev_idx, and Slic3r::vis_node::pt_idx.

Here is the call graph for this function:

Member Data Documentation

points

Points Slic3r::MultiPoint::points

Referenced by Slic3r::BuildVolume::BuildVolume(), Slic3r::ExPolygonsIndices::ExPolygonsIndices(), Slic3r::Polyline::Polyline(), Slic3r::GCode::_do_export(), Slic3r::GCode::_extrude(), Slic3r::FillHoneycomb::_fill_surface_single(), Slic3r::FillPlanePath::_fill_surface_single(), Slic3r::Print::_make_skirt(), Slic3r::sla::ConcaveHull::add_connector_rectangles(), Slic3r::FFFTreeSupport::RichInterfacePlacer::add_points_along_lines(), libnest2d::shapelike::addVertex(), Slic3r::any_expolygon_contains(), Slic3r::Polyline::append(), Slic3r::Polyline::append(), Slic3r::Polyline::append(), Slic3r::Polyline::append(), Slic3r::Polyline::append(), Slic3r::anonymous_namespace{SL1_SVG.cpp}::append_svg(), Slic3r::WipeTowerIntegration::append_tcr(), Slic3r::Polygon::area(), Slic3r::Polygon::area(), Slic3r::ExtrusionMultiPath::as_polyline(), Slic3r::MutablePolygon::assign(), begin(), begin(), boost::polygon::polygon_traits< Slic3r::ExPolygon >::begin_points(), boost::polygon::polygon_traits< Slic3r::Polygon >::begin_points(), bounding_box(), Slic3r::SeamPlacerImpl::calculate_polygon_angles_at_vertices(), cbegin(), cend(), Slic3r::Polygon::centroid(), Slic3r::chain_lines(), Slic3r::SupportSpotsGenerator::check_extrusion_entity_stability(), Slic3r::ExPolygon::clear(), Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox(), Slic3r::ClipperUtils::clip_clipper_polygon_with_subject_bbox(), Slic3r::Polyline::clip_end(), Slic3r::Polyline::clip_start(), Slic3r::SupportMaterialInternal::collect_bridging_perimeter_areas(), priv::collect_close_points(), Slic3r::ExtrusionPath::collect_points(), Slic3r::ExtrusionMultiPath::collect_points(), Slic3r::ExtrusionLoop::collect_points(), Slic3r::colored_points_to_polygon(), Slic3r::Polygon::concave_points(), Slic3r::Fill::connect_base_support(), Slic3r::connect_brim_lines(), Slic3r::Fill::connect_infill(), Slic3r::FillAdaptive::connect_lines_using_hooks(), Slic3r::contains(), Slic3r::contour_distance(), Slic3r::contours_simplified(), Slic3r::EdgeGrid::Grid::contours_simplified(), Slic3r::Geometry::convex_hull(), Slic3r::Geometry::convex_hulll(), Slic3r::Polygon::convex_points(), Slic3r::count_points(), Slic3r::count_points(), Slic3r::EdgeGrid::Grid::create(), Slic3r::EdgeGrid::Grid::create(), libnest2d::shapelike::create(), Slic3r::create_boundary_infill_graph(), Slic3r::Polygon::densify(), Slic3r::diff(), Slic3r::diff_ex(), Slic3r::diff_ex(), Slic3r::diff_pl(), Slic3r::diff_pl(), Slic3r::diff_pl(), Slic3r::distance_of_segmens(), Slic3r::sla::anonymous_namespace{Pad.cpp}::divide_blueprint(), Slic3r::Emboss::divide_segments_for_close_point(), Slic3r::Polygon::douglas_peucker(), Slic3r::GUI::ImGuiWrapper::draw(), Slic3r::FFFSupport::draw_perimeters(), Slic3r::elephant_foot_compensation(), Slic3r::emit_perimeter_prev_next_segment(), Slic3r::emit_perimeter_segment_on_vertical_line(), Slic3r::ExPolygon::empty(), empty(), end(), end(), boost::polygon::polygon_traits< Slic3r::ExPolygon >::end_points(), boost::polygon::polygon_traits< Slic3r::Polygon >::end_points(), Slic3r::FFFTreeSupport::ensure_maximum_distance_polyline(), Slic3r::Polyline::equally_spaced_points(), Slic3r::ExtrusionQualityEstimator::estimate_speed_from_extrusion_quality(), Slic3r::SupportSpotsGenerator::estimate_supports_malformations(), Slic3r::evaluate_support_arch_cost(), Slic3r::evaluate_support_arches(), Slic3r::ClipperZUtils::expolygons_to_zpaths(), Slic3r::Algorithm::expolygons_to_zpaths_expanded_opened(), Slic3r::expolygons_to_zpaths_shrunk(), Slic3r::Polyline::extend_end(), Slic3r::Polyline::extend_start(), Slic3r::SupportGridPattern::extract_support(), Slic3r::GCode::extrude_loop(), Slic3r::GCode::extrude_multi_path(), Slic3r::ExtrusionSimulator::extrude_to_accumulator(), Slic3r::extrusion_entities_append_loops(), Slic3r::extrusion_polyline_extents(), priv::fill_polygon_distances(), Slic3r::Print::finalize_first_layer_convex_hull(), priv::find_close_point(), Slic3r::find_first_different_vertex(), find_point(), find_point(), Slic3r::WipeTower::finish_layer(), Slic3r::Polygon::first_intersection(), Slic3r::ExtrusionPath::first_point(), Slic3r::NSVGUtils::flatten_cubic_bez(), Slic3r::foreach_vertex(), Slic3r::sla::foreach_vertex(), Slic3r::fuzzy_polygon(), Slic3r::FFFSupport::LoopInterfaceProcessor::generate(), Slic3r::get_all_polygons(), Slic3r::get_arrange_poly(), Slic3r::get_extents(), Slic3r::get_extents(), Slic3r::get_extents_rotated(), Slic3r::get_extents_rotated(), Slic3r::SVG::get_path_d(), Slic3r::get_polygon_vertex_inward_normal(), Slic3r::get_polygon_vertex_offset(), Slic3r::GUI::GLGizmoPainterBase::get_projected_mouse_positions(), Slic3r::FillLightning::Layer::getBestGroundingLocation(), Slic3r::FakeWipeTower::getFakeExtrusionPathsFromWipeTower(), has_duplicate_points(), Slic3r::has_duplicate_points(), Slic3r::has_duplicate_points(), Slic3r::has_duplicate_points(), Slic3r::FillAdaptive::has_no_collinear_lines(), Slic3r::GUI::GLModel::init_from(), priv::insert_edges(), priv::insert_edges(), Slic3r::Polygon::intersection(), Slic3r::intersection(), Slic3r::intersection_pl(), Slic3r::intersection_pl(), Slic3r::intersection_pl(), Slic3r::intersection_pl(), Slic3r::Polygon::intersections(), Slic3r::Geometry::is_ccw(), Slic3r::ExtrusionPath::is_closed(), Slic3r::Polyline::is_closed(), Slic3r::Arachne::ExtrusionLine::is_contour(), Slic3r::Polygon::is_counter_clockwise(), Slic3r::Polygon::is_valid(), Slic3r::SupportGridPattern::island_samples(), Slic3r::Polygon::last_point(), Slic3r::Polyline::last_point(), Slic3r::ExtrusionPath::last_point(), Slic3r::Polyline::leftmost_point(), Slic3r::Polygon::length(), Slic3r::Polyline::length(), Slic3r::Polyline::lines(), Slic3r::GUI::Plater::priv::load_model_objects(), Slic3r::make_circle_num_segments(), Slic3r::make_expolygons_simple(), Slic3r::make_fill_polylines(), Slic3r::make_wave(), Slic3r::makeGrid(), Slic3r::mark_boundary_segments_overlapping_infill(), Slic3r::ExtrusionPath::middle_point(), Slic3r::FFFSupport::modulate_extrusion_by_overlapping_layers(), Slic3r::Polygon::new_scale(), Slic3r::Polyline::new_scale(), Slic3r::Voronoi::offset(), Slic3r::offset(), Slic3r::offset(), Slic3r::offset_expolygon_inner(), Slic3r::operator!=(), Slic3r::operator!=(), Slic3r::ClipperUtils::ExPolygonProvider::iterator::operator*(), operator=(), Slic3r::Polygon::operator=(), Slic3r::Polyline::operator=(), operator=(), Slic3r::Polygon::operator=(), Slic3r::Polyline::operator=(), Slic3r::operator==(), Slic3r::operator==(), Slic3r::Polygon::operator[](), Slic3r::Polyline::operator[](), Slic3r::Polygon::operator[](), Slic3r::Polyline::operator[](), Slic3r::FillAdaptive::Intersection::other_hook(), Slic3r::ExPolygon::overlaps(), Slic3r::Polygon::parameter_by_length(), Slic3r::paths_touch(), Slic3r::Polygon::point_projection(), Slic3r::ExtrusionLoop::polygon(), Slic3r::MutablePolygon::polygon(), Slic3r::BoundingBox::polygon(), Slic3r::polygon_is_convex(), Slic3r::polygon_segment_append(), Slic3r::polygon_segment_append_reversed(), Slic3r::polygons_match(), Slic3r::polylines_from_paths(), Slic3r::precompute_polygon_distances(), Slic3r::Print::process(), Slic3r::sla::raster_to_polygons(), Slic3r::SL1_SVGReader::read(), Slic3r::reconnect_polylines(), Slic3r::remove_collinear(), remove_duplicate_points(), priv::remove_same_neighbor(), priv::remove_spikes_in_duplicates(), Slic3r::remove_sticks(), priv::remove_when_spike(), Slic3r::Arachne::removeColinearEdges(), Slic3r::Arachne::removeDegenerateVerts(), Slic3r::FillLightning::Node::removeJunctionOverlap(), Slic3r::resample_polygon(), libnest2d::shapelike::reserve(), Slic3r::anonymous_namespace{SL1.cpp}::rings_to_expolygons(), rotate(), rotate(), scale(), scale(), Slic3r::segment_length(), boost::polygon::polygon_mutable_traits< Slic3r::ExPolygon >::set_points(), boost::polygon::polygon_mutable_traits< Slic3r::Polygon >::set_points(), Slic3r::Polyline::simplify(), Slic3r::Polygon::simplify(), Slic3r::Arachne::simplify(), Slic3r::ExPolygon::simplify_p(), boost::polygon::polygon_traits< Slic3r::ExPolygon >::size(), boost::polygon::polygon_traits< Slic3r::Polygon >::size(), Slic3r::slice_region_by_vertical_lines(), Slic3r::ExtrusionLoop::split_at(), Slic3r::Polyline::split_at(), Slic3r::Polygon::split_at_index(), Slic3r::Polygon::split_at_vertex(), Slic3r::ExtrusionLoop::split_at_vertex(), Slic3r::GUI::ImGuiWrapper::suggest_location(), Slic3r::take(), Slic3r::take_ccw_full(), Slic3r::take_ccw_limited(), Slic3r::take_cw_full(), Slic3r::take_cw_limited(), Slic3r::take_limited(), Slic3r::GluTessWrapper::tesselate3d(), Slic3r::PerimeterGenerator::thick_polyline_to_multi_path(), Slic3r::to_lines(), Slic3r::to_lines(), Slic3r::to_lines(), Slic3r::to_lines(), Slic3r::to_lines(), Slic3r::to_linesf(), Slic3r::sla::AGGRaster< PixelRenderer, Renderer, Rasterizer, Scanline >::to_path(), Slic3r::to_points(), Slic3r::to_points(), Slic3r::to_points(), Slic3r::Arachne::to_polygon(), Slic3r::to_polygon(), Slic3r::NSVGUtils::to_polygons(), Slic3r::to_polyline(), Slic3r::to_polyline(), Slic3r::to_polylines(), Slic3r::to_polylines(), Slic3r::to_polylines(), Slic3r::to_polylines(), Slic3r::to_polylines(), Slic3r::SupportSpotsGenerator::to_short_lines(), Slic3r::Arachne::ExtrusionLine::toPolygon(), libnest2d::shapelike::toString(), Slic3r::anonymous_namespace{SL1_SVG.cpp}::transform(), translate(), Slic3r::AvoidCrossingPerimeters::travel_to(), Slic3r::traverse_graph_generate_polylines(), Slic3r::traverse_loops_classic(), Slic3r::traverse_pt(), Slic3r::FFFSupport::tree_supports_generate_paths(), Slic3r::Triangulation::triangulate(), Slic3r::Polygon::triangulate_convex(), Slic3r::triangulate_wall(), Slic3r::GUI::GLCanvas3D::update_sequential_clearance(), Slic3r::FFFTreeSupport::validate_range(), Slic3r::variable_offset_inner_raw(), Slic3r::variable_offset_outer_ex(), Slic3r::variable_offset_outer_raw(), Slic3r::wall_strip(), and Slic3r::Wipe::wipe().

---

The documentation for this class was generated from the following files:

• src/libslic3r/MultiPoint.hpp
• src/libslic3r/MultiPoint.cpp