From 2a0107467f19d3eadcad55ee62bdfd6e618bda32 Mon Sep 17 00:00:00 2001
From: Vojtech Bubnik <bubnikv@gmail.com>
Date: Mon, 8 Feb 2021 17:40:47 +0100
Subject: Fix of Hilbert Curve Infill: Unable to slice, PrusaSlicer not
 responding. #5771 Fixed by hard limiting the number of iterations of
 reorder_by_two_exchanges_with_segment_flipping()

---
 src/libslic3r/ShortestPath.cpp | 17 ++++++++++++++++-
 1 file changed, 16 insertions(+), 1 deletion(-)

diff --git a/src/libslic3r/ShortestPath.cpp b/src/libslic3r/ShortestPath.cpp
index 3d5903df1..09c3d2a36 100644
--- a/src/libslic3r/ShortestPath.cpp
+++ b/src/libslic3r/ShortestPath.cpp
@@ -1527,6 +1527,11 @@ static inline void do_crossover(const std::vector<FlipEdge> &edges_in, std::vect
 	assert(edges_in.size() == edges_out.size());
 }
 
+// Worst time complexity:    O(min(n, 100) * (n * log n + n^2)
+// Expected time complexity: O(min(n, 100) * (n * log n + k * n)
+// where n is the number of edges and k is the number of connection_lengths candidates after the first one
+// is found that improves the total cost.
+//FIXME there are likley better heuristics to lower the time complexity.
 static inline void reorder_by_two_exchanges_with_segment_flipping(std::vector<FlipEdge> &edges)
 {
 	if (edges.size() < 2)
@@ -1536,7 +1541,8 @@ static inline void reorder_by_two_exchanges_with_segment_flipping(std::vector<Fl
 	std::vector<FlipEdge> 					edges_tmp(edges);
 	std::vector<std::pair<double, size_t>>	connection_lengths(edges.size() - 1, std::pair<double, size_t>(0., 0));
 	std::vector<char>						connection_tried(edges.size(), false);
-	for (size_t iter = 0; iter < edges.size(); ++ iter) {
+	const size_t 							max_iterations = std::min(edges.size(), size_t(100));
+	for (size_t iter = 0; iter < max_iterations; ++ iter) {
 		// Initialize connection costs and connection lengths.
 		for (size_t i = 1; i < edges.size(); ++ i) {
 			const FlipEdge   	 &e1 = edges[i - 1];
@@ -1601,6 +1607,8 @@ static inline void reorder_by_two_exchanges_with_segment_flipping(std::vector<Fl
 	}
 }
 
+#if 0
+// Currently not used, too slow.
 static inline void reorder_by_three_exchanges_with_segment_flipping(std::vector<FlipEdge> &edges)
 {
 	if (edges.size() < 3) {
@@ -1683,6 +1691,7 @@ static inline void reorder_by_three_exchanges_with_segment_flipping(std::vector<
 		}
 	}
 }
+#endif
 
 typedef Eigen::Matrix<double, Eigen::Dynamic, Eigen::Dynamic, Eigen::DontAlign> Matrixd;
 
@@ -1754,6 +1763,8 @@ static inline std::pair<double, size_t> minimum_crossover_cost(
 	return std::make_pair(cost_min, flip_min);
 }
 
+#if 0
+// Currently not used, too slow.
 static inline void reorder_by_three_exchanges_with_segment_flipping2(std::vector<FlipEdge> &edges)
 {
 	if (edges.size() < 3) {
@@ -1850,8 +1861,11 @@ static inline void reorder_by_three_exchanges_with_segment_flipping2(std::vector
 		}
 	}
 }
+#endif
 
 // Flip the sequences of polylines to lower the total length of connecting lines.
+// Used by the infill generator if the infill is not connected with perimeter lines
+// and to order the brim lines.
 static inline void improve_ordering_by_two_exchanges_with_segment_flipping(Polylines &polylines, bool fixed_start)
 {
 #ifndef NDEBUG
@@ -1903,6 +1917,7 @@ static inline void improve_ordering_by_two_exchanges_with_segment_flipping(Polyl
 #endif /* NDEBUG */
 }
 
+// Used to optimize order of infill lines and brim lines.
 Polylines chain_polylines(Polylines &&polylines, const Point *start_near)
 {
 #ifdef DEBUG_SVG_OUTPUT
-- 
cgit v1.2.3