search

CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
4.98k stars 1.39k forks source link

Add a CMake option `CGAL_ENABLE_EXPENSIVE_ASSERTIONS` (was "Degenerated `min_rectangle_2` on quasi-rectangle polygons.") #5075

Open nojhan opened 4 years ago

nojhan commented 4 years ago

Issue Details

While using min_rectangle_2 on some quasi-rectangle polygons, the output is not a rectangle but a degenerated set of 4 points, two pairs of which are equals.

A simple example is a polygon having two identical points, but I don't know if that's even considered as matching the preconditions, so I'll keep that one for later.

Anyway, there is some (supposedly) good quasi-rectangle polygons of 4 points which ends in a degenerated rectangle (see below).

Source Code

The following minimal test have been inspired from Bounding_volumes/test/Bounding_volumes/minimum_enclosing_quadrilateral_2_test_C.cpp and can be build with the same command that the one produced by cmake on this file (see a minimal build script below).

// Copyright (c) 2020 Thales group
//
// Author: Johann Dreo <johann.dreo@thalesgroup.com>

#include <iostream>
#include <cassert>

#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/min_quadrilateral_2.h>

typedef CGAL::Cartesian<double> Kernel;
typedef Kernel::Point_2         Point_2;
typedef CGAL::Polygon_2<Kernel> Polygon_2;

template<class IT>
bool no_duplicates(IT begin, IT end)
{
    for(auto ip = begin; ip != end; ip++) {
        auto in = ip; in++;
        if( std::find(in, end, *ip) != end ) {
            return false;
        }
    }
    return true;
}

int main()
{
  CGAL::set_pretty_mode(std::cout);

  Polygon_2 p;
  p.push_back(Point_2(-793712.4828,3944967.931));
  p.push_back(Point_2(-793737.6144,3944812.829));
  p.push_back(Point_2(-794069.5283,3944825.442));
  p.push_back(Point_2(-794044.3884,3944980.544));
  std::cout << "Input:" << std::endl << p << std::endl;

  Polygon_2 r;
  CGAL::min_rectangle_2(p.vertices_begin(), p.vertices_end(), std::back_inserter(r));
  std::cout << "Min_rectangle:" << std::endl << r << std::endl;

  bool no_duplicated_points = no_duplicates(r.vertices_begin(), r.vertices_end());
  if(not no_duplicated_points) {
    std::cout << "ERROR: duplicated points" << std::endl;
    assert(no_duplicated_points); // FAIL
  }

  return 0;
}

I had no success trying to bisect this bug, because of the drastic changes in the build system.

Minimal build & check script:

#!/bin/sh
mkdir -p build/
cd build/
(/usr/bin/c++ -DCGAL_EIGEN3_ENABLED -DCGAL_USE_CORE=1 -DCGAL_USE_GMPXX=1 -I./cgal/build/include -I./cgal/AABB_tree/include -I./cgal/Advancing_front_surface_reconstruction/include -I./cgal/Algebraic_foundations/include -I./cgal/Algebraic_kernel_d/include -I./cgal/Algebraic_kernel_for_circles/include -I./cgal/Algebraic_kernel_for_spheres/include -I./cgal/Alpha_shapes_2/include -I./cgal/Alpha_shapes_3/include -I./cgal/Apollonius_graph_2/include -I./cgal/Arithmetic_kernel/include -I./cgal/Arrangement_on_surface_2/include -I./cgal/BGL/include -I./cgal/Barycentric_coordinates_2/include -I./cgal/Boolean_set_operations_2/include -I./cgal/Bounding_volumes/include -I./cgal/Box_intersection_d/include -I./cgal/CGAL_Core/include -I./cgal/CGAL_ImageIO/include -I./cgal/CGAL_ipelets/include -I./cgal/Cartesian_kernel/include -I./cgal/Circular_kernel_2/include -I./cgal/Circular_kernel_3/include -I./cgal/Circulator/include -I./cgal/Classification/include -I./cgal/Combinatorial_map/include -I./cgal/Cone_spanners_2/include -I./cgal/Convex_decomposition_3/include -I./cgal/Convex_hull_2/include -I./cgal/Convex_hull_3/include -I./cgal/Convex_hull_d/include -I./cgal/Distance_2/include -I./cgal/Distance_3/include -I./cgal/Envelope_2/include -I./cgal/Envelope_3/include -I./cgal/Filtered_kernel/include -I./cgal/Generalized_map/include -I./cgal/Generator/include -I./cgal/Geomview/include -I./cgal/GraphicsView/include -I./cgal/HalfedgeDS/include -I./cgal/Hash_map/include -I./cgal/Heat_method_3/include -I./cgal/Homogeneous_kernel/include -I./cgal/Hyperbolic_triangulation_2/include -I./cgal/Inscribed_areas/include -I./cgal/Installation/include -I./cgal/Interpolation/include -I./cgal/Intersections_2/include -I./cgal/Intersections_3/include -I./cgal/Interval_skip_list/include -I./cgal/Interval_support/include -I./cgal/Inventor/include -I./cgal/Jet_fitting_3/include -I./cgal/Kernel_23/include -I./cgal/Kernel_d/include -I./cgal/LEDA/include -I./cgal/Linear_cell_complex/include -I./cgal/Matrix_search/include -I./cgal/Mesh_2/include -I./cgal/Mesh_3/include -I./cgal/Mesher_level/include -I./cgal/Minkowski_sum_2/include -I./cgal/Minkowski_sum_3/include -I./cgal/Modifier/include -I./cgal/Modular_arithmetic/include -I./cgal/Nef_2/include -I./cgal/Nef_3/include -I./cgal/Nef_S2/include -I./cgal/NewKernel_d/include -I./cgal/Number_types/include -I./cgal/OpenNL/include -I./cgal/Optimal_bounding_box/include -I./cgal/Optimal_transportation_reconstruction_2/include -I./cgal/Optimisation_basic/include -I./cgal/Partition_2/include -I./cgal/Periodic_2_triangulation_2/include -I./cgal/Periodic_3_mesh_3/include -I./cgal/Periodic_3_triangulation_3/include -I./cgal/Periodic_4_hyperbolic_triangulation_2/include -I./cgal/Point_set_2/include -I./cgal/Point_set_3/include -I./cgal/Point_set_processing_3/include -I./cgal/Poisson_surface_reconstruction_3/include -I./cgal/Polygon/include -I./cgal/Polygon_mesh_processing/include -I./cgal/Polygonal_surface_reconstruction/include -I./cgal/Polyhedron/include -I./cgal/Polyhedron_IO/include -I./cgal/Polyline_simplification_2/include -I./cgal/Polynomial/include -I./cgal/Polytope_distance_d/include -I./cgal/Principal_component_analysis/include -I./cgal/Principal_component_analysis_LGPL/include -I./cgal/Profiling_tools/include -I./cgal/Property_map/include -I./cgal/QP_solver/include -I./cgal/Random_numbers/include -I./cgal/Ridges_3/include -I./cgal/STL_Extension/include -I./cgal/Scale_space_reconstruction_3/include -I./cgal/SearchStructures/include -I./cgal/Segment_Delaunay_graph_2/include -I./cgal/Segment_Delaunay_graph_Linf_2/include -I./cgal/Set_movable_separability_2/include -I./cgal/Shape_detection/include -I./cgal/Skin_surface_3/include -I./cgal/Snap_rounding_2/include -I./cgal/Solver_interface/include -I./cgal/Spatial_searching/include -I./cgal/Spatial_sorting/include -I./cgal/Straight_skeleton_2/include -I./cgal/Stream_lines_2/include -I./cgal/Stream_support/include -I./cgal/Subdivision_method_3/include -I./cgal/Surface_mesh/include -I./cgal/Surface_mesh_approximation/include -I./cgal/Surface_mesh_deformation/include -I./cgal/Surface_mesh_parameterization/include -I./cgal/Surface_mesh_segmentation/include -I./cgal/Surface_mesh_shortest_path/include -I./cgal/Surface_mesh_simplification/include -I./cgal/Surface_mesh_skeletonization/include -I./cgal/Surface_mesh_topology/include -I./cgal/Surface_mesher/include -I./cgal/Surface_sweep_2/include -I./cgal/TDS_2/include -I./cgal/TDS_3/include -I./cgal/Testsuite/include -I./cgal/Tetrahedral_remeshing/include -I./cgal/Three/include -I./cgal/Triangulation/include -I./cgal/Triangulation_2/include -I./cgal/Triangulation_3/include -I./cgal/Union_find/include -I./cgal/Visibility_2/include -I./cgal/Voronoi_diagram_2/include -I./cgal/build/test/Bounding_volumes -isystem /usr/include/eigen3 -g -o minimum_enclosing_quadrilateral_2_check.cpp.o -c ./cgal/Bounding_volumes/test/Bounding_volumes/minimum_enclosing_quadrilateral_2_check.cpp && /usr/bin/c++ -g minimum_enclosing_quadrilateral_2_check.cpp.o -o minimum_enclosing_quadrilateral_2_check /usr/lib/x86_64-linux-gnu/libgmpxx.so /usr/lib/x86_64-linux-gnu/libmpfr.so /usr/lib/x86_64-linux-gnu/libgmp.so) || exit 127

./minimum_enclosing_quadrilateral_2_check || exit 100

Environment

nojhan commented 4 years ago

Note: passing a convex_hull_2 instead of the initial polygon solves the issue.

However, I don't know why the clockwise precondition checks fails to detect the problem.

MaelRL commented 4 years ago

The precondition did not fail because it is an expensive precondition, which are not enabled by default, even in debug mode. You can enable expensive assertions with:

#define CGAL_CHECK_EXPENSIVE

and your input will indeed fail:

CGAL error: precondition violation!
Expression : orientation_2(f, l, t) == COUNTERCLOCKWISE
nojhan commented 4 years ago

I understand the rationale. However, as a naive user I would have expected a Debug build to include expensive assertions, especially given that there is a CMake warning already in that mode. Maybe adding a CMake ENABLE_EXPENSIVE_ASSERTIONS option would be a good compromise.

lrineau commented 4 years ago

I understand the rationale. However, as a naive user I would have expected a Debug build to include expensive assertions, especially given that there is a CMake warning already in that mode. Maybe adding a CMake ENABLE_EXPENSIVE_ASSERTIONS option would be a good compromise.

It should be prefixed with CGAL, so CGAL_ENABLE_EXPENSIVE_ASSERTIONS.

@maxGimeno