-------------------------------------------------- From: "Simonson, Lucanus J" <lucanus.j.simonson@intel.com> Sent: Thursday, October 09, 2008 2:59 PM To: <boost@lists.boost.org> 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