Degenerate versions of the `Power_side_of_oriented_power_sphere/circle` predicates

[MaelRL]

The predicates Power_side_of_oriented_power_sphere_3 and Power_side_of_oriented_power_circle_2 were recently moved to the kernel (see this small feature / PR).

Their basic versions (4 Weighted_point_3 + a query Weighted_point_3 for 3D, 3 Weighted_point_2 + a query Weighted_point_2 for 2D) make sense with the orientation given by the input defining the orientation of the sphere.

These predicates are mostly used by the regular triangulations, in degenerate geometric configurations such as 4 coplanar Weighted_point_3. The predicates thus provide overloads such as 2 Weighted_point_3 and a query point. This made sense in the regular triangulation setting because the points passed as arguments are taken from triangulation cells, which have known (positive) orientation.

However, in a general setting, one cannot orient e.g. 3 Weighted_point_3 in 3D space and thus the predicate cannot announce (assuming the query point is not on the boundary) whether POSITIVE or NEGATIVE will be returned (which is not unlike the degenerate overload of the predicate CoplanarOrientation_3). This makes it really tricky to understand and use.

After discussion with @odevil, @janetournois, and @MoniqueTeillaud, the possible solutions are:

1. Do not document them, but leave an explanation in the code for the adventurers that really need those degenerate versions of power_side_of_oriented_power_sphere_3 / ...circle_2.

2. Completely remove the code and rework the code in regular triangulations to proceed like in Delaunay triangulations. In details, this means:

   • If the triangulation has dimension 3
   • For 5 finite vertices, nothing changes, call power_side_of_oriented_power_sphere_3
   • For 5 vertices, one of which being the infinite_vertex, call orientation(4 points with correct order, depending on the position of the infinite_vertex)
     • if coplanar, return power_side_of_bounded_power_circle_3(4 points)
     • otherwise, return orientation(4 points, once again in the correct order)
   • If the triangulation has dim 2, the Conflict_tester should take 4 vertices as argument
   • If the infinite_vertex is not one of those vertices, return power_side_of_bounded_power_circle_3(4 points)
   • Otherwise, return coplanar_orientation(3 points, in the correct order depending on the position of the infinite_vertex) -- If collinear, handle it with some kind of collinear_orientation predicate

The same must be done in RT2.h, and wherever else the predicates are used.

3. Document it like in CoplanarOrientation_3, that is "That predicate will return something consistenly, but whether it is positive or negative, is for you to decide through the order of arguments"

4. Rewrite CGAL without orientation !

The 3rd option is not very satisfying. Currently, I have used the 1st option in this branch, but the 2nd would be better, and is todo.

Maybe a GSoC can be opened for the 4th option : ).

[MoniqueTeillaud]

Thank you for the summary.

Precisions:

• option 1 is fine as a temporary solution. However it is not clean, as regular triangulations become dependent on undocumented code.
• for option 3, the predicate would have to return a result that is not only consistent with istself, but also with CoplanarOrientation_3. Reading the manual would become a nightmare.

A GSoC for option 4 is an interesting idea. Success does not look very likely, though: such a task requires to have both a wide and a deep knowledge of CGAL, which an intern caanot have.

[MaelRL]

The GSoC part was a joke : >

[MoniqueTeillaud]

well, worth thinking

[afabri]

If I understand correctly you, @MaelRL , went for Option 1, namely to remove the documentation. Shall we close this issue?