CGAL users discussion list

["Ch'Gans" <>]

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?

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.

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()

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