# 2D arrangements comparison

8 messages
Open this post in threaded view
|

## 2D arrangements comparison

 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
Open this post in threaded view
|

## Re: 2D arrangements comparison

 I suggest that you construct an arrangement-with-history and traverse its cells.   ____  _        ____             _  /_____/_) o    /__________  __  // (____ (   (    (    (_/ (_/-(-'_(/                         _/ On 7 June 2017 at 17:25, Maxim Torgonskiy 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
Open this post in threaded view
|

## Re: 2D arrangements comparison

 Thanks Efi, I'll check it.2017-06-08 2:21 GMT-04:00 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 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
Open this post in threaded view
|

## Re: 2D arrangements comparison

 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,Maxim2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy :Thanks Efi, I'll check it.2017-06-08 2:21 GMT-04:00 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 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
Open this post in threaded view
|

## Re: 2D arrangements comparison

 After several weeks I have another small question.I use Arr_circle_segment_traits_2 with CGAL::Cartesian 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,Maxim2017-06-14 0:52 GMT-04:00 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,Maxim2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy :Thanks Efi, I'll check it.2017-06-08 2:21 GMT-04:00 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 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
Open this post in threaded view
|

## Re: 2D arrangements comparison

 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 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,Maxim2017-06-14 0:52 GMT-04:00 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,Maxim2017-06-08 10:44 GMT-04:00 Maxim Torgonskiy :Thanks Efi, I'll check it.2017-06-08 2:21 GMT-04:00 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 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