1 // Copyright (c) 2000
2 // Utrecht University (The Netherlands),
3 // ETH Zurich (Switzerland),
4 // INRIA Sophia-Antipolis (France),
5 // Max-Planck-Institute Saarbruecken (Germany),
6 // and Tel-Aviv University (Israel). All rights reserved.
7 //
8 // This file is part of CGAL (www.cgal.org)
9 //
10 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Intersections_2/include/CGAL/Intersections_2/internal/Triangle_2_Triangle_2_intersection_impl.h $
11 // $Id: Triangle_2_Triangle_2_intersection_impl.h 8b41189 2020-03-26T18:58:21+01:00 Sébastien Loriot
12 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
13 //
14 //
15 // Author(s) : Geert-Jan Giezeman
16
17 #include <CGAL/Triangle_2.h>
18 #include <CGAL/kernel_assertions.h>
19 #include <CGAL/number_utils.h>
20 #include <vector>
21
22 #include <CGAL/Intersections_2/Line_2_Line_2.h>
23 #include <CGAL/Intersection_traits_2.h>
24 #include <CGAL/Algebraic_structure_traits.h>
25
26 namespace CGAL {
27
28 namespace Intersections {
29
30 namespace internal {
31
32 template <class K>
33 struct Pointlist_2_rec_ {
34 Pointlist_2_rec_ *next;
35 typename K::Point_2 point;
36 Oriented_side side;
37 };
38
39 template <class K>
40 struct Pointlist_2_ {
41 int size;
42 Pointlist_2_rec_<K> *first;
43 Pointlist_2_() ;
44 ~Pointlist_2_() ;
45 };
46
47
48
49 template <class K>
Pointlist_2_()50 Pointlist_2_<K>::Pointlist_2_()
51 {
52 size = 0;
53 first = 0;
54 }
55
56 template <class K>
~Pointlist_2_()57 Pointlist_2_<K>::~Pointlist_2_()
58 {
59 Pointlist_2_rec_<K> *cur;
60 for (int i=0; i<size; i++) {
61 cur = first;
62 first = cur->next;
63 delete cur;
64 }
65 }
66
67
68
69
70 template <class K>
_init_list(Pointlist_2_<K> & list,const typename K::Triangle_2 & trian)71 void _init_list(Pointlist_2_<K> &list,
72 const typename K::Triangle_2 &trian)
73 {
74 // check on degeneracies of trian.
75 if (!trian.is_degenerate()) {
76 list.size = 3;
77 list.first = 0;
78 for (int i=0; i<3; i++) {
79 Pointlist_2_rec_<K> *newrec =
80 new Pointlist_2_rec_<K>;
81 newrec->next = list.first;
82 list.first = newrec;
83 newrec->point = trian[i];
84 }
85 } else {
86 // _not_implemented();
87 CGAL_kernel_assertion(false);
88 }
89 }
90
91
92
93 template <class K>
_cut_off(Pointlist_2_<K> & list,const typename K::Line_2 & cutter)94 void _cut_off(Pointlist_2_<K> &list,
95 const typename K::Line_2 &cutter)
96 {
97 int i;
98 const int list_size=list.size;
99 Pointlist_2_rec_<K> *cur, *last=0, *newrec;
100 for (i=0, cur = list.first; i<list_size; i++, cur = cur->next) {
101 cur->side = cutter.oriented_side(cur->point);
102 last = cur;
103 }
104 for (cur = list.first, i=0; i<list_size; i++, cur = cur->next) {
105 if ((cur->side == ON_POSITIVE_SIDE
106 && last->side == ON_NEGATIVE_SIDE)
107 || (cur->side == ON_NEGATIVE_SIDE
108 && last->side == ON_POSITIVE_SIDE)) {
109 // add a vertex after cur
110 typename K::Line_2 l(cur->point, last->point);
111 ++list.size;
112 newrec = new Pointlist_2_rec_<K>;
113 newrec->next = last->next;
114 last->next = newrec;
115 newrec->side = ON_ORIENTED_BOUNDARY;
116 Line_2_Line_2_pair<K> linepair(&cutter, &l);
117 CGAL_kernel_assertion_code(typename Line_2_Line_2_pair<K>::Intersection_results isr =)
118 linepair.intersection_type();
119 CGAL_kernel_assertion(isr == Line_2_Line_2_pair<K>::POINT);
120 newrec->point = linepair.intersection_point();
121 }
122 last = cur;
123 }
124 CGAL_kernel_assertion(list.size-list_size <= 2);
125 Pointlist_2_rec_<K> **curpt;
126 curpt = &list.first;
127 while (*curpt != 0) {
128 cur = *curpt;
129 if (cur->side == ON_NEGATIVE_SIDE) {
130 --list.size;
131 *curpt = cur->next;
132 delete cur;
133 } else {
134 curpt = &cur->next;
135 }
136 }
137 if (list_size == 2 && list.size-list_size == 1) {
138 --list.size;
139 cur = list.first;
140 if (cur->side == ON_ORIENTED_BOUNDARY) {
141 list.first = cur->next;
142 delete cur;
143 } else {
144 last = cur;
145 cur = cur->next;
146 last->next = cur->next;
147 delete cur;
148 }
149 }
150 }
151
152
153 template <class K>
154 class Triangle_2_Triangle_2_pair {
155 public:
156 enum Intersection_results {NO_INTERSECTION, POINT, SEGMENT, TRIANGLE, POLYGON};
Triangle_2_Triangle_2_pair(typename K::Triangle_2 const * trian1,typename K::Triangle_2 const * trian2)157 Triangle_2_Triangle_2_pair(typename K::Triangle_2 const *trian1,
158 typename K::Triangle_2 const *trian2)
159 : _trian1(trian1), _trian2(trian2), _known(false) {}
160
161 Intersection_results intersection_type() const;
162
163 typename K::Point_2 intersection_point() const;
164 typename K::Segment_2 intersection_segment() const;
165 typename K::Triangle_2 intersection_triangle() const;
166 bool intersection(/*Polygon_2<R> &result*/) const;
167 int vertex_count() const;
168 typename K::Point_2 vertex(int i) const;
169 protected:
170 typename K::Triangle_2 const* _trian1;
171 typename K::Triangle_2 const * _trian2;
172 mutable bool _known;
173 mutable Intersection_results _result;
174 mutable Pointlist_2_<K> _pointlist;
175 };
176
177 template <class K>
178 typename Triangle_2_Triangle_2_pair<K>::Intersection_results
intersection_type()179 Triangle_2_Triangle_2_pair<K>::intersection_type() const
180 {
181 typedef typename K::Line_2 Line_2;
182 if (_known)
183 return _result;
184 // The non const this pointer is used to cast away const.
185 _known = true;
186 if (!do_overlap(_trian1->bbox(), _trian2->bbox())) {
187 _result = NO_INTERSECTION;
188 return _result;
189 }
190 _init_list(_pointlist, *_trian1);
191 if (_trian2->is_degenerate()) {
192 // _not_implemented();
193 CGAL_kernel_assertion(false);
194 } else {
195 Line_2 l(_trian2->vertex(0), _trian2->vertex(1));
196 if (l.oriented_side(_trian2->vertex(2)) == ON_POSITIVE_SIDE) {
197 // counterclockwise triangle
198 _cut_off(_pointlist, l);
199 l = Line_2(_trian2->vertex(1), _trian2->vertex(2));
200 _cut_off(_pointlist, l);
201 l = Line_2(_trian2->vertex(2), _trian2->vertex(0));
202 _cut_off(_pointlist, l);
203 } else {
204 l = l.opposite();
205 _cut_off(_pointlist, l);
206 l = Line_2(_trian2->vertex(0), _trian2->vertex(2));
207 _cut_off(_pointlist, l);
208 l = Line_2(_trian2->vertex(2), _trian2->vertex(1));
209 _cut_off(_pointlist, l);
210 }
211 }
212 switch (_pointlist.size) {
213 case 0:
214 _result = NO_INTERSECTION;
215 break;
216 case 1:
217 _result = POINT;
218 break;
219 case 2:
220 _result = SEGMENT;
221 break;
222 case 3:
223 _result = TRIANGLE;
224 break;
225 default:
226 _result = POLYGON;
227 }
228 return _result;
229 }
230
231
232 template <class K>
233 bool
intersection()234 Triangle_2_Triangle_2_pair<K>::intersection(
235 /* Polygon_2<R> &result */) const
236 {
237 if (!_known)
238 intersection_type();
239 if (_result != TRIANGLE && _result != POLYGON)
240 return false;
241 Pointlist_2_rec_<K> *cur;
242 int i;
243 for (i=0, cur = _pointlist.first;
244 i<_pointlist.size;
245 i++, cur = cur->next) {
246 std::cout << to_double(cur->point.x()) << ' ';
247 std::cout << to_double(cur->point.y()) << ' ';
248 }
249 std::cout << std::endl;
250 return true;
251 }
252
253 template <class K>
254 int
vertex_count()255 Triangle_2_Triangle_2_pair<K>::vertex_count() const
256 {
257 CGAL_kernel_assertion(_known);
258 return _pointlist.size;
259 }
260
261 template <class K>
262 typename K::Point_2
vertex(int n)263 Triangle_2_Triangle_2_pair<K>::vertex(int n) const
264 {
265 CGAL_kernel_assertion(_known);
266 CGAL_kernel_assertion(n >= 0 && n < _pointlist.size);
267 Pointlist_2_rec_<K> *cur;
268 int k;
269 for (k=0, cur = _pointlist.first;
270 k < n;
271 k++, cur = cur->next) {
272 }
273 return cur->point;
274 }
275
276 template <class K>
277 typename K::Triangle_2
intersection_triangle()278 Triangle_2_Triangle_2_pair<K>::intersection_triangle() const
279 {
280 typedef typename K::Triangle_2 Triangle_2;
281 if (!_known)
282 intersection_type();
283 CGAL_kernel_assertion(_result == TRIANGLE);
284 if(CGAL::left_turn(_pointlist.first->point,
285 _pointlist.first->next->point,
286 _pointlist.first->next->next->point))
287 {
288 return Triangle_2(_pointlist.first->point,
289 _pointlist.first->next->point,
290 _pointlist.first->next->next->point);
291 }
292 else {
293 return Triangle_2(_pointlist.first->point,
294 _pointlist.first->next->next->point,
295 _pointlist.first->next->point);
296 }
297 }
298
299 template <class K>
300 typename K::Segment_2
intersection_segment()301 Triangle_2_Triangle_2_pair<K>::intersection_segment() const
302 {
303 typedef typename K::Segment_2 Segment_2;
304 if (!_known)
305 intersection_type();
306 CGAL_kernel_assertion(_result == SEGMENT);
307 return Segment_2(_pointlist.first->point,
308 _pointlist.first->next->point);
309 }
310
311 template <class K>
312 typename K::Point_2
intersection_point()313 Triangle_2_Triangle_2_pair<K>::intersection_point() const
314 {
315 if (!_known)
316 intersection_type();
317 CGAL_kernel_assertion(_result == POINT);
318 return _pointlist.first->point;
319 }
320
321
322 //algorithm taken from here : https://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order
323 template <typename K, typename Exact>
324 struct Is_cw
325 {
operatorIs_cw326 bool operator()(const std::vector<typename K::Point_2>& ps)
327 {
328 typename K::FT res(0);
329 std::size_t length = ps.size();
330 for(std::size_t i = 0; i<length; ++i)
331 res += (ps[(i+1)%length].x() - ps[i].x())*(ps[(i+1)%length].y()+ps[i].y());
332
333 return res > 0;
334 }
335 };
336
337 template <typename K>
338 struct Is_cw<K, Tag_true>
339 {
340 bool operator()(const std::vector<typename K::Point_2>& ps)
341 {
342 return CGAL::right_turn(ps[0], ps[1], ps[2]);
343 }
344 };
345
346 template <class K>
347 typename CGAL::Intersection_traits
348 <K, typename K::Triangle_2, typename K::Triangle_2>::result_type
349 intersection(const typename K::Triangle_2 &tr1,
350 const typename K::Triangle_2 &tr2,
351 const K&)
352 {
353 typedef Triangle_2_Triangle_2_pair<K> Intersection_type;
354 Intersection_type ispair(&tr1, &tr2);
355 switch (ispair.intersection_type())
356 {
357 case Intersection_type::NO_INTERSECTION:
358 default:
359 return intersection_return<typename K::Intersect_2, typename K::Triangle_2, typename K::Triangle_2>();
360 case Intersection_type::POINT:
361 return intersection_return<typename K::Intersect_2, typename K::Triangle_2, typename K::Triangle_2>(ispair.intersection_point());
362 case Intersection_type::SEGMENT:
363 return intersection_return<typename K::Intersect_2, typename K::Triangle_2, typename K::Triangle_2>(ispair.intersection_segment());
364 case Intersection_type::TRIANGLE:
365 return intersection_return<typename K::Intersect_2, typename K::Triangle_2, typename K::Triangle_2>(ispair.intersection_triangle());
366 case Intersection_type::POLYGON:
367 {
368 typedef std::vector<typename K::Point_2> Container;
369 Container points(ispair.vertex_count());
370 for (int i =0; i < ispair.vertex_count(); i++)
371 points[i] = ispair.vertex(i);
372
373 if(Is_cw<K, typename Algebraic_structure_traits<typename K::FT>::Is_exact>()(points))
374 {
375 std::reverse(points.begin(), points.end());
376
377 }
378 return intersection_return<typename K::Intersect_2, typename K::Triangle_2, typename K::Triangle_2>(points);
379 }
380 }
381 }
382
383 } // namespace internal
384 } // namespace Intersections
385 } //namespace CGAL
386