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>`.

Enumerations
enum	CGAL::Bisection_event { CGAL::CURRENT_DATA = 0 , CGAL::BAD_DATA , CGAL::ERROR_DATA , CGAL::FINAL_BAD_DATA }
	Enumeration of events during the bisection process. More...

Functions
template<typename InputData , typename GetSize , typename Simplify , typename Run , typename Notify >
int	CGAL::bisect_failures (const InputData &data, GetSize get_size, Simplify simplify, Run run, Notify notify)
	bisects input data by iteratively simplifying it to identify a failing case, from which no further elements can be removed while still failing.

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

Enumeration Type Documentation

◆ Bisection_event

enum CGAL::Bisection_event

#include <CGAL/bisect_failures.h>

Enumeration of events during the bisection process.

See also: bisect_failures

Enumerator
CURRENT_DATA	Current data being tested.
BAD_DATA	Data that reproduces the original failure.
ERROR_DATA	Data that causes a different failure.
FINAL_BAD_DATA	Minimal failing data that cannot be further simplified.

Function Documentation

◆ bisect_failures()

template<typename InputData , typename GetSize , typename Simplify , typename Run , typename Notify >

int CGAL::bisect_failures	(	const InputData &	data,
		GetSize	get_size,
		Simplify	simplify,
		Run	run,
		Notify	notify
	)

#include <CGAL/bisect_failures.h>

bisects input data by iteratively simplifying it to identify a failing case, from which no further elements can be removed while still failing.

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)
GetSize	Function object type, callable with a signature `std::size_t GetSize(const InputData& data)`
Simplify	Function object type, callable with a signature `bool Simplify(InputData& data, std::size_t start, std::size_t end)`
Run	Function object type, callable with a signature `int Run(const InputData& data)`
Notify	Function object type, callable with a signature `void Notify(const InputData& data, Bisection_event event)`

Parameters

data	The input data to bisect
get_size	Function that returns the "size" of the data (e.g., number of elements).
simplify	Function that simplifies the data by removing elements with indices in `[start, end)`. Should return `true` if simplification succeeded, `false` otherwise.
run	Function that tests the data. Should return 0 (`EXIT_SUCCESS`) on success, non-zero on failure. May also throw exceptions to indicate failure.
notify	Function that is called with the data at different stages. It can be used to save the data to a file or output. Its second parameter `event`, of type `Bisection_event`, 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 (by a call run(data)) to verify if it fails, and captures the failure pattern. If the run succeeds, returns EXIT_SUCCESS immediately.
Starts with a ratio of 0.5 (removing 50% of elements) and divides data into "buckets".
For each bucket,
- creates a simplified version of the data by removing that bucket, using simplify,
- call notify(data, CURRENT_DATA) where data is the simplified data,
- and tests the simplified version by a call run(data).
Then:
- If it fails with the same pattern as the original, calls notify(data, BAD_DATA) and restarts bisection with this smaller dataset and the same ratio.
- If it fails differently, calls notify(data, ERROR_DATA) and continues with the next bucket.
- If it succeeds, continue with 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).
Calls notify(data, FINAL_BAD_DATA) with the minimal failing case and return the result of run(data) on it.

Warning: CGAL::bisect_failures requires the tested code to be compiled with assertions enabled. That means NDEBUG and CGAL_NDEBUG should not be defined. If run fails with a segmentation fault, This function cannot catch it and will also crash.

Here is an example of how to use CGAL::bisect_failures:

  // 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, CGAL::Bisection_event event) {
    std::string prefix;
    switch(event) {
      case CGAL::BAD_DATA:
        prefix = "bad_data";
        break;
      case CGAL::FINAL_BAD_DATA:
        prefix = "final_bad_data";
        break;
      case CGAL::ERROR_DATA:
        prefix = "error_data";
        break;
      case CGAL::CURRENT_DATA:
        prefix = "current_data";
        break;
      default:
        CGAL_UNREACHABLE();
    }
    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 << std::endl;
    } else {
      std::cout << "Saved mesh with " << m.number_of_faces()
                << " faces to " << out_filename << std::endl;
    }
  };
 
  // Run bisection to find minimal failing case
  std::cout << "\n=== Starting bisection to find minimal failing case ===\n" << std::endl;
 
  int result = CGAL::bisect_failures(mesh_a, get_size, simplify, run, save);

Examples: STL_Extension/bisect_failures.cpp.

Classes

Typedefs

Enumerations

Functions