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