История изменений
Исправление nikitos, (текущая версия) :
class Segment
{
// ...
public:
int intersects ( Segment const& o ) const throw()
{
return left() <= o.right() && o.left() <= right();
}
};
class IntersectTest
{
Segment m_seg;
public:
IntersectTest ( Segment const& seg ) throw() : m_seg(seg)
{
}
int operator()(Segment const& other ) const throw()
{
return m_seg.intersects(other);
}
};
std::vector<Segment> seg;
// заполняем тут массив seg сегментами
Segment pattern; // инициализируем сегмент, пересечение с которым проверяем
// получаем диапазон сегментов, которые пересекают заданный.
std::vector<Segment>::iterator last_intersected = std::partition ( seg.begin(), seg.end(), IntersectTest(pattern) );
Можно partition разбить на 2 вызова, сделав не одну функцию а 2-полу теста из Segment::intersects. С этой же идеей - городить деревянные структуры в памяти. У меня сегменты хранятся в виде 64-битных значений: старшие 32 бита - длина отрезка, младшие 32 - его начало, все целочисельное. Работает достаточно быстро для моих применений.
Исходная версия nikitos, :
class Segment
{
// ...
public:
int intersects ( Segment const& o ) const throw()
{
return left() <= o.right() && o.left() <= right();
}
};
class IntersectTest
{
Segment m_seg;
public:
IntersectTest ( Segment const& seg ) throw() : m_seg(seg)
{
}
int operator()(Segment const& other ) const throw()
{
return m_seg.intersects(other);
}
};
std::vector<Segment> seg;
// заполняем тут массив seg сегментами
Segment pattern; // инициализируем сегмент, пересечение с которым проверяем
// получаем диапазон сегментов, которые пересекают заданный.
std::vector<Segment>::iterator last_intersected = std::partition ( seg.begin(), seg.end(), IntersectTest(pattern) );