CGAL general polygons: rigid motions and area

Question

Investigating this question, I'll have to deal with shapes whose boundaries are made up from line segments and circular arcs. It seems CGAL should be able to help me here: According to this section of the User's Manual, a General_polygon_set_2 with Gps_segment_traits_2 as its traits class should be able to express most of the operations I need, in particular intersections and differences.

What I haven't found in the docs so far is a way to apply rigid motions to these shapes, and a way to compute the area of the resulting shape.

I guess I can work around both problems. For rigid motions, I could recreate the shape after transforming the original defining objects. And to compute the area, I could use a variantion of the shoelace approach, adjusted to cope with circular arcs. The example from the manual prints details about the supporting circle, and digging thorugh the headers I found that every curve for my polygons does have a supporting_circle() method, soi i guess it is in fact an Arr_circle_segment_traits_2<K>::X_monotone_curve_2. So I should be able to get at enough circle information to compute the area. I only found this in the headers after using deliberate compiler error messages to learn about the types of some objects which the manual simply describes as unspecified_type.

Nevertheless, both of these operations will take quite some work, and I'm surprised that there seems to be no built-in way to do these. On the other hand, the way CGAL does its customizations via template arguments, I might simply be missing a way to do these things which works for circular segments although it might not work for other general polygons. Do you know any shortcuts I might be able to use?

Answer 1

I'm afraid you are not going to like my answer.

I'm a CGAL developer, actually one of the developers of the Reg. Boolean Operation and the Arrangement packages.

First, the operations you are asking for are not supported.

Regarding the area computation, your approach seems feasible. It will be, however, a great effort for us to require such an operation in the concept, because then we would need to implement the operation for all the traits classes we support. I guess, it is always possible to start with one and then adding them one by one. I will throw it into our todo list, but I wouldn't put my bets on a quick delivery...

Regarding the transformation, the answer is more involved. As you have already noticed, applying a non-exact transform to the (exact) geometric shape (e.g., arrangement, general polygon set, or even a small linear simple convex polygon) can be harmful. You must come up with an exact transform, for example, a transformation matrix that comprises numbers of an exact type---the same (or at least convertible to one another) type used to represent the (exact) coordinates of the geometric elements. The problem is, naturally, rotation, because you typically start with an angle and use trigonometric functions (e.g., sin() and cos()) to compute the rotation matrix. Let's say you want to rotate by a given angle, say alpha. You need to compute an approximation of alpha, such that sin(alpha) and cos(alpha) are rational numbers, and thus can be represented by numbers of the aforementioned exact type. The free function CGAL::rational_rotation_approximation() can help. As mentioned in the manual entry of this function, the approximation is based on Farey sequences as described in the rational rotation method presented by Canny and Ressler at the 8th SoCG 1992.

Good luck!