CGAL users discussion list

["Ch'Gans" <>]

On 8 April 2017 at 09:01, Efi Fogel 
<>
 wrote:
> On 7 April 2017 at 15:56, Ch'Gans 
> <>
>  wrote:
>> On 31 March 2017 at 05:37, Efi Fogel 
>> <>
>>  wrote:
>> > Check out vertical decomposition; see
>> > http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html.
>>
>> Hi Efi,
>>
>> Is it me or it is not possible to apply the vertical decomposition to
>> general polygon with circle/segment edges?
>
>
> You are the first one to try it, and it has been developed to serve as the
> convex decomposition step of an implementation of the Minkowski sum
> operation, which supports only linear polygons, so you are probably right
> about this limitation.

[...]

>> Actually I am not even sure what exactly a '1 root' point is, does
>> that mean that it has coordinates expressed as 'a0 +a1*sqrt(r)' with
>> a0=0 and a1=1? If so then that is an interesting property that i might
>> be able to exploit.
>
>
> A one-root number is actually a Square_root_extension; see
> http://doc.cgal.org/latest/Number_types/classCGAL_1_1Sqrt__extension.html.
> It's a number represented as 'a0 + a1 * sqrt(a2)', where the type of a0, a1,
> and a2 are template parameters. a0 doesn't have to be 0. It turns out that
> this number type is sufficient for the circle-segment traits. This traits
> supports line segments and circular arcs, where the coefficients of the line
> segments must be rational. A vertical segment that has an endpoint with
> Square_root_extension coordinates does not necessarily have rational
> coordinates any longer, so I guess it is impossible to do it in an exact
> manner.

Thanks for the explanation, very much appreciated.

[...]

>> decomp() and vertical_decomposition() can be easily modified to work
>> with an arrangement based on Gps_circle_segment_traits_2, the only
>> blocker for me ATM is the add_vertical_segment()
>
>
> Yes, I think it's a real blocker.

I've just spent a few hours this after-noon on this, it all started with:
How does boolean set operations deal with that? Surely I can find a
piece of code in there that will teach me the tricks...
So I dug into the code, frantically looking for a line creating a new
segment out of 2 existing points, but never found one! ;)
I suddenly realised that my search was vain. The boolean set
operations don't need to do that, they "just" need predicates and
modifier functions such as split() and merge(), That's it, that's all
and it's beautiful! ;)
It reminds me of Chuck Norris jokes, one goes "Chuck Norris makes fire
by rubbing 2 ice cubes together" lol!

Chris