2D arrangements comparison

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

2D arrangements comparison

Maxim Torgonskiy
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim

Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Efi Fogel
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim


Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Maxim Torgonskiy
Thanks Efi, I'll check it.

2017-06-08 2:21 GMT-04:00 Efi Fogel <[hidden email]>:
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim



Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Maxim Torgonskiy
It worked for me with Arr_circle_segment_traits_2, Arr_polycurve_traits_2 and Arrangement_with_history_2.
I put two polycurves into two different arrangements, make overlay and iterate the segments of the resulting arrangement. With arrangement with history I can detect which of two polycurves (or whether both of them) generates a segment. It's sufficient for my intersection type detection.

Thanks,
Maxim

2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
Thanks Efi, I'll check it.

2017-06-08 2:21 GMT-04:00 Efi Fogel <[hidden email]>:
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim




Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Maxim Torgonskiy
After several weeks I have another small question.

I use Arr_circle_segment_traits_2 with CGAL::Cartesian<CGAL::Exact_rational> taken from a CGAL example. If I understand correctly Arr_circle_segment_traits_2 must be used only with rational numbers (at least for circle centers). Is there any workaround or different similar kernel which allows to use real coordinates?

Thanks,
Maxim

2017-06-14 0:52 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
It worked for me with Arr_circle_segment_traits_2, Arr_polycurve_traits_2 and Arrangement_with_history_2.
I put two polycurves into two different arrangements, make overlay and iterate the segments of the resulting arrangement. With arrangement with history I can detect which of two polycurves (or whether both of them) generates a segment. It's sufficient for my intersection type detection.

Thanks,
Maxim

2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
Thanks Efi, I'll check it.

2017-06-08 2:21 GMT-04:00 Efi Fogel <[hidden email]>:
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim





Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Efi Fogel
First, you can use Exact_predicates_exact_constructions_kerner. 

The whole idea behind the Arr_circle_segment_traits_2 traits class template is that you can use a rational kernel and still be able to construct an arrangement of circular arcs. You can any kernel you want as long as it supports exact rational arithmetic. 

If you want to use real coordinates, you may also try the algebraic traits provided by the package, or even the conic traits. 


On Jul 17, 2017 06:59, "Maxim Torgonskiy" <[hidden email]> wrote:
After several weeks I have another small question.

I use Arr_circle_segment_traits_2 with CGAL::Cartesian<CGAL::Exact_rational> taken from a CGAL example. If I understand correctly Arr_circle_segment_traits_2 must be used only with rational numbers (at least for circle centers). Is there any workaround or different similar kernel which allows to use real coordinates?

Thanks,
Maxim

2017-06-14 0:52 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
It worked for me with Arr_circle_segment_traits_2, Arr_polycurve_traits_2 and Arrangement_with_history_2.
I put two polycurves into two different arrangements, make overlay and iterate the segments of the resulting arrangement. With arrangement with history I can detect which of two polycurves (or whether both of them) generates a segment. It's sufficient for my intersection type detection.

Thanks,
Maxim

2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
Thanks Efi, I'll check it.

2017-06-08 2:21 GMT-04:00 Efi Fogel <[hidden email]>:
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim






Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Maxim Torgonskiy
Hello Efi,

Thank you for your suggestions. I've tried with EPEC but I still should define coordinates of a circle center as well as of arc endpoints as rational numbers. For instance, if I change 'Point_2 t(Number_Type(3) / Number_Type(2), 2);' to 'Point_2 t(1.5, 2);' in the example below CGAL fails with a comparison assertion. Is it possible to define at least either the center or the endpoints with real coordinates?

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_circle_segment_traits_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel    Kernel;
typedef Kernel::FT                                           Number_Type;
typedef Kernel::Point_2                                      Rational_Point_2;
typedef Kernel::Circle_2                                     Circle_2;
typedef CGAL::Arr_circle_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::CoordNT                                    CoordNT;
typedef Traits_2::Point_2                                    Point_2;
typedef Traits_2::Curve_2                                    Curve_2;

int main() {
  Rational_Point_2 c(Number_Type(3) / Number_Type(2), 0);
  Circle_2 circle(c, 4, CGAL::COUNTERCLOCKWISE);
  Point_2 s(Number_Type(7) / Number_Type(2), 0);
  Point_2 t(Number_Type(3) / Number_Type(2), 2);
  Curve_2 arc(circle, s, t);

  return 0;
}

Thanks,
Maxim


2017-07-17 3:49 GMT-04:00 Efi Fogel <[hidden email]>:
First, you can use Exact_predicates_exact_constructions_kerner. 

The whole idea behind the Arr_circle_segment_traits_2 traits class template is that you can use a rational kernel and still be able to construct an arrangement of circular arcs. You can any kernel you want as long as it supports exact rational arithmetic. 

If you want to use real coordinates, you may also try the algebraic traits provided by the package, or even the conic traits. 


On Jul 17, 2017 06:59, "Maxim Torgonskiy" <[hidden email]> wrote:
After several weeks I have another small question.

I use Arr_circle_segment_traits_2 with CGAL::Cartesian<CGAL::Exact_rational> taken from a CGAL example. If I understand correctly Arr_circle_segment_traits_2 must be used only with rational numbers (at least for circle centers). Is there any workaround or different similar kernel which allows to use real coordinates?

Thanks,
Maxim

2017-06-14 0:52 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
It worked for me with Arr_circle_segment_traits_2, Arr_polycurve_traits_2 and Arrangement_with_history_2.
I put two polycurves into two different arrangements, make overlay and iterate the segments of the resulting arrangement. With arrangement with history I can detect which of two polycurves (or whether both of them) generates a segment. It's sufficient for my intersection type detection.

Thanks,
Maxim

2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
Thanks Efi, I'll check it.

2017-06-08 2:21 GMT-04:00 Efi Fogel <[hidden email]>:
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim







Reply | Threaded
Open this post in threaded view
|

Re: 2D arrangements comparison

Efi Fogel
First, changing to 'Point_2 t(1.5, 2);' is expected to fail, because floating point 1.5 is not exactly 3/2.
Secondly, we typically refer to a type that can represent roots of polynomials as 'real'. What do you mean by 'real'?

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 11 August 2017 at 14:58, Maxim Torgonskiy <[hidden email]> wrote:
Hello Efi,

Thank you for your suggestions. I've tried with EPEC but I still should define coordinates of a circle center as well as of arc endpoints as rational numbers. For instance, if I change 'Point_2 t(Number_Type(3) / Number_Type(2), 2);' to 'Point_2 t(1.5, 2);' in the example below CGAL fails with a comparison assertion. Is it possible to define at least either the center or the endpoints with real coordinates?

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_circle_segment_traits_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel    Kernel;
typedef Kernel::FT                                           Number_Type;
typedef Kernel::Point_2                                      Rational_Point_2;
typedef Kernel::Circle_2                                     Circle_2;
typedef CGAL::Arr_circle_segment_traits_2<Kernel>            Traits_2;
typedef Traits_2::CoordNT                                    CoordNT;
typedef Traits_2::Point_2                                    Point_2;
typedef Traits_2::Curve_2                                    Curve_2;

int main() {
  Rational_Point_2 c(Number_Type(3) / Number_Type(2), 0);
  Circle_2 circle(c, 4, CGAL::COUNTERCLOCKWISE);
  Point_2 s(Number_Type(7) / Number_Type(2), 0);
  Point_2 t(Number_Type(3) / Number_Type(2), 2);
  Curve_2 arc(circle, s, t);

  return 0;
}

Thanks,
Maxim


2017-07-17 3:49 GMT-04:00 Efi Fogel <[hidden email]>:
First, you can use Exact_predicates_exact_constructions_kerner. 

The whole idea behind the Arr_circle_segment_traits_2 traits class template is that you can use a rational kernel and still be able to construct an arrangement of circular arcs. You can any kernel you want as long as it supports exact rational arithmetic. 

If you want to use real coordinates, you may also try the algebraic traits provided by the package, or even the conic traits. 


On Jul 17, 2017 06:59, "Maxim Torgonskiy" <[hidden email]> wrote:
After several weeks I have another small question.

I use Arr_circle_segment_traits_2 with CGAL::Cartesian<CGAL::Exact_rational> taken from a CGAL example. If I understand correctly Arr_circle_segment_traits_2 must be used only with rational numbers (at least for circle centers). Is there any workaround or different similar kernel which allows to use real coordinates?

Thanks,
Maxim

2017-06-14 0:52 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
It worked for me with Arr_circle_segment_traits_2, Arr_polycurve_traits_2 and Arrangement_with_history_2.
I put two polycurves into two different arrangements, make overlay and iterate the segments of the resulting arrangement. With arrangement with history I can detect which of two polycurves (or whether both of them) generates a segment. It's sufficient for my intersection type detection.

Thanks,
Maxim

2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy <[hidden email]>:
Thanks Efi, I'll check it.

2017-06-08 2:21 GMT-04:00 Efi Fogel <[hidden email]>:
I suggest that you construct an arrangement-with-history and traverse its cells.

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/



On 7 June 2017 at 17:25, Maxim Torgonskiy <[hidden email]> wrote:
Hello,

I need to verify whether two 2D curves 1) don't intersect, or 2) intersect, or 3) one contains another. The curves contain straight line segments and arc segments. I've found an overlay function in Arrangement_2 [1] which cover all the three cases. The problem is to verify whether the output arrangement is equal to one of the input arrangements. Is there any method to do the check? I've found only [2] equality operator in the code but it seems that it is not what I'm looking for. 

An example of input curves : c1 = (-1,0) -> (0,0) -> (0,1) -> (0,2) -> (2,1) ; c2 = (0,0.5) -> (0,1.5)

Thanks,
Maxim