Re: [boost] generative geometry algorithms library idea

Subject: Re: [boost] generative geometry algorithms library idea
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-09-23 15:16:12

--------------------------------------------------
From: "Michael Marcin" <mike.marcin_at_[hidden]>
Sent: Tuesday, September 23, 2008 1:37 PM
Newsgroups: gmane.comp.lib.boost.devel
To: <boost_at_[hidden]>
Subject: Re: generative geometry algorithms library idea

> Brandon Kohn wrote:
>> Hi all,
>>
>> I've been doing some work for the past few weeks on a generative/generic 
>> 2D geometry library (leaving open the possibility for 3D in the future). 
>> The idea is for all the algorithms to be generative taking coordinate, 
>> point, segment, polyline/gon types as template parameters (or deducing 
>> where presented as nested typedefs) and specialized traits types for 
>> accessing type traits and methods ( things like 
>> access_traits<point_type>::get_x( point ) .). So far the library has 
>> allowed me to work with the same algorithms in native floating type and 
>> exact types like gmp's mpq_class. It's just a first rough draft of ideas, 
>> and I would really like some input from the community to see if I'm on 
>> the right track for something that boost would be interested in having. 
>> I'll post a copy of the lib in the
> va
>>  ult. It's header only (with a small testbed with trivial testing and a 
>> visual studio 2008 solution/project). I hope there should not be too many 
>> issues compiling these tests/headers under ot
>>  her platforms.
>>
>> I'll put it in the vault as generative_geometry_algorithms.zip
>>
>> link: 
>> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=generative_geometry_algorithms.zip&directory=Math%20-%20Geometry&
>>
>> Thanks for any constructive input.
>>
>
> Apologies I haven't looked at your library yet but is it likely that the 
> algorithms will be usable with eigen2* data types? Eigen2 seems to be the 
> best open source small vector/matrix library right now for performance. At 
> least that I can find.
>
> * http://eigen.tuxfamily.org/
>
> Thanks,
>
> -- 
> Michael Marcin
>

HI Michael,

I wouldn't see any reason why it wouldn't. The basic rationale for 
representation of primitives is that their numeric traits, dimension etc are 
embedded in a point_traits<> specialization. Access functions are specified 
in a separate traits specialization.

There are a couple of ways you can use the code: (apologies if the format 
doesn't come out right... this is my first time posting code)

For example, say you have a vector type for your point:

(eigen seems to use: VectorXf )

BOOST_DEFINE_USER_POINT_TRAITS( VectorXf, float, 2 );//note the 2 is 
dimension.

template <>
struct cartesian_access_traits< VectorXf >
{
    typedef VectorXf point_type;
    typedef boost::numeric::geometry::point_traits< VectorXf 
 >::coordinate_type coordinate_type;
    typedef boost::numeric::geometry::point_traits< 
VectorXf>::dimension_type  dimension_type;

    static inline coordinate_type get_x( const point_type& p ) { return 
p[0]; }
    static inline coordinate_type get_y( const point_type& p ) { return 
p[1]; }

    //Note, the template requirement here is due to some experimentation I'm 
doing on how to deal with different dimensions and the
    //construct member functions specification both 2 and higher dimensions.
    //I wanted to make use the enable_if/disable_if based on the 
point_traits<>::dimension_type and to do that, you have to be in a template 
member function
    //(at least in visual studio)
    template <typename Point>
    static inline point_type      construct( const coordinate_type& x, const 
coordinate_type& y ) { point_type p(dimenstion_type::value); p[0] = x; p[1] 
= y; return p; }
};

BOOST_DEFINE_SEGMENT_TRAITS( VectorXf,  segment< VectorXf > );
BOOST_DEFINE_SEGMENT_ACCESS_TRAITS( segment< VectorXf > );

Here is a specialization I did for the GMP rational type using the point 
template provided with my code:
typedef point<mpq_class, 2>      point_rational_2d;
BOOST_DEFINE_POINT_TRAITS( point_rational_2d );
BOOST_DEFINE_CARTESIAN_ACCESS_TRAITS( point_rational_2d );
BOOST_DEFINE_SEGMENT_TRAITS( point_rational_2d, segment< point_rational_2d 
 > );
BOOST_DEFINE_SEGMENT_ACCESS_TRAITS( segment< point_rational_2d > );

You can then use the points as-is in the algorithms:

For example:

BOOST_AUTO_TEST_CASE( TestIntersections )
{
     using namespace boost::numeric::geometry;
     typedef cartesian_access_traits< VectorFx > point_access;

     VectorFx p1 = point_access::construct< VectorFx >( 0., 0. ); //I 
agree... it's annoying to have the point type specified here as a template 
parameter.
     VectorFx p2 = point_access::construct< VectorFx >( 1., 1. );
     VectorFx p3 = point_access::construct< VectorFx >( 1., 0. );
     VectorFx p4 = point_access::construct< VectorFx >( 0., 1. );

    segment< VectorFx > seg1( p1, p2 );
    segment< VectorFx > seg2( p3, p4 );

    VectorFx xPoints[2];
    intersection_type iType = intersect( seg1, seg2, xPoints, 
fraction_tolerance_comparison_policy<float>(1e-5) );
    std::cout << iType << " at point: " << point_access::get_x( Points[0] ) 
<< ", " << point_access::get_y( xPoints[0] ) << std::endl;
}

This is still very much a work in progress, but please do have a look and 
see what you think. I'd like to hear suggestions about the design or how I 
might improve things.

Cheers,

Brandon