Classes
struct	CGAL::Compact
	`Compact` is a tag class. More...

struct	CGAL::Fast
	`Fast` is a tag class. More...

class	CGAL::Fourtuple< T >
	The `Fourtuple` class stores a homogeneous (same type) fourtuple of objects of type `T`. More...

struct	CGAL::Location_policy< Tag >
	`Location_policy` is a policy class which can be used to specify a trade-off between memory usage and time complexity for the point location strategy used in a data-structure. More...

class	CGAL::Sixtuple< T >
	The `Sixtuple` class stores a homogeneous (same type) sixtuple of objects of type `T`. More...

struct	CGAL::Boolean_tag< value >
	Depending on `bool value` the class `Boolean_tag` indicates that something is `true` or `false` respectively. More...

struct	CGAL::Null_functor
	Class indicating the absence of a functor. More...

struct	CGAL::Sequential_tag
	Tag used to disable concurrency. More...

struct	CGAL::Parallel_tag
	Tag used to enable concurrency. More...

struct	CGAL::Parallel_if_available_tag
	This tag is a convenience typedef to `Parallel_tag` if the third party library Intel TBB has been found and linked, and to `Sequential_tag` otherwise. More...

struct	CGAL::Null_tag
	General tag indicating that non of any other possible tags is valid. More...

struct	CGAL::Manifold_tag
	The class `Manifold_tag` is a tag class used to monitor the surface meshing algorithm. More...

struct	CGAL::Manifold_with_boundary_tag
	The class `Manifold_with_boundary_tag` is a tag class used to monitor the surface meshing algorithm. More...

struct	CGAL::Non_manifold_tag
	The class `Non_manifold_tag` is a tag class used to monitor the surface meshing algorithm. More...

class	CGAL::Threetuple< T >

class	CGAL::Twotuple< T >
	The `Twotuple` class stores a homogeneous (same type) pair of objects of type `T`. More...

class	CGAL::Uncertain< T >
	An object of the class `Uncertain` represents an uncertainty on the value of type `T`. More...

class	CGAL::Quadruple< T1, T2, T3, T4 >
	The Quadruple class is an extension of `std::pair`. More...

class	CGAL::Triple< T1, T2, T3 >
	The Triple class is an extension of `std::pair`. More...

Typedefs
typedef Location_policy< Compact >	CGAL::Compact_location
	A typedef to `Location_policy<Compact>`.

typedef Location_policy< Fast >	CGAL::Fast_location
	A typedef to `Location_policy<Fast>`.

typedef CGAL::Boolean_tag< false >	CGAL::Tag_false
	The typedef `Tag_false` is `Boolean_tag<false>`.

typedef CGAL::Boolean_tag< true >	CGAL::Tag_true
	The typedef `Tag_true` is `Boolean_tag<true>`.

Functions
template<typename InputData , typename GetSizeFn , typename SimplifyFn , typename RunFn , typename SaveFn >
int	CGAL::bisect_failures (const InputData &data, GetSizeFn get_size_fn, SimplifyFn simplify_fn, RunFn run_fn, SaveFn save_fn)
	Bisects input data by iteratively simplifying it to identify the minimal failing case.

Typedef Documentation

◆ Compact_location

typedef Location_policy<Compact> CGAL::Compact_location

#include <CGAL/Location_policy.h>

A typedef to Location_policy<Compact>.

See also: Compact; Fast; Location_policy; Fast_location

◆ Fast_location

typedef Location_policy<Fast> CGAL::Fast_location

#include <CGAL/Location_policy.h>

A typedef to Location_policy<Fast>.

See also: Compact; Fast; Location_policy; Compact_location

◆ Tag_false

typedef CGAL::Boolean_tag<false> CGAL::Tag_false

#include <CGAL/tags.h>

The typedef Tag_false is Boolean_tag<false>.

It is used to indicate, for example, that a certain feature is not available in a class.

See also: CGAL::Boolean_tag<bool value>; CGAL::Tag_true

◆ Tag_true

typedef CGAL::Boolean_tag<true> CGAL::Tag_true

#include <CGAL/tags.h>

The typedef Tag_true is Boolean_tag<true>.

It is used to indicate, for example, that a certain feature is available in a class.

See also: CGAL::Boolean_tag<bool value>; CGAL::Tag_false

Function Documentation

◆ bisect_failures()

template<typename InputData , typename GetSizeFn , typename SimplifyFn , typename RunFn , typename SaveFn >

int CGAL::bisect_failures	(	const InputData &	data,
		GetSizeFn	get_size_fn,
		SimplifyFn	simplify_fn,
		RunFn	run_fn,
		SaveFn	save_fn
	)

#include <CGAL/bisect_failures.h>

Bisects input data by iteratively simplifying it to identify the minimal failing case.

This debugging utility helps identify minimal test cases when complex input data causes failures. It works by iteratively simplifying the data and testing whether the failure persists, using a bisection-like approach to narrow down to the smallest failing case.

The algorithm divides the input data into "buckets" and systematically removes each bucket to test if the failure persists. It starts with a coarse granularity (ratio=0.5, removing half the elements) and automatically becomes more fine-grained (dividing ratio by 2) when no fault is found. When a failure is found, it restarts the bisection with the smaller failing data, progressively narrowing down to the minimal case.

Template Parameters

InputData	The type of input data to bisect (must be copyable and assignable)
GetSizeFn	Function object type: `std::size_t GetSizeFn(const InputData& data)`
SimplifyFn	Function object type: `bool SimplifyFn(InputData& data, std::size_t start, std::size_t end)`
RunFn	Function object type: `int RunFn(const InputData& data)`
SaveFn	Function object type: `void SaveFn(const InputData& data, const std::string& filename_prefix)`

Parameters

data	The input data to bisect
get_size_fn	Function that returns the "size" of the data (e.g., number of elements).
simplify_fn	Function that simplifies the data by removing elements from `[start, end)`. Should return `true` if simplification succeeded, `false` otherwise.
run_fn	Function that tests the data. Should return 0 (`EXIT_SUCCESS`) on success, non-zero on failure. May also throw exceptions to indicate failure.
save_fn	Function that saves the data to a file or output. Its second parameter (`filename_prefix`) indicates the context (e.g., "bad", "final_bad", "error", "current") and can be used to name the output accordingly.

Returns: Exit code: 0 (EXIT_SUCCESS) if no failures found, non-zero otherwise

The algorithm:

Tests the full data first to verify it fails and capture the failure pattern
Starts with a ratio of 0.5 (removing 50% of elements) and divides data into "buckets"
For each bucket, creates a simplified version by removing that portion
Tests the simplified version with run_fn
If it fails with the same pattern as the original, saves it as "bad" and restarts bisection with this smaller dataset
If it succeeds or fails differently, tries the next bucket
After a complete pass with no matching failures found, reduces the ratio by half (0.5 → 0.25 → 0.125...)
Repeats until no further simplification is possible (minimal failing case found)
Saves the minimal failing case as "final_bad" and returns its exit code

  // Define the callbacks for bisect_failures
 
  auto get_size = [](const Mesh& m) -> std::size_t {
    return m.number_of_faces();
  };
 
  auto simplify = [](Mesh& m, int start, int end) -> bool {
    for(auto i = end - 1; i >= start; --i) {
      const auto f = m.faces().begin() + i;
      CGAL::Euler::remove_face(halfedge(*f, m), m);
    }
 
    return m.is_valid();
  };
 
  auto run = [&mesh_b](Mesh& mesh) -> int {
    return CGAL::Polygon_mesh_processing::clip(mesh, mesh_b) ? EXIT_SUCCESS : EXIT_FAILURE;
  };
 
  auto save = [](const Mesh& m, const std::string& prefix) {
    std::string out_filename = prefix + ".off";
    if(!CGAL::IO::write_polygon_mesh(out_filename, m)) {
      std::cerr << "Warning: Could not save mesh to " << out_filename << "\n";
    } else {
      std::cout << "Saved mesh with " << m.number_of_faces()
                << " faces to " << out_filename << "\n";
    }
  };
 
  // Run bisection to find minimal failing case
  std::cout << "\n=== Starting bisection to find minimal failing case ===\n\n";
 
  int result = CGAL::bisect_failures(mesh_a, get_size, simplify, run, save);

Examples: STL_Extension/bisect_failures.cpp.

Classes

Typedefs