Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Andreas Fabri (andreas.fabri_at_[hidden])
Date: 2009-08-26 04:13:17

Simonson, Lucanus J wrote:
> Andreas Fabri wrote:
>> Hello,
>>
>> When I compute union or intersection of two rectangles rotated by 45
>> degree that form an X, I don't necessarily get a 45 degree polygon,
>> namely when 
>> the intersection point is not an integer.
>>
>> For example when one polygon has an edge   0,0  -- 10,10
>>         and the other polygon has an edge  -1,10 --  9,9
>>
>> then they intersect mathematically at  4.5,4.5
>> but as you snap to an integer, you get for example  5,5
>>
>> Now -1,10 -- 5,5  is no longer a 45 degree edge.
>>
>> Isn't the fact that the set of 45 degree polygons is not closed
>> under Boolean operations with snap rounding bothersome (even in
>> practice). 
> 
> It would be very bothersome.  I don't use snap rounding with 45 degree polygons, they are handled by a completely different implementation of the sweepline algorithm.
> 
> In the event that there is an non integer intersection in 45 degree polygon computation I modify the topology of the output to "clip off" corners that lands on a 0.5 value by inserting an edge of length 1.  This preserves the 45 degree invariant and also approximates the correct result as closely as possible given the constraints of the integer grid.  Details of this and an example diagram are shown in slide 8 of the boostcon presentation (linked to in the docs) entitled "Details of 45-degree Booleans".
> 
> Some discussion of this behavior might be warrented in the documentation for Polygon 45 Set.
> 
> A user can easily avoid non-integer intersection artifacts with 45 data by multiplying all cordinate values by two.  The output polygon vertices will then be even-even or odd-odd coordinate pairs (such data cannot give rise to non-integer intersection) and can be fed back into the algorithm as many times as desired.

Well, if you use an int, you can't multiply that often with 2 without getting an overflow,
but as you write in the paper, that is not a problem, because you can use arbitrary precision
integer types like GMP.  But doesn't that make it slow in practice?  Will it appear in
practice, that is do you have situations in your VLSI related software that does iterations
of Boolean operations?

So when you multiply the coordianted of polygon P by two, and feed it back the user has to
associate the scale factor to P, in order to also scale a not-yet scaled polygon Q, before
applying a Boolean operation on P and Q.  Not a big deal, but wouldn't it make sense that
the scale factor becomes part of your package?

best regards,

andreas

> 
> Thanks,
> Luke
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
> 
>