Subject: CGAL users discussion list
List archive
Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions
Chronological Thread
- From: Efi Fogel <>
- To:
- Subject: Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions
- Date: Sat, 10 Oct 2015 18:04:15 +0300
- Authentication-results: mail2-smtp-roc.national.inria.fr; spf=None ; spf=Pass ; spf=None
- Ironport-phdr: 9a23:kBKTihawyKVI5Th+mGTyzRH/LSx+4OfEezUN459isYplN5qZpcSybnLW6fgltlLVR4KTs6sC0LqK9f+xEjJRqb+681k8M7V0HycfjssXmwFySOWkMmbcaMDQUiohAc5ZX0Vk9XzoeWJcGcL5ekGA6ibqtW1aJBzzOEJPK/jvHcaK1oLsh7z0pMyYPVQArQH+SI0xBS3+lR/WuMgSjNkqAYcK4TyNnEF1ff9Lz3hjP1OZkkW0zM6x+Jl+73YY4Kp5pIYTGZj8ZLkyGLxEECw9YSdy/9zurRCFTA2V53JaXH9RiQtNGwGC7Rf0WdD6vSL+8+Z8wyKHJtalcbdhUjur6+JnSQTjlTwcHz8/6mDezMJq34xBpxf0ihJ+i6DTb4yRfK5zcKLTetwXQUJOW89QU2pKBYbqPNhHNPYIIesN99q1nFAJtxbrXQQ=
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.
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.
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 /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
On Fri, Oct 9, 2015 at 8:33 PM, Panaghis Mavrokefalos <> wrote:
./test 4Thank 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:
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
AbortedI 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
- [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Panaghis Mavrokefalos, 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Sebastien Loriot (GeometryFactory), 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Panaghis Mavrokefalos, 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Efi Fogel, 10/10/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Panaghis Mavrokefalos, 10/09/2015
- Re: [cgal-discuss] minkowski_sum_2 assertion failures, even when using exact constructions, Sebastien Loriot (GeometryFactory), 10/09/2015
Archive powered by MHonArc 2.6.18.