Boost logo

Boost :

Subject: Re: [boost] A design for geometric objects
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-12-04 14:05:20


Bruno Lalande wrote:
>> int main(int, char** argv)
>> {
>> ellipse_traits<ellipse>::width();
>> ellipse_traits<circle>::width();
>> return 0;
>> }

Mathias G wrote:
>Sorry for the late reply, but from a quick glance I can tell this is
>just single dispatch.
>Geometric algorithms really need multi-dispatch.

Hmm, I have three boolean algorithms. One for manhattan data, which is a small constant factor slower than std::sort, one for data that includes 45 degree edges, which is a small constant factor slower than the manhattan algorithm and a very very slow, but robust arbitrary angle algorithm. I use operator syntax to call boolean operations.

polygon_45_data<int> p45;
polygon_90_data<int> p90;
polygon_data<int> p;

p90 & p90; //calls manhattan intersection boolean algorithm
p45 | p90; //calls 45 union boolean algorithm
p45 - p45; //calls 45 and not boolean algorithm
p ^ p90; //calls arbitrary angle xor boolean algorithm

These operators are overloaded with SFINAE on return type such that three intersection operators are sufficient to cover all valid combinations of any geometry type, rectangle, six flavors of polgyons with and without holes in the manhattan, 45, or general domains, and std containers thereof as well as my data structures that serve as the inputs to the boolean algorithms

//manhattan boolean intersection operator
//works on any two manhattan geometric data types
template <typename geometry_type_1, typename geometry_type_2>
typename requires_2<
        typename is_polygon_90_set_type<geometry_type_1>::type::type,
      typename is_polygon_90_set_type<geometry_type_2>::type::type,
      polygon_90_set_view<geometry_type_1, geometry_type_2,
                boolean_op::BinaryAnd> >::type
operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
  return polygon_90_set_view<geometry_type_1, geometry_type_2,
                                        boolean_op::BinaryAnd>
      (lvalue, rvalue,
       polygon_90_set_traits<geometry_type_1>::orient(lvalue),
       boolean_op::BinaryAnd());
}

//45 degree boolean intersection operator
//works with any combination of 45 and 90
template <typename geometry_type_1, typename geometry_type_2>
typename requires_3<
        typename is_polygon_45_or_90_set_type<geometry_type_1>::type::type,
      typename is_polygon_45_or_90_set_type<geometry_type_2>::type::type,
      typename is_either_polygon_45_set_type<geometry_type_1, ``
                geometry_type_2>::type::type,
      polygon_45_set_view<geometry_type_1, geometry_type_2, 1> >::type
operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
  return polygon_45_set_view<geometry_type_1, geometry_type_2, 1>
      (lvalue, rvalue);
}

//arbitrary angle boolean intersection operator
//works with any combination of arbitrary angle, 45 and 90
template <typename geometry_type_1, typename geometry_type_2>
typename requires_3<
        typename is_any_polygon_set_type<geometry_type_1>::type::type,
      typename is_any_polygon_set_type<geometry_type_2>::type::type,
      typename is_either_polygon_set_type<geometry_type_1,
        geometry_type_2>::type::type,
      polygon_set_view<geometry_type_1, geometry_type_2, 1> >::type
operator&(const geometry_type_1& lvalue, const geometry_type_2& rvalue) {
  return polygon_set_view<geometry_type_1, geometry_type_2, 1>
      (lvalue, rvalue);
}

Is this what you mean by multiple dispatch, Mathias?

I will be checking the complete working code into the sandbox shortly, but I want to make an internal release of it first.

By the way, I notice the boost con deadline for submission abstracts is fast approaching. What would the boost community like to see in a boost con abstract about geometry from me?

Regards,
Luke


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk