1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#include <vector>
#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/box_intersection_d.h>
template <typename Poly>
class Polylines_do_intersect
{
typedef typename Poly::const_iterator Iterator;
typedef typename std::iterator_traits<Iterator>::value_type Point_2;
typedef typename CGAL::Kernel_traits<Point_2>::Kernel::Segment_2 Segment_2;
typedef CGAL::Bbox_2 Bbox_2;
const Poly& pA, &pB;
struct Box : public CGAL::Box_intersection_d::Box_with_handle_d<double,2,Iterator> {
typedef CGAL::Box_intersection_d::Box_with_handle_d<double,2,Iterator> Base;
Box( const Bbox_2& b, Iterator it)
: Base(b,it)
{}
};
class FirstIntersection
{};
class Overlap {
const Poly& pA, &pB;
public:
Overlap(const Poly& pA, const Poly& 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 Poly& pA, const Poly& 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 Poly>
bool polylines_do_intersect(const Poly& pA,const Poly& pB)
{
Polylines_do_intersect<Poly> pdi(pA,pB);
return pdi();
}
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::vector<Point_2> CGAL_polyline;
int main()
{
CGAL_polyline pA = { Point_2(0,0), Point_2(1,0) };
CGAL_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;
}
|
