CGAL users discussion list

[Efraim Fogel <>]

Hi J.L.M.,

I was able to reproduce the errors. As a matter of fact, if you compile
in debug mode, you get an assertion.

The "2D Regularized Boolean Set-Operations" package supports only
regularized operations. Lower dimensional features of polygons are
ignored. The "2D Minkowski Sums" package operate on the same type of
polygons, so in essence a degenerate polygon that consists of a single
vertex or of 2 vertices is considered invalid. The manual does not say
much about the validity of the operands. The package supports 2 methods
- one is based on convolution and the other on convex decomposition. The
latter uses the union (join) operation of the "2D Regularized Boolean
Set-Operations", so obviously it is not expected to produce the right
results for all degenerate cases. I did try it though on the line case
you provided, and it just happened to work.

This leaves the convolution method. The point case you provided can be
easily handled separately. We may very well add some code to handle this
case. I believe that in concept the line case, and perhaps even many
more degenerate cases, can be handled correctly by enhancing the code,
meaning, we can consider this as a feature, which is currently not
supported, and your email as a request for supporting it.

In the meanwhile, you can always compute the Minkowski sum of two
polygons, where at least one of them consists of a small number of
vertices, using a brute-force method, in reasonable time. Add each
vertex of P with each vertex of Q, and compute the convex hull of the
vertices pairwise sums.

J.L.M. wrote:
> Thanks for the help. Unfortunately, changing the kernel does not alter
> the output. I am still getting the same behavior using an
> Exact_predicate_exact_construction_kernel. That is, in the line case,
> the same polygon is being produced, and in the point case, the program
> is still going into an infinite loop.
>
> The change I did was to add this line:
>
> #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
>
> And change my Kernel typedef to:
>
> typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
>
> 
>  wrote:
>> As Ben pointed out, you must use an exact-predicate and
>> exact-construction kernel. I suggest:
>>
>> CGAL::Exact_predicate_exact_construction_kernel
>>
>> Quoting "Ben Supnik" 
>> <>:
>>
>>> Hi JLM,
>>>
>>> Am I right in thinking that you are using a kernel that does not
>>> have exact constructions with Minkowski sum?
>>>
>>> I'm not 100% sure on this, but I think you need an exact
>>> construction kernel to use Minkowski sums.
>>>
>>> cheers
>>> Ben
>>>
>>>
>>>
>>> J.L.M. wrote:
>>>> Attached are two simple programs that demonstrate my difficulties
>>>> with 2D Minkowski sums. The first one, mks_point.cpp enters into an
>>>> infinite loop when attempting to calculate the Minkowski sum of one
>>>> polygon with another polygon that contains only one single point.
>>>> It is my expectation that the result of such a computation is
>>>> merely the translation of the polygon by the point.
>>>>
>>>> Secondly, and more important to me, I need to calculate the
>>>> Minkowski sum of a polygon and an edge of another polygon. I am
>>>> doing that by making a polygon with only two verticies. The second
>>>> program shows my problem. The output is:
>>>>
>>>> { Outer boundary = [ 14 vertices: (-7 -3) (-7 -13) (-13 -13) (-13
>>>> -3) (-17 -3) (-27 -3) (-27 -17) (-3 -17) (7 -17) (7 -3) (3 -3) (7
>>>> -3) (7 -17) (-3 -17) ]
>>>>  0 holes:
>>>> }
>>>>
>>>> Which is incorrect. The last three verticies should not exist, and
>>>> if you look closely, they backtrack along the path around the
>>>> polygon. When I use the verticies in an OpenGL program to display
>>>> the polygon, I get a nonsensical shape. If those last three
>>>> verticies were not there, then the shape would be correct. It is a
>>>> U shape with square corners, translated horizontally. So the
>>>> vertical parts of the U shape should be thick due to the translation.
>>>>
>>>> When I remove the negative signs from the Q polygon, then the
>>>> output is correct.
>>>>
>>>> I would appreciate some help with this. I did not see anything in
>>>> the CGAL manual stating that there were restrictions on the
>>>> Minkowski sum operation.
>>>>
>>>> Thanks.
>>>>
>>>
>>> -- 
>>> Scenery Home Page: http://scenery.x-plane.com/
>>> Scenery blog: http://xplanescenery.blogspot.com/
>>> Plugin SDK: http://www.xsquawkbox.net/xpsdk/
>>> X-Plane Wiki: http://wiki.x-plane.com/
>>> Scenery mailing list: 
>>> 
>>> Developer mailing list: 
>>> 
>>>
>>> -- 
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
-- 
  ____  _        ____             _
 /_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                        _/