CGAL users discussion list

[Efi Fogel <>]

On 7 April 2017 at 15:56, Ch'Gans <> wrote:

On 31 March 2017 at 05:37, Efi Fogel <> wrote:
> Check out vertical decomposition; see
> http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html.

Hi Efi,

Is it me or it is not possible to apply the vertical decomposition to
general polygon with circle/segment edges?

You are the first one to try it, and it has been developed to serve as the convex decomposition step of an implementation of the Minkowski sum operation, which supports only linear polygons, so you are probably right about this limitation.

The Polygon_vertical_decomposition_2 class uses these harcoded typedefs:
  typedef CGAL::Polygon_2<Kernel, Container>             Polygon_2;
  typedef CGAL::Polygon_with_holes_2<Kernel, Container>  Polygon_with_holes_2;
  typedef CGAL::Arr_segment_traits_2<Kernel>             Arr_segment_traits;
  typedef CGAL::Gps_segment_traits_2<Kernel, Container, Arr_segment_traits>
                                                         Traits_2;
  typedef CGAL::General_polygon_set_2<Traits_2>          General_polygon_set_2;


So I have tried to re-implement the vertical decomposition using
Gps_circle_segment_traits_2, but i'm stuck with a weird problem:
To build a vertical X_monotone_curve_2 connecting two arrangement
vertices (with associated '1 root'  points) I need first a 'Kernel'
supporting line, and AFAICT, i cannot build one _exactly_ out of
algebraic numbers...
Actually I am not even sure what exactly a '1 root' point is, does
that mean that it has coordinates expressed as 'a0 +a1*sqrt(r)' with
a0=0 and a1=1? If so then that is an interesting property that i might
be able to exploit.

A one-root number is actually a Square_root_extension; see http://doc.cgal.org/latest/Number_types/classCGAL_1_1Sqrt__extension.html. It's a number represented as 'a0 + a1 * sqrt(a2)', where the type of a0, a1, and a2 are template parameters. a0 doesn't have to be 0. It turns out that this number type is sufficient for the circle-segment traits. This traits supports line segments and circular arcs, where the coefficients of the line segments must be rational. A vertical segment that has an endpoint with Square_root_extension coordinates does not necessarily have rational coordinates any longer, so I guess it is impossible to do it in an exact manner.

Another idea i had (but haven't tried yet), is to calculate, using the
Kernel, the intersection point of the supporting lines associated with
the first 2 incident edges of each vertices, they should be
geometrically equivalent to the '1 root' point of the shared vertex
but expressed using the kernel number type. But that would work only
with linear segment, ... bummer!

decomp() and vertical_decomposition() can be easily modified to work
with an arrangement based on Gps_circle_segment_traits_2, the only
blocker for me ATM is the add_vertical_segment()

Yes, I think it's a real blocker.

Does anyone have tips to share on how to make the vertical
decomposition works with the Gps_circle_segment_traits_2, and maybe
could someone tell me if it is actually possible to do it in an exact
manner or not.

Thanks,
Chris

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss