Re: [boost] [GTL] redesign checked into sandbox

From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-05-10 17:19:48

Simonson, Lucanus J wrote:
>> Given my proposed operator syntax for so-called Boolean operations I
>> could fold the arbitrary angle geometry provided by Berend's library
>> into mine (or visa-vera.)
>>
>> manhattan + manhattan => manhattan result type by way of manhattan
>> algorithm
>> manhattan + 45-degree => 45-degree result type by way of 45 degree
>> algorithm
>> manhattan/45-degree + arbitrary angle => arbitrary angle result by
way
>> of arbitrary angle algorithm

Phil wrote:
>As I recall, with Barend's library if you ask for the intersection of 
>two unit-squares (0,0,1,1) and (1,0,2,1) you'll get a line (1,0,1,1), 
>since it considers all points on the perimeter of a polygon to be 
>included in the polygon:
>
>+-+-+
>| | |
>+-+-+
>
>Luke, what does your library do in this case?  I mention this because, 
>as well as the C++ language style issues which I'm pleased to see are 
>being discussed by smarter people than me, there are no doubt very many

>geometry-related design choices here.  If your library were 
>stand-alone, your choices wouldn't matter much; but if as you suggest 
>it can integrate with other (future) libraries, then consistent choices

>are needed.

I've been waiting for this to come up.  It is the old open/closed
semantics issue.  In the specification for what I implemented the
boundary is neither "in" or "out", but somewhere in between.  My
implementation is consistent with the behavior of the EDA vendor tools.
My choices did matter, and in fact, I didn't get to choose, the choice
was made decades ago.  

If performed as a Boolean operation on polygons that happened to be
rectangles the intersection that produces a zero area polygon is a
degeneracy and will not be output.  Only positive area regions are
output.  However, there is also provided by my library a rich language
on rectangle types, which includes intersection of two rectangles that
will return the degenerate intersection as a line modeled as a rectangle
with zero area.

Let's say that instead of intersection it is the subtraction operation
being performed (equivalent to (A & !B) on the same two rectangles as
your example above.  My library would leave A unchanged, would Barend's
library clip the boundary off of A and back it away by some epsilon in
service of the boundaries are "in" semantic?  It may be that Barend only
implements intersection and union, in which case this issue would never
come up because without inverting operations the semantic is never
problematic.

You can generally model "in" semantics by adding an additional bit of
precision to your (integer) coordinates (shifting coordinate values left
by one) and inflating your polygons by one resulting in all odd
coordinates.
Shapes own the even coordinates near their boundaries and your example
above would produce a non-zero intersection containing one column of
even coordinates.  We do things this way at the application level when
we need to worry about the boundary condition.  You could model "out"
semantics by deflating by one instead.

I can't image how much of a pain all this becomes when using floating
point coordinates due to numerical error.  Does Barend's library
consider a boundary to be shared if it is within some epsilon?  What
about if it is within some epsilon of equal angle?  It seems it would
get awfully messy in a hurry.  Even if I were to implement arbitrary
angle geometry, I would do it on fixed point coordinates at the
interfaces and probably use variable precision numerical types for
robustness of the algorithms themselves.  

Given that people seem very concerned about compatibility with cgal it
seems like we should be figuring out what it does in these cases.  The
boost license allows cgal to ship my code with their library if they
choose.  I think it makes a lot of sense to think about compatibility
issues.

Thanks,
Luke