\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 5.0.1 - Intersecting Sequences of dD Iso-oriented Boxes
Box_intersection_d/box_d_do_intersect_polylines.cpp
#include <vector>
#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
template <typename Polyline>
class Polylines_do_intersect
{
typedef typename Polyline::const_iterator Iterator;
typedef typename std::iterator_traits<Iterator>::value_type Point_2;
typedef CGAL::Bbox_2 Bbox_2;
const Polyline& pA, &pB;
struct Box : public CGAL::Box_intersection_d::Box_with_handle_d<double,2,Iterator> {
Box( const Bbox_2& b, Iterator it)
: Base(b,it)
{}
};
class FirstIntersection
{};
class Overlap {
const Polyline& pA, &pB;
public:
Overlap(const Polyline& pA, const Polyline& pB)
: pA(pA), pB(pB)
{}
void operator()(const Box& a, const Box& b) {
Segment_2 sa(*(a.handle()), *(++(a.handle())));
Segment_2 sb(*(b.handle()), *(++(b.handle())));
if(CGAL::do_intersect(sa,sb)){
throw FirstIntersection();
}
}
};
public:
Polylines_do_intersect(const Polyline& pA, const Polyline& pB)
: pA(pA), pB(pB)
{}
bool operator()() const
{
std::vector<Box> bA, bB;
bA.reserve(pA.size() - 1 );
bB.reserve(pB.size() - 1 );
Iterator begin = pA.begin();
for(std::size_t j=0; j < pA.size()-1; j++){
Bbox_2 bb = pA[j].bbox() + pA[j+1].bbox();
bA.push_back(Box(bb, begin+j));
}
begin = pB.begin();
for(std::size_t j=0; j < pB.size()-1; j++){
Bbox_2 bb = pB[j].bbox() + pB[j+1].bbox();
bB.push_back(Box(bb, begin+j));
}
Overlap overlap(pA,pB);
try {
CGAL::box_intersection_d( bA.begin(), bA.end(), bB.begin(), bB.end(), overlap);
} catch(const FirstIntersection& ) {
return true;
}
return false;
}
};
template <typename Polyline>
bool polylines_do_intersect(const Polyline& pA,const Polyline& pB)
{
Polylines_do_intersect<Polyline> pdi(pA,pB);
return pdi();
}
typedef K::Point_2 Point_2;
typedef std::vector<Point_2> Polyline;
int main()
{
Polyline pA = { Point_2(0,0), Point_2(1,0) };
Polyline pB = { Point_2(0,0), Point_2(0,1), Point_2(2,1) , Point_2(1,0)};
if(polylines_do_intersect(pA,pB)){
std::cout << "intersection" << std::endl;
} else {
std::cout << "no intersection" << std::endl;
}
return 0;
}