Boost logo

Boost :

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
>> link:
>> 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.
> *
> 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

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 > );

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_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
     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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at