ShortestPath.cpp File Reference

#include "ExtrusionEntity.hpp"
#include <vector>
#include <utility>
#include <cstddef>
#include "Point.hpp"
#include <limits>
#include <algorithm>
#include <memory>
#include "ExPolygon.hpp"
#include "BoundingBox.hpp"
#include <Eigen/Core>
#include "Polyline.hpp"
#include <iterator>
#include "Line.hpp"
#include "libslic3r.h"
#include "ShortestPath.hpp"
#include "ExtrusionEntityCollection.hpp"
#include "KDTreeIndirect.hpp"
#include "MutablePriorityQueue.hpp"
#include "Print.hpp"
#include "GCode/OrderingStrategies.hpp"
#include <array>
#include <cmath>
#include <cassert>
#include <deque>
#include "MultiMaterialSegmentation.hpp"

Include dependency graph for ShortestPath.cpp:

Go to the source code of this file.

Classes
class	Slic3r::NearestPoints< K >
struct	Slic3r::FlipEdge
struct	Slic3r::ConnectionCost
class	Slic3r::FourOptCosts

Namespaces
namespace	Slic3r
	|/ Copyright (c) Prusa Research 2020 - 2023 Enrico Turri @enricoturri1966 |/ |/ PrusaSlicer is released under the terms of the AGPLv3 or higher |/

Typedefs
typedef Eigen::Matrix< double, Eigen::Dynamic, Eigen::Dynamic, Eigen::DontAlign >	Slic3r::Matrixd

Functions
static bool	Slic3r::extrusion_entity_has_endpoints (const ExtrusionEntity *entity)
template<typename EndPointType, typename KDTreeType, typename CouldReverseFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_closest_point (std::vector< EndPointType > &end_points, KDTreeType &kdtree, CouldReverseFunc &could_reverse_func, EndPointType &first_point)
static std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_exact (const std::vector< Vec2d > &end_points, const std::vector< char > &could_reverse, const Vec2d *start)
template<typename PointType, typename SegmentEndPointFunc, bool REVERSE_COULD_FAIL, typename CouldReverseFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_greedy_constrained_reversals_ (SegmentEndPointFunc end_point_func, CouldReverseFunc could_reverse_func, size_t num_segments, const PointType *start_near)
template<typename QueueType, typename KDTreeType, typename ChainsType, typename EndPointType>
void	Slic3r::update_end_point_in_queue (QueueType &queue, const KDTreeType &kdtree, ChainsType &chains, std::vector< EndPointType > &end_points, EndPointType &end_point, size_t first_point_idx, const EndPointType *first_point)
template<typename PointType, typename SegmentEndPointFunc, bool REVERSE_COULD_FAIL, typename CouldReverseFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_greedy_constrained_reversals2_ (SegmentEndPointFunc end_point_func, CouldReverseFunc could_reverse_func, size_t num_segments, const PointType *start_near)
template<typename PointType, typename SegmentEndPointFunc, typename CouldReverseFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_greedy_constrained_reversals (SegmentEndPointFunc end_point_func, CouldReverseFunc could_reverse_func, size_t num_segments, const PointType *start_near)
template<typename PointType, typename SegmentEndPointFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_greedy (SegmentEndPointFunc end_point_func, size_t num_segments, const PointType *start_near)
template<typename PointType, typename SegmentEndPointFunc, typename CouldReverseFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_greedy_constrained_reversals2 (SegmentEndPointFunc end_point_func, CouldReverseFunc could_reverse_func, size_t num_segments, const PointType *start_near)
template<typename PointType, typename SegmentEndPointFunc>
std::vector< std::pair< size_t, bool > >	Slic3r::chain_segments_greedy2 (SegmentEndPointFunc end_point_func, size_t num_segments, const PointType *start_near)
static void	Slic3r::improve_chain_by_local_search (std::vector< std::pair< size_t, bool > > &chain, const std::vector< Vec2d > &end_points, const std::vector< char > &could_reverse, const Vec2d *start_near)
static std::vector< std::pair< size_t, bool > >	Slic3r::chain_nearest_next (const std::vector< Vec2d > &end_points, const std::vector< char > &could_reverse, const Vec2d &start)
static double	Slic3r::chain_travel (const std::vector< std::pair< size_t, bool > > &chain, const std::vector< Vec2d > &end_points, const Vec2d &start)
template<typename EntityPtr>
static std::vector< std::pair< size_t, bool > >	Slic3r::chain_extrusion_entities_impl (const std::vector< EntityPtr > &entities, const Point *start_near, bool improve=false)
std::vector< std::pair< size_t, bool > >	Slic3r::chain_extrusion_entities (std::vector< ExtrusionEntity * > &entities, const Point *start_near)
template<typename EntityPtr>
static void	Slic3r::remove_entities_without_endpoints (std::vector< EntityPtr > &entities)
void	Slic3r::reorder_extrusion_entities (std::vector< ExtrusionEntity * > &entities, const std::vector< std::pair< size_t, bool > > &chain)
void	Slic3r::chain_and_reorder_extrusion_entities (std::vector< ExtrusionEntity * > &entities, const Point &start_near)
void	Slic3r::chain_and_reorder_extrusion_entities (std::vector< ExtrusionEntity * > &entities, const Point *start_near)
void	Slic3r::chain_and_reorder_extrusion_entities (std::vector< const ExtrusionEntity * > &entities, const Point &start_near, std::vector< std::unique_ptr< ExtrusionEntity > > &reversed_clones)
std::vector< std::pair< size_t, bool > >	Slic3r::chain_extrusion_paths (std::vector< ExtrusionPath > &extrusion_paths, const Point *start_near)
void	Slic3r::reorder_extrusion_paths (std::vector< ExtrusionPath > &extrusion_paths, const std::vector< std::pair< size_t, bool > > &chain)
void	Slic3r::chain_and_reorder_extrusion_paths (std::vector< ExtrusionPath > &extrusion_paths, const Point *start_near)
std::vector< size_t >	Slic3r::chain_expolygons (const ExPolygons &input_exploy)
std::vector< size_t >	Slic3r::chain_points (const Points &points, const Point *start_near)
static bool	Slic3r::improve_cycle_by_or_opt (std::vector< size_t > &path, const Points &points)
std::vector< size_t >	Slic3r::chain_points_with_postprocessing (const Points &points, const Point *start_near)
static ConnectionCost	Slic3r::operator- (const ConnectionCost &lhs, const ConnectionCost &rhs)
static std::pair< double, size_t >	Slic3r::minimum_crossover_cost (const std::vector< FlipEdge > &edges, const std::pair< size_t, size_t > &span1, const ConnectionCost &cost1, const std::pair< size_t, size_t > &span2, const ConnectionCost &cost2, const std::pair< size_t, size_t > &span3, const ConnectionCost &cost3, const double cost_current)
static void	Slic3r::do_crossover (const std::vector< FlipEdge > &edges_in, std::vector< FlipEdge > &edges_out, const std::pair< size_t, size_t > &span1, const std::pair< size_t, size_t > &span2, const std::pair< size_t, size_t > &span3, size_t i)
static void	Slic3r::reorder_by_two_exchanges_with_segment_flipping (std::vector< FlipEdge > &edges)
static void	Slic3r::improve_ordering_by_two_exchanges_with_segment_flipping (Polylines &polylines, bool fixed_start)
Polylines	Slic3r::chain_polylines (Polylines &&polylines, const Point *start_near)
std::vector< const PrintInstance * >	Slic3r::chain_print_object_instances (const std::vector< const PrintObject * > &print_objects, const Point *start_near)
std::vector< const PrintInstance * >	Slic3r::chain_print_object_instances (const Print &print)
Polylines	Slic3r::chain_lines (const std::vector< Line > &lines, const double point_distance_epsilon)