Re: [boost] Geometry and spatial indexes, my opinion

Subject: Re: [boost] Geometry and spatial indexes, my opinion
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-10-09 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
>