Re: [boost] generative geometry algorithms library idea

Subject: Re: [boost] generative geometry algorithms library idea
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-09-26 20:24:26

>> Hi Brandon,
>>
>
>Hi Barend,

Hi Brandon and Barend,

If two is company, is three a community?  I suggested to Brandon off
list that we ought to merge.  I also conceded that the algorithms he
provides are a better starting point than mine in terms of what a boost
geometry library ought to provide.  The primary thing preventing us from
working together and sharing algorithms is the lack of an agreed upon
standard for abstracting geometry data types from the algorithms that
work on them.  We all agree that it should be done, we even largely
agree on how in a general sense.  If we could pick one specific syntax
and pattern, or combine ideas to arrive at one we all agree on, then we
could port our algorithms and their interfaces into that form.  Ideally,
we should be able to compare our algorithms side by side in the same
library to chose which one becomes the one that is published as the
boost algorithm.  Barend has a line intersection algorithm.  I have
boolean operations on manhattan, 45-degree and now arbitrary angle
polgyons.  Replacing my line intersection algorithm with the one coming
from Barend or Brandon's library might speed up my boolean operations.
My scanline that does boolean operations is generic and provides several
other algorithms such as connectivity extraction and property merge
operations, but may not be as fast as Brandon's for simple Booleans.
Ideally, I'd like to find out the answers to these questions with a
minimum of effort.  I think the algorithms themselves are less important
than their interfaces, and as Brandon said, the whole meat of the
problem is how to parameterize the coordinate data type in a way that
actually works for complex numerical data types and is still usable.

Brandon pointed out:
>Also, there are some other issues with respect to using custom number
types 
>which may not use math function like std::sqrt or the trig functions
which 
>may require specialization of math_function traits for the coordinate
type. 
>I had to do this in order to use mpq_class (rational exact type in GMP)
so 
>that I could get distances between two points :-).  (In the end its
going >to 
>require defining a generic Taylor series expansion for all the trig +
sqrt 
>functions that support number types as template parameters.) 

These issues clearly need to be sorted out.  I just integrated mpz_class
into my integer geometry oriented algorithms because I need upwards of
90 bits of integer precision to store intermediate values of complex
algebraic expressions.  I had to wrap it to provide the casting operator
to integer so that I could parameterize the high precision data type in
my code without directly depending on GPL'd gmp header files.  For me
the problem of how to bridge the conceptual gap between floating point
and integer geometry is an open question.  Even multi-precision rational
data type geometry does not really satisfy my needs because a robust
linescan in rational coordinates may lead to new intersections and many
degeneracies being introduced when snapping back to integer coordinates
at the output.  I don't need an epsilon or comparison policy argument to
deal with integer coordinates, so I don't have these in my library.
Clearly, I should need it if comparing Euclidean distances, and I could
benefit from incorporating it.  I'd like to see a boost library that
works well with floating point, rational/lazy-exact and integer
coordinates of geometry that I can contribute to/use.  This could mean
that the line segment intersection algorithm requires a snapping policy
in addition to a comparison policy.  It might even mean separate integer
and floating point implementations of some algorithms where convolving
the complexities of the one with those of the other is simply not worth
the trouble.

I think we should focus on how we can get from where we are
today--talking about my geometry library, your geometry library and his
geometry library-- to the point where we need to be; talking about the
boost geometry library and the community of developers who are
contributing to it.

Luke