acme
Foundational cross-platform layer of the ca2 framework
Loading...
Searching...
No Matches
polygon.h
1#pragma once
2
3
4//#include "_collection.h"
5//#include "_geometry2d.h"
6#include "point_array.h"
7#include "rectangle.h"
8
9
10template < prototype_number NUMBER >
11class polygon_base :
12 public point_array_base < NUMBER >
13{
14public:
15
16
17 using BASE_ARRAY = point_array_base < NUMBER >;
18
19 //using POLYGON_BASE_TYPE = point_array_base < NUMBER >;
20 //using POINT_BASE_TYPE = POINT_TYPE;
21 using UNIT_TYPE = NUMBER;
22 //using SIZE_TYPE = typename POINT_TYPE::SIZE_TYPE;
23 //using RECTANGLE_TYPE = typename POINT_TYPE::RECTANGLE_TYPE;
24 //using RECTANGLE_BASE_TYPE = typename RECTANGLE_TYPE::RECTANGLE_BASE_TYPE;
25
26
27 bool m_bDirty;
28 bool m_bDirtyBoundingRect;
29 ::rectangle_type < NUMBER > m_rectangleBounding;
30
31
32 polygon_base();
33 polygon_base(const polygon_base & polygon);
34 polygon_base(polygon_base&& polygon);
35 ~polygon_base();
36
37 template < prototype_rectangle RECTANGLE >
38 polygon_base & operator = (const RECTANGLE & rectangle)
39 {
40
41 m_rectangleBounding = rectangle;
42
43 this->set_size(4);
44
45 this->element_at(0) = m_rectangleBounding.top_left();
46 this->element_at(1) = m_rectangleBounding.top_right();
47 this->element_at(2) = m_rectangleBounding.bottom_right();
48 this->element_at(3) = m_rectangleBounding.bottom_left();
49
50 m_bDirty = false;
51 m_bDirtyBoundingRect = false;
52
53 return *this;
54
55 }
56
57
58 void rotate(::f64 dAngle)
59 {
60
61 point_array_base < NUMBER >::rotate(dAngle);
62 m_bDirtyBoundingRect = true;
63
64 }
65
66
67 void rotate(::f64 dAngle, ::point_type < UNIT_TYPE > pointCenter)
68 {
69
70 point_array_base < NUMBER >::rotate(dAngle, pointCenter);
71 m_bDirty = true;
72 m_bDirtyBoundingRect = true;
73
74 }
75
76
77
78 void check_dirty()
79 {
80
81 if (m_bDirty)
82 {
83 m_bDirty = false;
84 m_bDirtyBoundingRect = true;
85
86 }
87
88 }
89
90 const ::rectangle_type < NUMBER > & bounding_rect() const;
91
92 bool overlaps(const polygon_base & i32_polygon) const;
93
94 polygon_base convex_intersection(const polygon_base & polygon) const;
95
96 // sort clockwise
97 void sort();
98
99 bool bounding_rectangle_contains(const ::point_type < NUMBER > & point) const;
100
101 bool contains(const ::point_type < NUMBER > & point) const
102 {
103
104 return point_array_base < NUMBER >::polygon_contains_winding(point);
105
106 }
107
108 bool contains_alternate(const ::point_type < NUMBER > & point) const
109 {
110
111 return point_array_base < NUMBER >::polygon_contains_alternate(point);
112
113 }
114
115 polygon_base& operator = (const polygon_base& i32_polygon);
116 polygon_base& operator = (polygon_base&& i32_polygon);
117
118
119
120
121};
122
123template < prototype_number NUMBER >
124inline polygon_base < NUMBER >::polygon_base(const polygon_base& polygon) :
125point_array_base < NUMBER >(polygon)
126{
127
128}
129
130template < prototype_number NUMBER >
131inline polygon_base < NUMBER >::polygon_base(polygon_base&& polygon) :
132 point_array_base < NUMBER >(::transfer(polygon))
133{
134
135 m_bDirty = polygon.m_bDirty;
136 m_bDirtyBoundingRect = polygon.m_bDirtyBoundingRect;
137 m_rectangleBounding = polygon.m_rectangleBounding;
138
139}
140
141template < prototype_number NUMBER >
142inline bool polygon_base < NUMBER >::bounding_rectangle_contains(const ::point_type < NUMBER > & point) const
143{
144
145 return this->bounding_rect().contains(point);
146
147}
148
149
150inline ::f64 atan(const ::f64_point & point, ::f64 x, ::f64 y)
151{
152
153 return ::atan2(point.y - y, point.x - x);
154
155}
156
157//https://www.swtestacademy.com/intersection-convex-polygons-algorithm/
158// Sinan Oz is an experienced IT professional who has a big passion on software science and algorithms since he attended International Olympiads in Informatics in his early ages.He finished Istanbul Technical University Computer Engineering Department.He worked at Garanti Technology, one of the biggest technology centres in the country for about 5 years.After that, he started Kariyer.net and takes some serious projects as a Lead Architect and he promoted as a Software Development Manager.Currently, he is working at Movie Star Planet Kopenhagen office as a Senior Backend Game Developer.
159template < prototype_number NUMBER >
160void polygon_base < NUMBER >::sort()
161{
162
163 UNIT_TYPE x = 0;
164 UNIT_TYPE y = 0;
165
166 for (auto & point : *this)
167 {
168 x += point.x;
169 y += point.y;
170 }
171
172 x /= this->get_count();
173 y /= this->get_count();
174
175 this->predicate_sort([x, y](auto & point1, auto & point2) { return atan(point1, x, y) >= atan(point2, x, y); });
176
177}
178
179
180template < prototype_number NUMBER >
181polygon_base < NUMBER > & polygon_base < NUMBER >::operator = (const polygon_base& polygon)
182{
183
184 if (&polygon != this)
185 {
186
187 point_array_base < NUMBER >::operator = (polygon);
188 m_bDirty = polygon.m_bDirty;
189 m_bDirtyBoundingRect = polygon.m_bDirtyBoundingRect;
190 m_rectangleBounding = polygon.m_rectangleBounding;
191
192 }
193
194 return *this;
195
196}
197
198
199template < prototype_number NUMBER >
200polygon_base < NUMBER > & polygon_base < NUMBER >::operator = (polygon_base&& polygon)
201{
202
203 if (&polygon != this)
204 {
205
206 point_array_base < NUMBER >::operator = (::transfer(polygon));
207 m_bDirty = polygon.m_bDirty;
208 m_bDirtyBoundingRect = polygon.m_bDirtyBoundingRect;
209 if(!m_bDirtyBoundingRect)
210 {
211 m_rectangleBounding = polygon.m_rectangleBounding;
212 }
213
214 }
215
216 return *this;
217
218}
219
220
221inline bool i32_lineersection(::f64_point & point, const ::f64_point & pt1, const ::f64_point & pt2, const ::f64_point & pt3, const ::f64_point & pt4);
222
223
224//https://rbrundritt.wordpress.com/2008/10/20/approximate-points-of-intersection-of-two-line-segments/
225//latlong1 and latlong2 represent two coordinates that make up the bounded box
226//latlong3 is a i32_point that we are checking to see is inside the box
227inline bool inBoundedBox(const ::f64_point & pt1, const ::f64_point & pt2, const ::f64_point & pt3)
228{
229
230 ::f64 dSpan = 0.01;
231
232 if (pt1.x < pt2.x)
233 {
234
235 if (!(pt1.x - dSpan <= pt3.x && pt3.x <= pt2.x + dSpan))
236 {
237
238 return false;
239
240 }
241
242 }
243 else
244 {
245
246 if (!(pt2.x - dSpan <= pt3.x && pt3.x <= pt1.x + dSpan))
247 {
248
249 return false;
250
251 }
252
253 }
254
255 if (pt1.y < pt2.y)
256 {
257
258 if (!(pt1.y - dSpan <= pt3.y && pt3.y <= pt2.y + dSpan))
259 {
260
261 return false;
262
263 }
264
265 }
266 else
267 {
268
269 if (!(pt2.y - dSpan <= pt3.y && pt3.y <= pt1.y + dSpan))
270 {
271
272 return false;
273
274 }
275
276 }
277
278 return true;
279
280}
281
282inline bool inBoundedBox1(const ::f64_point & pt1, const ::f64_point & pt2, const ::f64_point & pt3)
283{
284
285 if (pt1.x < pt2.x)
286 {
287
288 if (!(pt1.x <= pt3.x && pt3.x <= pt2.x))
289 {
290
291 return false;
292
293 }
294
295 }
296 else
297 {
298
299 if (!(pt2.x <= pt3.x && pt3.x <= pt1.x))
300 {
301
302 return false;
303
304 }
305
306 }
307
308 if (pt1.y < pt2.y)
309 {
310
311 if (!(pt1.y <= pt3.y && pt3.y <= pt2.y))
312 {
313
314 return false;
315
316 }
317
318 }
319 else
320 {
321
322 if (!(pt2.y <= pt3.y && pt3.y <= pt1.y))
323 {
324
325 return false;
326
327 }
328
329 }
330
331 return true;
332
333}
334
335
336//https://rbrundritt.wordpress.com/2008/10/20/approximate-points-of-intersection-of-two-line-segments/
337inline bool i32_lineersection(::f64_point & point, const ::f64_point & pt1, const ::f64_point & pt2, const ::f64_point & pt3, const ::f64_point & pt4)
338{
339
340 //Line segment 1 (point1, point2)
341 ::f64 A1 = pt2.x - pt1.x;
342 ::f64 B1 = pt1.y - pt2.y;
343 ::f64 C1 = A1 * pt1.y + B1 * pt1.x;
344
345 //Line segment 2 (p3, p4)
346 ::f64 A2 = pt4.x - pt3.x;
347 ::f64 B2 = pt3.y - pt4.y;
348 ::f64 C2 = A2 * pt3.y + B2 * pt3.x;
349
350 ::f64 determinant = A1 * B2 - A2 * B1;
351
352 if (determinant != 0.0)
353 {
354
355 point.y = (B2 * C1 - B1 * C2) / determinant;
356
357 point.x = (A1 * C2 - A2 * C1) / determinant;
358
359 return inBoundedBox(pt1, pt2, point) && inBoundedBox(pt3, pt4, point);
360
361 }
362
363 // lines are parallel;
364 return false;
365
366}
367
368
369inline void get_intersection_points(f64_point_array_base & pa, const ::f64_point & point1, const ::f64_point & point2, const f64_point_array_base & paPolygon)
370{
371
372 ::f64_point point;
373
374 for (iptr i = 0; i < paPolygon.get_count(); i++)
375 {
376
377 if (i32_lineersection(point, point1, point2, i % paPolygon, (i + 1) % paPolygon))
378 {
379
380 pa.tolerance_add_unique(0.001, point);
381
382 }
383
384 }
385
386}
387
388
389template < prototype_number NUMBER >
390polygon_base < NUMBER >::polygon_base()
391{
392
393 m_bDirty = false;
394
395 m_bDirtyBoundingRect = false;
396
397}
398
399
400template < prototype_number NUMBER >
401polygon_base < NUMBER >::~polygon_base()
402{
403
404}
405
406
407//template < prototype_number NUMBER >
408//void polygon_base < NUMBER >::set_rect(const ::rectangle_type < NUMBER > & rectangle)
409//{
410//
411// m_rectangleBounding = rectangle;
412//
413// this->set_size(4);
414//
415// this->element_at(0) = m_rectangleBounding.top_left();
416// this->element_at(1) = m_rectangleBounding.top_right();
417// this->element_at(2) = m_rectangleBounding.bottom_right();
418// this->element_at(3) = m_rectangleBounding.bottom_left();
419//
420// m_bDirty = false;
421// m_bDirtyBoundingRect = false;
422//
423//}
424
425
426template < prototype_number NUMBER >
427const ::rectangle_type < NUMBER > & polygon_base < NUMBER >::bounding_rect() const
428{
429
430 ((polygon_base *)this)->check_dirty();
431
432 if (m_bDirtyBoundingRect && this->has_elements())
433 {
434
435 ((polygon_base *)this)->m_bDirtyBoundingRect = false;
436
437 ((polygon_base *)this)->m_rectangleBounding.maximum_minimum();
438
439 ((polygon_base *)this)->expand_bounding_box(((polygon_base *)this)->m_rectangleBounding.top_left(), ((polygon_base *)this)->m_rectangleBounding.bottom_right());
440
441// ((polygon_base *)this)->m_rectangleBounding.left = this->element_at(0).x;
442// ((polygon_base *)this)->m_rectangleBounding.top = this->element_at(0).y;
443// ((polygon_base *)this)->m_rectangleBounding.right = this->element_at(0).x;
444// ((polygon_base *)this)->m_rectangleBounding.bottom = this->element_at(0).y;
445//
446// for (::collection::index i = 1; i < this->get_count(); i++)
447// {
448//
449// ((polygon_base *)this)->m_rectangleBounding.left = minimum(m_rectangleBounding.left, this->element_at(i).x);
450// ((polygon_base *)this)->m_rectangleBounding.right = maximum(m_rectangleBounding.right, this->element_at(i).x);
451// ((polygon_base *)this)->m_rectangleBounding.top = minimum(m_rectangleBounding.top, this->element_at(i).y);
452// ((polygon_base *)this)->m_rectangleBounding.bottom = maximum(m_rectangleBounding.bottom, this->element_at(i).y);
453
454// }
455
456 }
457
458 return m_rectangleBounding;
459
460}
461
462
463template < prototype_number NUMBER >
464bool polygon_base < NUMBER >::overlaps(const polygon_base & polygon) const
465{
466
467 if (this->get_count() >= 3 && polygon.get_count() >= 3)
468 {
469
470 auto & r1 = bounding_rect();
471
472 auto & r2 = polygon.bounding_rect();
473
474 if (!r1.intersects(r2))
475 {
476
477 return false;
478
479 }
480
481 ::collection::count c1 = this->get_count();
482
483 ::collection::count c2 = polygon.get_count();
484
485 for (::i32 i = 0; i < c1; i++)
486 {
487
488 if (polygon.contains(this->element_at(i)))
489 {
490
491 return true;
492
493 }
494
495 }
496
497 for (::i32 i = 0; i < c2; i++)
498 {
499
500 if (this->contains(polygon[i]))
501 {
502
503 return true;
504
505 }
506
507 }
508
509 ::f64_point point;
510
511 for (::i32 i = 0; i < c1; i++)
512 {
513
514 for (::i32 k = 0; k < c2; k++)
515 {
516
517 if (i32_lineersection(point, this->element_at(i), this->element_at((i + 1) % c1), polygon[k], polygon[(k + 1) % c2]))
518 {
519
520 return true;
521
522 }
523
524 }
525
526 }
527
528 }
529
530 return false;
531
532}
533
534
535template < prototype_number NUMBER >
536polygon_base < NUMBER > polygon_base < NUMBER >::convex_intersection(const polygon_base & polygon) const
537{
538
539 ::collection::count c1 = this->get_count();
540
541 ::collection::count c2 = polygon.get_count();
542
543 polygon_base polygonResult;
544
545 if (c1 >= 3 && c2 >= 3)
546 {
547
548 //Add the corners of poly1 which are inside poly2
549 for (::i32 i = 0; i < c1; i++)
550 {
551
552 if (polygon.contains(this->element_at(i)))
553 {
554
555 polygonResult.tolerance_add_unique(0.001, this->element_at(i));
556
557 }
558
559 }
560
561 for (::i32 i = 0; i < c2; i++)
562 {
563
564 if (this->contains(polygon[i]))
565 {
566
567 polygonResult.tolerance_add_unique(0.001, polygon[i]);
568
569 }
570
571 }
572
573 for (::i32 i = 0; i < this->get_count(); i++)
574 {
575
576 get_intersection_points(polygonResult, i % *this, (i + 1) % *this, polygon);
577
578 }
579
580 polygonResult.sort();
581
582 polygonResult.m_bDirty = polygonResult.has_elements();
583
584 }
585
586 return polygonResult;
587
588}
589
590
591template < prototype_number NUMBER >
592class poly_polygon_base :
593 public ::pointer_array < ::array_particle < ::polygon_base < NUMBER > > >
594{
595public:
596
597
598 using UNIT_TYPE = NUMBER;
599
600
601 using ::pointer_array < ::array_particle < ::polygon_base < NUMBER > > >::pointer_array;
602
603
604 void expand_bounding_box(::point_type < UNIT_TYPE > & top_left, ::point_type < UNIT_TYPE > & bottom_right)
605 {
606
607 for(auto & ppolygon : *this)
608 {
609
610 ppolygon->expand_bounding_box(top_left, bottom_right);
611
612 }
613
614 }
615
616
617};
618
619
620
point_array_base
Definition point_array.h:25
point_array_base::tolerance_add_unique
inline ::collection::index tolerance_add_unique(UNIT_TYPE tolerance, const ::point_type< NUMBER > &pointAdd)
Definition point_array.h:67
pointer_array
Definition pointer_array.h:1882
poly_polygon_base
Definition polygon.h:594
polygon_base
Definition polygon.h:13