
Boost : 
Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Brandon Kohn (blkohn_at_[hidden])
Date: 20081009 16:51:53

From: "Simonson, Lucanus J" <lucanus.j.simonson_at_[hidden]>
Sent: Thursday, October 09, 2008 2:59 PM
To: <boost_at_[hidden]>
Subject: Re: [boost] Geometry and spatial indexes, my opinion
> Brandon wrote:
>>As for the general
>>case, there is already enough on the plate to have algorithms which
> support
>>both floating point and integral coordinate types :).
>
> That's for darn sure. That is the one thing about your library that
> really intrigues me. I'm pretty much integer only, Barend is pretty
> much floating point exclusively. Joel suggested early on that generic
> programming could resolve the issue easily, but you are the first person
> to take that issue on. How do you do it?
>
> Luke
Well, the jury is still out as to how effective the *real* solution will be.
I start by adding the ability to perform type dispatch based on the number
type of the coordinate. I manage that by again using a traits class (for the
coordinates):
//! Default point traits struct.
//! NOTE: must be specialized for user types.
template <typename Coordinate>
struct coordinate_traits
{
typedef typename Coordinate coordinate_type;
BOOST_MPL_ASSERT_MSG
(
( false )
, COORDINATE_TRAITS_NOT_DEFINED
, (Coordinate)
);
};
//! Macro for coordinate type with integral traits
#define BOOST_DEFINE_INTEGRAL_COORDINATE_TRAITS( Coordinate ) \
template <> \
struct coordinate_traits< Coordinate > \
{ \
typedef Coordinate coordinate_type; \
typedef boost::false_type is_float_t ; \
typedef boost::true_type is_integral_t; \
};
//! Macro for coordinate type with floating point traits
#define BOOST_DEFINE_FLOATING_POINT_COORDINATE_TRAITS( Coordinate ) \
template <> \
struct coordinate_traits< Coordinate > \
{ \
typedef Coordinate coordinate_type;\
typedef boost::true_type is_float_t; \
typedef boost::false_type is_integral_t; \
};
Then I can do a dispatch on the traits. The only issue I've tackled so far
is for comparing segments on a sweepline. I did this by using
boost::rational ( so overflow may still be a problem in some cases ). The
other issue I have yet to tackle is intersection between two segments for
integers. I have an implementation that uses O'Rourke's method from
Computational Geometry in C. In his method the segments are first converted
into parametric coordinates and then compared to see if the resulting system
of equations results in a point which is contained in each segment. As you
well know you can't do this with segments in integral coordinates as the
intersection point often has fractional coordinates. I suppose the only
thing you can do with that is resort to rationals. This will be necessary as
you must track all event points during the sweep (including the
intersections), and reporting of intersections requires that all segments
intersecting in the same point be associated with that point in the
sweepline. This leads me to think that the easiest solution is to make all
the coordinates rational in the event structure (for sorting
lexicographically) and then when actually reporting, making the rationals
available to the visitor class (which is how the reporting is done) along
with the offending segments. This way users who are able to use the
fractional intersections can still use them.. and those who cannot still
have the segments which intersect (and I assume they can glean whatever
information they need from them.) In cases like yours where you constraint
the slopes to be 0,1 or infinity, you can no doubt do a lot better on the
intersection, but a general rational solution for intersection would
probably still work. I still need to think about it more to see how I can
mitigate issues with overflow.
Cheers,
Brandon
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk