CGAL::do_intersect asserts if polygons wont intersect

[mmertama]

Issue Details

In case the polygons do not intersect (they are adjacent) like:

{
{{-832, 0},{-832, -192},{-768, -320},{-768, -400},{-736, -448},{-608, -448},{-576, -400},{-576, -344},{-475.6078, -24},{-480, -24},{-656, 48},{-720, 224},{-720, 288},{-720, 320},{-808, 352},{-808, 224},{-808, 128}}
and
{{-475.6078, -24},{-576, -344},{-256, -128},{-352, -24}}
};

Source Code

That is quite easy to spot:
... CGAL/Arr_segment_traits_2.h

line 722:

  // Intersect the two supporting lines.
  auto res = kernel.intersect_2_object()(cv1.line(), cv2.line());
  CGAL_assertion(bool(res)); 

Call stack:

 
std::__1::back_insert_iterator
std::__1::back_insert_iterator
CGAL::Surface_sweep_2::Random_access_output_iterator
CGAL::Surface_sweep_2::Surface_sweep_2
CGAL::Surface_sweep_2::Surface_sweep_2
CGAL::Surface_sweep_2::Surface_sweep_2
CGAL::Surface_sweep_2::No_intersection_surface_sweep_2
void CGAL::Surface_sweep_2::No_intersection_surface_sweep_2
void CGAL::overlay
CGAL::Gps_on_surface_base_2
CGAL::Gps_on_surface_base_2
bool CGAL::s_do_intersect
bool CGAL::s_do_intersect
bool CGAL::do_intersect

Environment

• Mac
• Compiler: Clang
• debug
• Specific flags:
• CGAL version: 6.0.1
• Boost version: 1.87.0
• Other libraries versions if used (Eigen, TBB, etc.):

[mmertama]

.... using CGAL::Exact_predicates_inexact_constructions_kernel, when using CGAL::Exact_predicates_exact_constructions_kernel it wont crash (at least with precision of numbers given above. )

[efifogel]

You must use CGAL::Exact_predicates_exact_constructions_kernel ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Sun, 4 May 2025 at 17:20, Markus Mertama ***@***.***> wrote: *mmertama* left a comment (CGAL/cgal#8873) <#8873 (comment)> .... using CGAL::Exact_predicates_inexact_constructions_kernel — Reply to this email directly, view it on GitHub <#8873 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOCA6KDCJSGCW75AS7T24YO3VAVCNFSM6AAAAAB4M6IPYWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQNBZGI2DOMJRHE> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[mmertama]

I did not spot that in the documentation, there should be a static_assert/concept/SFINAE to tell compile time that some template parameters are not working.

[efifogel]

No, there shouldn't. You can use an inexact predicate kernel at your own risk. I should have wrote: => You probably should use CGAL::Exact_predicates_exact_constructions_kernel in this case. In some cases the user might be certain that an inexact kernel suffices... ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Sun, 4 May 2025 at 20:10, Markus Mertama ***@***.***> wrote: *mmertama* left a comment (CGAL/cgal#8873) <#8873 (comment)> I did not spot that in the documentation, there should be a static_assert/concept/SFINAE to tell compile time that some template parameters are not working. — Reply to this email directly, view it on GitHub <#8873 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOHSDNA2PUIYDI356LL24ZCW3AVCNFSM6AAAAAB4M6IPYWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQNBZGMYTQOJZHA> . You are receiving this because you commented.Message ID: ***@***.***>

[afabri]

What about a static_warning ? I think we have that at some places.

[mmertama]

I supposed that would be sufficient, I wasted hours to figure out the reason - the runtime error wont provide any hint why it asserted.

[efifogel]

I guess it's not a bad idea; however, 1. it should be a warning dedicated to potential risk caused by imprecision that the user can suppress via a cmake flag with a somehow a distinction between epic, epec, and epec_with sqrt, and 2. it should apply to ALL constructs and functions of CGAL that are sensitive to imprecision ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Mon, 5 May 2025 at 09:58, Andreas Fabri ***@***.***> wrote: *afabri* left a comment (CGAL/cgal#8873) <#8873 (comment)> What about a static_warning ? I think we have that at some places. — Reply to this email directly, view it on GitHub <#8873 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOEYH5XWYNENITJKLLT244DXVAVCNFSM6AAAAAB4M6IPYWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQNJQGA4DAMJYGM> . You are receiving this because you commented.Message ID: ***@***.***>

[afabri]

And it is not only a question of kernel choice. If you use Simple_cartesian<Gmqp> it will be also ok.

[efifogel]

Right ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Mon, 5 May 2025 at 10:27, Andreas Fabri ***@***.***> wrote: *afabri* left a comment (CGAL/cgal#8873) <#8873 (comment)> And it is not only a question of kernel choice. If you use Simple_cartesian<Gmqp> it will be also ok. — Reply to this email directly, view it on GitHub <#8873 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOHKPRQSRYW3HQNISB3244HHZAVCNFSM6AAAAAB4M6IPYWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDQNJQGEZTMMJSHA> . You are receiving this because you commented.Message ID: ***@***.***>