Boost logo

Boost :

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-25 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 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.

Thanks,
Luke


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk