Предположим, вам нужна программа на C++ для расчета расстояния между двумя точками. Вы можете определить структуру:
struct mypoint
{
double x, y;
};
и функция, содержащая алгоритм:
double distance(mypoint const& a, mypoint const& b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
Довольно просто, и она пригодна для использования, но не универсальна. Для библиотеки она должна быть разработана более детально. Конструкция выше может использоваться только для 2D точек, для структуры mypoint (и никакой другой структуры), в картезианской системе координат. Общая библиотека должна быть в состоянии рассчитать расстояние:
- для любого класса точек или структуры, а не только для этого типа mypoint
- более чем в двух измерениях
- для других систем координат, например, над землей или на сфере
- между точкой и линией или между другими комбинациями геометрии
- с более высокой точностью, чем double
- избегание квадратного корня: часто мы не хотим этого делать, потому что это относительно дорогая функция, и для сравнения расстояний это не нужно
В этом и последующих разделах мы шаг за шагом сделаем дизайн более общим.
Функция расстояния может быть преобразована в функцию шаблона. Это тривиально и позволяет вычислить расстояние между другими типами точек, чем просто моя точка. Мы добавляем два параметра шаблона, позволяя вводить два разных типа точек.
template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return std::sqrt(dx * dx + dy * dy);
}
Эта версия шаблона немного лучше, но ненамного.
Рассмотрим класс C++, где переменные членов защищены. Такой класс не позволяет напрямую получить доступ к членам x и y. Этот пункт короткий, и мы просто двигаемся дальше.
Мы должны использовать общий подход и разрешить любой тип точки в качестве входа в функцию расстояния. Вместо доступа к элементам x и y, мы добавим несколько уровней косвенности, используя систему признаков. Затем функция становится:
template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
double dx = get<0>(a) - get<0>(b);
double dy = get<1>(a) - get<1>(b);
return std::sqrt(dx * dx + dy * dy);
}
Эта адаптированная функция расстояния использует общую функцию получения, с измерением в качестве шаблонного параметра, для доступа к координатам точки. Это переходит к системе признаков, определяемой следующим образом:
namespace traits
{
template <typename P, int D>
struct access {};
}
который затем специализирован для нашего типа mypoint, реализуя статический метод, называемый get:
namespace traits
{
template <>
struct access<mypoint, 0>
{
static double get(mypoint const& p)
{
return p.x;
}
};
...
}
Вызов признаков::доступ<моя точка,0>::get(a) возвращает нам нашу координату x. Мило, правда? Это слишком многословно для такой функции, часто используемой в библиотеке. Мы можем сократить синтаксис, добавив дополнительную бесплатную функцию:
template <int D, typename P>
inline double get(P const& p)
{
return traits::access<P, D>::get(p);
}
Это позволяет нам вызывать get<0>(a) для любой точки, имеющей признаки::специализация доступа, как показано в алгоритме расстояния в начале этого пункта. Поэтому мы хотели включить классы с такими методами, как x(), и они поддерживаются до тех пор, пока существует специализация доступа структура со статической функцией get, возвращающей x() для размерности 0 и аналогичной для 1 и y().
Теперь мы можем рассчитать расстояние между точками в 2D, точками любой структуры или класса. Но мы хотели иметь и 3D. Поэтому мы должны сделать это измерение агностическим. Это усложняет нашу дистанционную функцию. Мы можем использовать петлю для , чтобы пройти через измерения, но для петлей есть другая производительность, чем простое сложение координат, которое было там изначально. Тем не менее, мы можем больше использовать шаблоны и сделать алгоритм расстояния более сложным, но привлекательным для любителей шаблонов
template <typename P1, typename P2, int D>
struct pythagoras
{
static double apply(P1 const& a, P2 const& b)
{
double d = get<D-1>(a) - get<D-1>(b);
return d * d + pythagoras<P1, P2, D-1>::apply(a, b);
}
};
template <typename P1, typename P2 >
struct pythagoras<P1, P2, 0>
{
static double apply(P1 const&, P2 const&)
{
return 0;
}
};
Функция расстояния называет эту структуру pythagoras, указывая число измерений:
template <typename P1, typename P2>
double distance(P1 const& a, P2 const& b)
{
BOOST_STATIC_ASSERT(( dimension<P1>::value == dimension<P2>::value ));
return sqrt(pythagoras<P1, P2, dimension<P1>::value>::apply(a, b));
}
Упомянутое измерение определяется с использованием другого класса признаков:
namespace traits
{
template <typename P>
struct dimension {};
}
который должен быть снова специализирован для структуры mypoint.
Поскольку он должен публиковать только значение, мы удобно извлекаем его из Роста. MPL class boost::mpl::int_
namespace traits
{
template <>
struct dimension<mypoint> : boost::mpl::int_<2>
{};
}
Как и функция свободного доступа, библиотека также содержит метафункцию измерения.
template <typename P>
struct dimension : traits::dimension<P>
{};
Ниже объясняется, почему дополнительная декларация полезна. Теперь мы имеем агностицизм в числе измерений. Наша более общая функция расстояния теперь принимает точки трех или более измерений. Утверждение времени компиляции предотвратит точку a, имеющую два измерения, и точку b, имеющую три измерения.
Мы приняли двойное решение. Что, если наши точки целы?
Мы можем легко добавить класс черт, и мы сделаем это. Однако расстояние между двумя целыми координатами все еще может быть дробным значением. Кроме того, целью дизайна было избежать квадратных корней. Мы рассматриваем эти случаи ниже, в другом пункте. На данный момент мы продолжаем возвращаться дважды, но мы допускаем целые координаты для наших типов точек. Для определения типа координат добавляем еще один класс признаков coordinate_type, который должен быть специализирован пользователем библиотеки:
namespace traits
{
template <typename P>
struct coordinate_type{};
template <>
struct coordinate_type<mypoint>
{
typedef double type;
};
}
Как и функция доступа, где у нас была функция бесплатного доступа, мы также добавляем прокси. Более длинная версия представлена позже, короткая функция будет выглядеть так:
template <typename P>
struct coordinate_type : traits::coordinate_type<P> {};
Теперь мы можем снова изменить алгоритм расстояний. Поскольку он все еще возвращается вдвое, мы только модифицируем класс вычислений pythagoras. Он должен возвращать тип координат своего входа. Но у него есть два входных, возможно, разных типа точек. Они также могут различаться по типу координат. Не то, чтобы это было очень вероятно, но мы разрабатываем общую библиотеку и должны заниматься этими странными делами. Мы должны выбрать один из типов координат, и, конечно же, мы выбираем тот, который имеет самую высокую точность. Это здесь не проработано, это было бы слишком долго, и это не связано с геометрией. Мы просто предполагаем, что существует метафункция select_most_precise, выбирающая лучший тип.
Таким образом, наш класс вычислений становится:
template <typename P1, typename P2, int D>
struct pythagoras
{
typedef typename select_most_precise
<
typename coordinate_type<P1>::type,
typename coordinate_type<P2>::type
>::type computation_type;
static computation_type apply(P1 const& a, P2 const& b)
{
computation_type d = get<D-1>(a) - get<D-1>(b);
return d * d + pythagoras <P1, P2, D-1> ::apply(a, b);
}
};
Мы разработали систему агностической размерности, поддерживающую любой точечный тип любого типа координат. Есть еще некоторые изменения, но они будут разработаны позже. Теперь мы увидим, как мы вычисляем расстояние между точкой и многоугольником, или между точкой и линейным сегментом. Эти формулы более сложны, а влияние на дизайн еще больше. Мы не хотим добавлять функцию с другим именем #8217
template <typename P, typename S>
double distance_point_segment(P const& p, S const& s)
Мы хотим быть общими, функция расстояния должна быть названа из кода, не зная тип геометрии, с которой она обрабатывает, поэтому она должна быть названа расстоянием. Мы также не можем создать перегрузку, потому что это было бы неоднозначно, имея одинаковую подпись шаблона. Есть два решения:
Мы выбираем отправку тегов, потому что она вписывается в систему признаков. Более ранние версии (превью) Boost. Геометрия использовала SFINAE, но мы обнаружили, что у нее было несколько недостатков для такого большого дизайна, поэтому был сделан переход на диспетчеризацию тегов.
При диспетчеризации меток алгоритм расстояния проверяет тип геометрии входных параметров. Функция расстояния будет изменена следующим образом:
template <typename G1, typename G2>
double distance(G1 const& g1, G2 const& g2)
{
return dispatch::distance
<
typename tag<G1>::type,
typename tag<G2>::type,
G1, G2
>::apply(g1, g2);
}
Это относится к метафункции тега и переадресации вызова на метод apply dispatch::distance. Мета-функция tag является еще одним классом признаков и должна быть специализирована для каждого типа точек
namespace traits
{
template <typename G>
struct tag {};
template <>
struct tag<mypoint>
{
typedef point_tag type;
};
}
Бесплатные мета-функции, такие как Coordinat_system и получить:
template <typename G>
struct tag : traits::tag<G> {};
Тэги (point_tag, segment_tag и т.д.) представляют собой пустые структуры с целью специализации структуры отправки. Дистанционная структура и ее специализация определяются в отдельном пространстве имен и выглядят следующим образом:
namespace dispatch {
template < typename Tag1, typename Tag2, typename G1, typename G2 >
struct distance
{};
template <typename P1, typename P2>
struct distance < point_tag, point_tag, P1, P2 >
{
static double apply(P1 const& a, P2 const& b)
{
...
}
};
template <typename P, typename S>
struct distance
<
point_tag, segment_tag, P, S
>
{
static double apply(P const& p, S const& s)
{
...
}
};
}
Так что да, это возможно; алгоритм расстояния теперь является общим в том смысле, что он также поддерживает различные типы геометрии. Один недостаток: мы должны определить две диспетчерские специализации для точки - сегмента и для сегмента - точки отдельно. Это также будет решено в пункте обратимости ниже. Приведенный ниже пример показывает, где мы находимся сейчас: различные типы точек, типы геометрии, размеры.
point a(1,1);
point b(2,2);
std::cout << distance(a,b) << std::endl;
segment s1(0,0,5,3);
std::cout << distance(a, s1) << std::endl;
rgb red(255, 0, 0);
rbc orange(255, 128, 0);
std::cout << "color distance: " << distance(red, orange) << std::endl;
Мы описали выше, что у нас был класс признаков coordinate_type, определенный в чертах пространства имен, а также отдельный класс coordinate_type. Раньше в этом не было необходимости, потому что единственным отличием было положение о пространстве имен. Но теперь, когда у нас есть другой тип геометрии, сегмент в данном случае, это важно. Метафункцию coordinate_type можно назвать метафункцией для любого типа геометрии, точки, сегмента, полигона и т.д
template <typename G>
struct coordinate_type
{
typedef typename dispatch::coordinate_type
<
typename tag<G>::type, G
>::type type;
};
Внутри пространства имен диспетчера эта метафункция реализуется дважды: общая версия и одна специализация для точек. Специализация по точкам называется классом признаков. Общая версия называет специализацию точки своего рода рекурсивным определением метафункции:
namespace dispatch
{
template <typename GeometryTag, typename G>
struct coordinate_type
{
typedef typename point_type
<
GeometryTag, G
>::type point_type;
typedef typename coordinate_type < point_tag, point_type >::type type;
};
template <typename P>
struct coordinate_type<point_tag, P>
{
typedef typename
traits::coordinate_type<P>::type
type;
};
}
Это называется еще одной метафункцией point_type. Это не проработано здесь, но поймите, что он доступен для всех типов геометрии, и наберите тип точки, который составляет геометрию, называя его типом.
То же самое относится к размерности метафункции и к предстоящей системе координат метафункции.
До этого мы предполагали картезианскую систему. Но мы знаем, что Земля не плоская. Вычисление расстояния между двумя GPS-точками с системой выше приведет к абсурду. Мы снова расширяем наш дизайн. Для каждого типа точек мы определяем тип системы координат, используя систему признаков. Затем вычисление зависит от этой системы координат.
Координационная система подобна координационному типу, метафункции, вызывающей диспетчерскую функцию, чтобы иметь ее для любого геометрического типа, пересылающей к ее точечной специализации и, наконец, вызывающей класс признаков, определяющий тип с системой координат. Мы не 8217, мы показываем это снова. Мы лишь показываем определение нескольких систем координат:
struct cartesian {};
template<typename DegreeOrRadian>
struct geographic
{
typedef DegreeOrRadian units;
};
Таким образом, декартовы координаты просты, поскольку географически мы также можем выбрать, хранятся ли их координаты в градусах или в радианах.
Функция расстояния теперь изменится: она выберет метод вычисления для соответствующей системы координат, а затем вызовет схему диспетчеризации для расстояния. Метод вычисления, специализирующийся на системах координат, мы называем стратегией. Итак, новая версия функции расстояния:
template <typename G1, typename G2>
double distance(G1 const& g1, G2 const& g2)
{
typedef typename strategy_distance
<
typename coordinate_system<G1>::type,
typename coordinate_system<G2>::type,
typename point_type<G1>::type,
typename point_type<G2>::type,
dimension<G1>::value
>::type strategy;
return dispatch::distance
<
typename tag<G1>::type,
typename tag<G2>::type,
G1, G2, strategy
>::apply(g1, g2, strategy());
}
Упомянутая здесь стратегическая дистанция представляет собой структуру со специализацией для различных систем координат.
template <typename T1, typename T2, typename P1, typename P2, int D>
struct strategy_distance
{
typedef void type;
};
template <typename P1, typename P2, int D>
struct strategy_distance<cartesian, cartesian, P1, P2, D>
{
typedef pythagoras<P1, P2, D> type;
};
Итак, вот наш пифагор снова, теперь определяемый как стратегия. Дистанционная диспетчерская функция просто называет свой метод применения.
Так что это важный шаг: для сферических или географических систем координат может быть реализована другая стратегия (вычислительный метод). Для сферических координат системы имеют формулу хересина. Таким образом, структура диспетчерских черт специализировалась на этом
template <typename P1, typename P2, int D = 2>
struct strategy_distance<spherical, spherical, P1, P2, D>
{
typedef haversine<P1, P2> type;
};
Для географии у нас есть несколько вариантов расчёта расстояний. Есть метод Андойера, быстрый и точный, есть метод Винсенти, более медленный и более точный, и есть некоторые менее точные подходы.
В системе координат одна стратегия определяется как стратегия по умолчанию. Чтобы использовать другую стратегию, мы снова изменяем наш дизайн и добавляем перегрузку для алгоритма расстояния, принимая объект стратегии в качестве третьего параметра.
Эта новая функция расстояния перегрузки также имеет то преимущество, что стратегия может быть построена за пределами функции расстояния. Поскольку он был построен внутри, он не мог иметь параметров конструкции. Но для Эндойера, Винсенти или формулы хересина, безусловно, имеет смысл иметь конструктора, принимающего радиус Земли в качестве параметра.
Таким образом, перегруженная функция расстояния:
template <typename G1, typename G2, typename S>
double distance(G1 const& g1, G2 const& g2, S const& strategy)
{
return dispatch::distance
<
typename tag<G1>::type,
typename tag<G2>::type,
G1, G2, S
>::apply(g1, g2, strategy);
}
Стратегия должна иметь метод, использующий два момента в качестве аргументов (для точек). Не обязательно, что это статический метод. Стратегия может определять конструктор, где значение конфигурации передается и хранится в качестве переменной члена. В таких случаях статический метод будет неудобным. Она может быть реализована как обычный метод (с квалификатором const).
Мы не перечислим здесь все реализации, Винсенти охватил бы полстраницы математики, но вы поймете идею. Расстояние можно назвать таким:
distance(c1, c2)
где c1 и c2 являются картезианскими точками или вот так:
distance(g1, g2)
где g1 и g2 являются географическими точками, называя стратегию по умолчанию для географических точек (например, Andoyer), и вот так:
distance(g1, g2, vincenty<G1, G2>(6275))
где стратегия четко определена и построена с радиусом.
Пять классов признаков, упомянутых в предыдущих разделах, образуют вместе понятие точки. Любой тип точки, для которого специализации реализуются в пространстве имен признаков, должен быть принят в качестве действительного типа. Таким образом, концепция точки состоит из:
- специализация для
признаков::тег - специализация для
признаков::координировать_систему - специализация для
признаков::координировать_тип - специализация для
признаков::измерение
Последний представляет собой класс, содержащий метод get и (необязательный) набор методов, первые четыре являются метафункциями, либо определяющими тип, либо декларирующими значение (соответствуют конвенциям MPL).
Таким образом, у нас теперь есть агностицизм для числа измерений, агностицизм для систем координат; дизайн может обрабатывать любой тип координат, и он может обрабатывать различные типы геометрии. Кроме того, код не будет компилироваться в случае двух точек с разными размерами (из-за утверждения), и он не будет компилироваться для двух точек с разными системами координат (потому что нет специализации). Библиотека может проверить, соответствует ли тип точки требованиям, предъявляемым концепциями. Об этом говорится в разделе Проверка концепции.
Мы обещали, что вызов std::sqrt не всегда был необходим. Таким образом, мы определяем результат расстояния структура , которая содержит квадратное значение и может быть преобразована в двойное значение. Однако это нужно делать только для пифагора. Функции сферического расстояния не принимают квадратный корень, поэтому для них не нужно избегать дорогостоящего вызова квадратного корня; они могут просто вернуть свое расстояние.
Таким образом, структура результата расстояния зависит от стратегии, поэтому она является типом стратегии. Структура результата выглядит так:
template<typename T = double>
struct cartesian_distance
{
T sq;
explicit cartesian_distance(T const& v) : sq (v) {}
inline operator T() const
{
return std::sqrt(sq);
}
};
У него также есть операторы, которые сравнивают себя с другими результатами, не принимая квадратный корень.
Каждая стратегия должна определять тип возврата в классе стратегии, например:
typedef cartesian_distance<T> return_type;
или:
typedef double return_type;
для картезианских (пифагор) и сферических, соответственно.
Наша функция расстояния будет изменена, как и ожидалось, чтобы отразить новый тип возврата. Для перегрузки стратегией это не сложно:
template < typename G1, typename G2, typename Strategy >
typename Strategy::return_type distance( G1 const& G1 , G2 const& G2 , S const& strategy)
Но для того, у кого нет стратегии, мы должны выбрать стратегию, тип координат и т.д. Было бы просторно сделать это в одной строке, поэтому мы добавим отдельную метафункцию:
template <typename G1, typename G2 = G1>
struct distance_result
{
typedef typename point_type<G1>::type P1;
typedef typename point_type<G2>::type P2;
typedef typename strategy_distance
<
typename cs_tag<P1>::type,
typename cs_tag<P2>::type,
P1, P2
>::type S;
typedef typename S::return_type type;
};
изменить функцию расстояния:
template <typename G1, typename G2>
inline typename distance_result<G1, G2>::type distance(G1 const& g1, G2 const& g2)
{
}
Конечно, и прикладные функции в диспетчерских специализациях вернут такой результат. У них есть стратегия в качестве шаблонного параметра везде, что делает менее многословную версию возможной.
В этом обосновании дизайна, Boost. Геометрия шаг за шагом разработана с использованием диспетчеризации тегов, концепций, черт и метапрограммирования. Мы использовали известную функцию расстояния, чтобы показать дизайн.
Повышаю. Геометрия разработана так, как описано здесь, с некоторыми другими методами, такими как автоматическое изменение аргументов шаблона, литье тегов и повторное использование классов реализации или классов отправки в качестве политик в других классах отправки.
