
Boost : 
Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 20090825 17:49:27
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 45degree Booleans".
Some discussion of this behavior might be warrented in the documentation for Polygon 45 Set.
A user can easily avoid noninteger intersection artifacts with 45 data by multiplying all cordinate values by two. The output polygon vertices will then be eveneven or oddodd coordinate pairs (such data cannot give rise to noninteger intersection) and can be fed back into the algorithm as many times as desired.
Thanks,
Luke
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk