[KSP] Finalizing Partition Error [Help][CGAL 6.0.1]

[ThreeBoxWithCode]

When I use KSP(Kinetic Shape Partition)[CGAL 6.0.1] to partition the space, the code ksp.partition(2) reports an error.

Issue Details

Details of the error are as follows:

--- FINALIZING PARTITION:
* getting volumes ...
CGAL error: precondition violation!
Expression : !collinear(o_prime,o,q)
File       : D:\Program_Files\CGAL-6.0.1\CGAL-6.0.1\include\CGAL/Polygon_mesh_processing/internal/Corefinement/predicates.h
Line       : 77
Explanation:
Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html
ERROR: constrained Delaunay triangulation failed

I found that in sorted_around_edge function, points o_prime, o, q were detected as collinear errors. I would like to ask how can I add constraints to the input_vertices and input_faces to avoid such errors?

I hope someone can give me some ideas. Thank you very much~

Source Code

using EPICK = CGAL::Exact_predicates_inexact_constructions_kernel;
using EPECK = CGAL::Exact_predicates_exact_constructions_kernel;

using Kernel = EPICK;
using FT = typename Kernel::FT;
using Point_3 = typename Kernel::Point_3;

using Surface_mesh = CGAL::Surface_mesh<Point_3>;
using KSP = CGAL::Kinetic_space_partition_3<EPICK>;
using Timer = CGAL::Real_timer;

std::vector<Point_3> input_vertices;
std::vector<std::vector<std::size_t> > input_faces;

try
	{
		KSP ksp(CGAL::parameters::verbose(true).debug(false));
		ksp.insert(input_vertices, input_faces);

		ksp.initialize(CGAL::parameters::bbox_dilation_ratio(1.1).reorient_bbox(false));

		ksp.partition(2);  // Error reported here!!

		ksp.getVolumes<EPICK>(output_vertices, output_faces, output_volume_centers);
	}
	catch (std::exception& e) {
		std::cerr << "\t--STOCKER: partition failed: " << e.what() << std::endl;
		return false;
	}
	catch (...) {
		return false;
	}

	if (output_faces.size() != output_volume_centers.size()) {
		return false;
	}

Environment

• Operating system (Windows, 64 bits):
• Compiler: visiual studio 2022
• Release or debug mode: Debug
• CGAL version: 6.0.1
• Boost version: 1.79.0
• Other libraries versions if used: Eigen-3.3.4

[soesau]

I will look into it. Can you share the input data or a minimal set of polygons, so I can reproduce the error?

[ThreeBoxWithCode]

I will look into it. Can you share the input data or a minimal set of polygons, so I can reproduce the error?

@soesau Thanks for your reply. I changed the data into.OFF format and put it in this link.

Here is an explanation of the data, I build polygons by assigning 2-D line segments with positive and negative height values, which I call fake polygons:

[ThreeBoxWithCode]

@soesau Hello, can this error be repeated on your side?

[soesau]

Yes, I can reproduce the error and I am working on a solution!

[ThreeBoxWithCode]

Thanks for confirming! Please let me know if you need any additional details from my side. Looking forward to your solution.

[soesau]

@ThreeBoxWithCode I created a PR with a fix. You can try it. However, we may continue to work on the PR.

[ThreeBoxWithCode]

I will try it, thank you for your work 👍