CGAL users discussion list

[Efi Fogel <>]

Hi Panaghis,

Before 4.7 the call minkowski_sum_2(p, q) computed the minkowski sum of p and q using the standard (full convolution) method. In 4.7, an improved method has been introduced, namely minkowski_sum_by_reduced_convolution_2(). This method is more efficient; thus the call to minkowski_sum_2() has been directed to call the latter.

First, I was able to reproduce all the errors using version 4.7. That is:
a. using minkowski_sum_by_full_convolution_2(p, q)---cases 0, 1, and 2

b. using minkowski_sum_by_reduced_convolution_2()---case 4,

c. using minkowski_sum_2(p, q, Greene_convex_decomposition_2....)---case 3

1. We are aware of some bugs in the old function minkowski_sum_by_full_convolution_2(). Recall that in most cases this is less efficient than minkowski_sum_by_reduced_convolution_2().

2. Interestingly, when compiling in release mode the last 2 errors above (i.e., (b.) and (c.)) go away.

You may have discovered some bugs with the new code of minkowski_sum_by_reduced_convolution_2() and of the old code of minkowski_sum_2(p, q, Greene_convex_decomposition_2....) that we had not been aware of beforehand. We will investigate and hopefully resolve these issues soon.

Thanks,

Efi

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

On Fri, Oct 9, 2015 at 8:33 PM, Panaghis Mavrokefalos <> wrote:

Thank you for your timely reply,

I built the 4.7-beta2 release, and the first three cases (which used the convolution strategy) now complete successfully. The fourth one still crashes, however, and I have discovered a fifth test case, which uses the convolution strategy and still crashes with the new version, although this time with a different error message:

./test 4

p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: cv.is_in_x_range(p)
File: /home/panaghis/devel/CGAL/CGAL-4.7-beta2/include/CGAL/Arr_segment_traits_2.h
Line: 457
Aborted

I am attaching the relevant diff patch.

2015-10-09 17:03 GMT+03:00 Sebastien Loriot (GeometryFactory) <>:

Could you give the 4.7 release a try?
The 2D minkowski sum package have been partly rework?

Thanks,

Sebastien.

On 10/09/2015 07:36 AM, Panaghis Mavrokefalos wrote:

Hello,

I have been using the minkowski_sum_2() function from the 2D Minkowski Sums
package to compute the sums of some non-convex, but simple polygons. In
some of
my test cases, I noticed CGAL assertion failures (pre- and post-condition
failures) at runtime, which I traced to calls of that function. I am
aware that
these sort of errors occur when using a kernel with inexact
consrtuctions, but
I made sure I was using the Exact_predicates_exact_constructions_kernel. At
first, I tried replacing the default (convolution) strategy with a
decomposition strategy (I chose Greene_convex_decomposition_2), but then the
errors occurred in another test case.

A test file is attached, reproducing the cases which triggerred the
errors. The
CMakeLists.txt file is generated using `cgal_create_CMakeLists -s main`.
I am
building with g++ version 4.8.4 and using CGAL version 4.5.1, configured
with
CMAKE_CXX_FLAGS=-frounding-math -std=c++11.

There are four different test cases, corresponding to the first command line
argument of the executable equal to 0 through 3. The simplicity of the input
polygons to the minkowski_sum_2() function is explicitly tested before the
call. For each test case, the output of the run of the executable is shown:

./main 0

p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of
'CGAL::Precondition_exception'
   what():  CGAL ERROR: precondition violation!
Expr: nodeP != NULL && nodeP->is_valid()
File: /usr/local/include/CGAL/Multiset.h
Line: 339
Aborted

./main 1

p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of 'CGAL::Assertion_exception'
   what():  CGAL ERROR: assertion violation!
Expr: (!is_valid(i)) || (!is_valid(s)) || (!(i>s))
File: /usr/local/include/CGAL/Interval_nt.h
Line: 139
Explanation:  Variable used before being initialized (or CGAL bug)
Aborted

./main 2

p is simple
q is simple
Computing the Minkowski sum of p and q using the default strategy
terminate called after throwing an instance of
'CGAL::Precondition_exception'
   what():  CGAL ERROR: precondition violation!
Expr: nodeP != NULL && nodeP->is_valid()
File: /usr/local/include/CGAL/Multiset.h
Line: 339
Aborted

./main 3

p is simple
q is simple
Computing the Minkowski sum of p and q using the Greene decomposition
strategy
terminate called after throwing an instance of
'CGAL::Postcondition_exception'
   what():  CGAL ERROR: postcondition violation!
Expr: convex_partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(), res.output_so_far_begin(),
res.output_so_far_end(), traits)
File: /usr/local/include/CGAL/Partition_2/partition_greene_approx_convex_2.h
Line: 834
Aborted

Since, as mentioned before, I am using an exact constructions kernel, and a
variety of different errors are produced, I am at a loss as to what is
wrong.
Any help would be greatly appreciated.

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