KiCad PCB EDA Suite
Loading...
Searching...
No Matches
polygon_triangulation.h
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Modifications Copyright (C) 2018-2024 KiCad Developers
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, you may find one here:
18 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
19 * or you may search the http://www.gnu.org website for the version 2 license,
20 * or you may write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
22 *
23 * Based on Uniform Plane Subdivision algorithm from Lamot, Marko, and Borut ┼Żalik.
24 * "A fast polygon triangulation algorithm based on uniform plane subdivision."
25 * Computers & graphics 27, no. 2 (2003): 239-253.
26 *
27 * Code derived from:
28 * K-3D which is Copyright (c) 2005-2006, Romain Behar, GPL-2, license above
29 * earcut which is Copyright (c) 2016, Mapbox, ISC
30 *
31 * ISC License:
32 * Permission to use, copy, modify, and/or distribute this software for any purpose
33 * with or without fee is hereby granted, provided that the above copyright notice
34 * and this permission notice appear in all copies.
35 *
36 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
37 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
38 * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
39 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
40 * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
41 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
42 * THIS SOFTWARE.
43 *
44 */
45
46#ifndef __POLYGON_TRIANGULATION_H
47#define __POLYGON_TRIANGULATION_H
48
49#include <algorithm>
50#include <deque>
51#include <cmath>
52
53#include <advanced_config.h>
54#include <clipper.hpp>
57#include <math/box2.h>
58#include <math/vector2d.h>
59
60#include <wx/log.h>
61
62#define TRIANGULATE_TRACE "triangulate"
64{
65public:
67 m_vertices_original_size( 0 ), m_result( aResult )
68 {};
69
72 {
73 m_bbox = aPoly.BBox();
75
76 if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
77 return true;
78
82 VERTEX* firstVertex = createList( aPoly );
83
84 if( !firstVertex || firstVertex->prev == firstVertex->next )
85 return true;
86
87 wxLogTrace( TRIANGULATE_TRACE, "Created list with %f area", firstVertex->area() );
88
90 firstVertex->updateList();
91
96 if( aHintData && aHintData->Vertices().size() == m_vertices.size() )
97 {
98 m_result.SetTriangles( aHintData->Triangles() );
99 return true;
100 }
101 else
102 {
103 auto retval = earcutList( firstVertex );
104
105 if( !retval )
106 {
107 wxLogTrace( TRIANGULATE_TRACE, "Tesselation failed, logging remaining vertices" );
108 logRemaining();
109 }
110
111 m_vertices.clear();
112 return retval;
113 }
114 }
115
116private:
117 struct VERTEX
118 {
119 VERTEX( size_t aIndex, double aX, double aY, POLYGON_TRIANGULATION* aParent ) :
120 i( aIndex ),
121 x( aX ),
122 y( aY ),
123 parent( aParent )
124 {
125 }
126
127 VERTEX& operator=( const VERTEX& ) = delete;
128 VERTEX& operator=( VERTEX&& ) = delete;
129
130 bool operator==( const VERTEX& rhs ) const
131 {
132 return this->x == rhs.x && this->y == rhs.y;
133 }
134 bool operator!=( const VERTEX& rhs ) const { return !( *this == rhs ); }
135
136
148 {
149 parent->m_vertices.emplace_back( i, x, y, parent );
150 VERTEX* a2 = &parent->m_vertices.back();
151 parent->m_vertices.emplace_back( b->i, b->x, b->y, parent );
152 VERTEX* b2 = &parent->m_vertices.back();
153 VERTEX* an = next;
154 VERTEX* bp = b->prev;
155
156 next = b;
157 b->prev = this;
158
159 a2->next = an;
160 an->prev = a2;
161
162 b2->next = a2;
163 a2->prev = b2;
164
165 bp->next = b2;
166 b2->prev = bp;
167
168 return b2;
169 }
170
174 void remove()
175 {
176 next->prev = prev;
177 prev->next = next;
178
179 if( prevZ )
180 prevZ->nextZ = nextZ;
181
182 if( nextZ )
183 nextZ->prevZ = prevZ;
184
185 next = nullptr;
186 prev = nullptr;
187 nextZ = nullptr;
188 prevZ = nullptr;
189 }
190
192 {
193 if( !z )
194 z = parent->zOrder( x, y );
195 }
196
202 {
203 VERTEX* p = next;
204
205 while( p != this )
206 {
210 if( *p == *p->next )
211 {
212 p = p->prev;
213 p->next->remove();
214
215 if( p == p->next )
216 break;
217 }
218
219 p->updateOrder();
220 p = p->next;
221 };
222
223 updateOrder();
224 zSort();
225 }
226
230 void zSort()
231 {
232 std::deque<VERTEX*> queue;
233
234 queue.push_back( this );
235
236 for( auto p = next; p && p != this; p = p->next )
237 queue.push_back( p );
238
239 std::sort( queue.begin(), queue.end(), []( const VERTEX* a, const VERTEX* b )
240 {
241 if( a->z != b->z )
242 return a->z < b->z;
243
244 if( a->x != b->x )
245 return a->x < b->x;
246
247 if( a->y != b->y )
248 return a->y < b->y;
249
250 return a->i < b->i;
251 } );
252
253 VERTEX* prev_elem = nullptr;
254
255 for( auto elem : queue )
256 {
257 if( prev_elem )
258 prev_elem->nextZ = elem;
259
260 elem->prevZ = prev_elem;
261 prev_elem = elem;
262 }
263
264 prev_elem->nextZ = nullptr;
265 }
266
267
271 bool inTriangle( const VERTEX& a, const VERTEX& b, const VERTEX& c )
272 {
273 return ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
274 && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
275 && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
276 }
277
282 double area( const VERTEX* aEnd = nullptr ) const
283 {
284 const VERTEX* p = this;
285 double a = 0.0;
286
287 do
288 {
289 a += ( p->x + p->next->x ) * ( p->next->y - p->y );
290 p = p->next;
291 } while( p != this && p != aEnd );
292
293 if( p != this )
294 a += ( p->x + aEnd->x ) * ( aEnd->y - p->y );
295
296 return a / 2;
297 }
298
299 const size_t i;
300 double x;
301 double y;
303
304 // previous and next vertices nodes in a polygon ring
305 VERTEX* prev = nullptr;
306 VERTEX* next = nullptr;
307
308 // z-order curve value
309 int32_t z = 0;
310
311 // previous and next nodes in z-order
312 VERTEX* prevZ = nullptr;
313 VERTEX* nextZ = nullptr;
314 };
315
321 int32_t zOrder( const double aX, const double aY ) const
322 {
323 int32_t x = static_cast<int32_t>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
324 int32_t y = static_cast<int32_t>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
325
326 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
327 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
328 x = ( x | ( x << 2 ) ) & 0x33333333;
329 x = ( x | ( x << 1 ) ) & 0x55555555;
330
331 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
332 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
333 y = ( y | ( y << 2 ) ) & 0x33333333;
334 y = ( y | ( y << 1 ) ) & 0x55555555;
335
336 return x | ( y << 1 );
337 }
338
339
344 {
345 std::set<VERTEX*> seen;
346 wxLog::EnableLogging();
347 for( VERTEX& p : m_vertices )
348 {
349 if( !p.next || p.next == &p || seen.find( &p ) != seen.end() )
350 continue;
351
352 logVertices( &p, &seen );
353 }
354 }
355
356 void logVertices( VERTEX* aStart, std::set<VERTEX*>* aSeen )
357 {
358 if( aSeen && aSeen->count( aStart ) )
359 return;
360
361 if( aSeen )
362 aSeen->insert( aStart );
363
364 int count = 1;
365 VERTEX* p = aStart->next;
366 wxString msg = wxString::Format( "Vertices: %d,%d,", static_cast<int>( aStart->x ),
367 static_cast<int>( aStart->y ) );
368
369 do
370 {
371 msg += wxString::Format( "%d,%d,", static_cast<int>( p->x ), static_cast<int>( p->y ) );
372
373 if( aSeen )
374 aSeen->insert( p );
375
376 p = p->next;
377 count++;
378 } while( p != aStart );
379
380 if( count < 3 ) // Don't log anything that only has 2 or fewer points
381 return;
382
383 msg.RemoveLast();
384 wxLogTrace( TRIANGULATE_TRACE, msg );
385 }
386
392 {
393 if( !aStart || aStart->next == aStart->prev )
394 return aStart;
395
396 VERTEX* p = aStart;
397 VERTEX* next = p->next;
398 VERTEX* retval = aStart;
399 int count = 0;
400
402 sq_dist *= sq_dist;
403
404 do
405 {
406 VECTOR2D diff = VECTOR2D( next->x - p->x, next->y - p->y );
407
408 if( diff.SquaredEuclideanNorm() < sq_dist )
409 {
410 if( next == aStart )
411 {
412 retval = p;
413 aStart->remove();
414 count++;
415 break;
416 }
417
418 next = next->next;
419 p->next->remove();
420 count++;
421 retval = p;
422 }
423 else
424 {
425 p = next;
426 next = next->next;
427 }
428 } while( p != aStart && next && p );
429
430 wxLogTrace( TRIANGULATE_TRACE, "Removed %d points in simplifyList", count );
431
432 if( count )
433 return retval;
434
435 return nullptr;
436 }
437
438
447 {
448 VERTEX* retval = nullptr;
449 size_t count = 0;
450
451 if( ( retval = simplifyList( aStart ) ) )
452 aStart = retval;
453
454 wxASSERT( aStart->next && aStart->prev );
455
456 VERTEX* p = aStart->next;
457
458 while( p != aStart && p->next && p->prev )
459 {
460 // We make a dummy triangle that is actually part of the existing line segment
461 // and measure its area. This will not be exactly zero due to floating point
462 // errors. We then look for areas that are less than 4 times the area of the
463 // dummy triangle. For small triangles, this is a small number
464 VERTEX tmp( 0, 0.5 * ( p->prev->x + p->next->x ), 0.5 * ( p->prev->y + p->next->y ), this );
465 double null_area = 4.0 * std::abs( area( p->prev, &tmp, p->next ) );
466
467 if( *p == *( p->next ) || std::abs( area( p->prev, p, p->next ) ) <= null_area )
468 {
469 // This is a spike, remove it, leaving only one point
470 if( *( p->next ) == *( p->prev ) )
471 p->next->remove();
472
473 p = p->prev;
474 p->next->remove();
475 retval = p;
476 ++count;
477
478 if( p == p->next )
479 break;
480
481 // aStart was removed above, so we need to reset it
482 if( !aStart->next )
483 aStart = p->prev;
484
485 continue;
486 }
487
488 p = p->next;
489 };
490
492 if( !p->next || p->next == p || p->next == p->prev )
493 return p;
494
495 // We needed an end point above that wouldn't be removed, so
496 // here we do the final check for this as a Steiner point
497 VERTEX tmp( 0, 0.5 * ( p->prev->x + p->next->x ),
498 0.5 * ( p->prev->y + p->next->y ), this );
499 double null_area = 4.0 * std::abs( area( p->prev, &tmp, p->next ) );
500
501 if( std::abs( area( p->prev, p, p->next ) ) <= null_area )
502 {
503 retval = p->next;
504 p->remove();
505 ++count;
506 }
507
508 wxLogTrace( TRIANGULATE_TRACE, "Removed %zu NULL triangles", count );
509
510 return retval;
511 }
512
517 {
518 wxLogTrace( TRIANGULATE_TRACE, "Creating list from %d points", points.PointCount() );
519
520 VERTEX* tail = nullptr;
521 double sum = 0.0;
522
523 // Check for winding order
524 for( int i = 0; i < points.PointCount(); i++ )
525 {
526 VECTOR2D p1 = points.CPoint( i );
527 VECTOR2D p2 = points.CPoint( i + 1 );
528
529 sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
530 }
531
532 VECTOR2I last_pt{ std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
534 sq_dist *= sq_dist;
535
536 auto addVertex = [&]( int i )
537 {
538 const VECTOR2I& pt = points.CPoint( i );
539 VECTOR2I diff = pt - last_pt;
540 if( diff.SquaredEuclideanNorm() > sq_dist )
541 {
542 tail = insertVertex( pt, tail );
543 last_pt = pt;
544 }
545 };
546
547 if( sum > 0.0 )
548 {
549 for( int i = points.PointCount() - 1; i >= 0; i-- )
550 addVertex( i );
551 }
552 else
553 {
554 for( int i = 0; i < points.PointCount(); i++ )
555 addVertex( i );
556 }
557
558 if( tail && ( *tail == *tail->next ) )
559 tail->next->remove();
560
561 return tail;
562 }
563
577 bool earcutList( VERTEX* aPoint, int pass = 0 )
578 {
579 wxLogTrace( TRIANGULATE_TRACE, "earcutList starting at %p for pass %d", aPoint, pass );
580
581 if( !aPoint )
582 return true;
583
584 VERTEX* stop = aPoint;
585 VERTEX* prev;
586 VERTEX* next;
587 int internal_pass = 1;
588
589 while( aPoint->prev != aPoint->next )
590 {
591 prev = aPoint->prev;
592 next = aPoint->next;
593
594 if( isEar( aPoint ) )
595 {
596 // Tiny ears cannot be seen on the screen
597 if( !isTooSmall( aPoint ) )
598 {
599 m_result.AddTriangle( prev->i, aPoint->i, next->i );
600 }
601 else
602 {
603 wxLogTrace( TRIANGULATE_TRACE, "Ignoring tiny ear with area %f",
604 area( prev, aPoint, next ) );
605 }
606
607 aPoint->remove();
608
609 // Skip one vertex as the triangle will account for the prev node
610 aPoint = next->next;
611 stop = next->next;
612
613 continue;
614 }
615
616 VERTEX* nextNext = next->next;
617
618 if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
619 locallyInside( prev, nextNext ) &&
620 locallyInside( nextNext, prev ) )
621 {
622 wxLogTrace( TRIANGULATE_TRACE,
623 "Local intersection detected. Merging minor triangle with area %f",
624 area( prev, aPoint, nextNext ) );
625 m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
626
627 // remove two nodes involved
628 next->remove();
629 aPoint->remove();
630
631 aPoint = nextNext;
632 stop = nextNext;
633
634 continue;
635 }
636
637 aPoint = next;
638
639 /*
640 * We've searched the entire polygon for available ears and there are still
641 * un-sliced nodes remaining.
642 */
643 if( aPoint == stop && aPoint->prev != aPoint->next )
644 {
645 VERTEX* newPoint;
646
647 // Removing null triangles will remove steiner points as well as colinear points
648 // that are three in a row. Because our next step is to subdivide the polygon,
649 // we need to allow it to add the subdivided points first. This is why we only
650 // run the RemoveNullTriangles function after the first pass.
651 if( ( internal_pass == 2 ) && ( newPoint = removeNullTriangles( aPoint ) ) )
652 {
653 // There are no remaining triangles in the list
654 if( newPoint->next == newPoint->prev )
655 break;
656
657 aPoint = newPoint;
658 stop = newPoint;
659 continue;
660 }
661
662 ++internal_pass;
663
664 // This will subdivide the polygon 2 times. The first pass will add enough points
665 // such that each edge is less than the average edge length. If this doesn't work
666 // The next pass will remove the null triangles (above) and subdivide the polygon
667 // again, this time adding one point to each long edge (and thereby changing the locations)
668 if( internal_pass < 4 )
669 {
670 wxLogTrace( TRIANGULATE_TRACE, "Subdividing polygon" );
671 subdividePolygon( aPoint, internal_pass );
672 continue;
673 }
674
675 // If we don't have any NULL triangles left, cut the polygon in two and try again
676 wxLogTrace( TRIANGULATE_TRACE, "Splitting polygon" );
677
678 if( !splitPolygon( aPoint ) )
679 return false;
680
681 break;
682 }
683 }
684
685 // Check to see if we are left with only three points in the polygon
686 if( aPoint->next && aPoint->prev == aPoint->next->next )
687 {
688 // Three concave points will never be able to be triangulated because they were
689 // created by an intersecting polygon, so just drop them.
690 if( area( aPoint->prev, aPoint, aPoint->next ) >= 0 )
691 return true;
692 }
693
694 /*
695 * At this point, our polygon should be fully tessellated.
696 */
697 if( aPoint->prev != aPoint->next )
699
700 return true;
701 }
702
703
708 bool isTooSmall( const VERTEX* aPoint ) const
709 {
711 double prev_sq_len = ( aPoint->prev->x - aPoint->x ) * ( aPoint->prev->x - aPoint->x ) +
712 ( aPoint->prev->y - aPoint->y ) * ( aPoint->prev->y - aPoint->y );
713 double next_sq_len = ( aPoint->next->x - aPoint->x ) * ( aPoint->next->x - aPoint->x ) +
714 ( aPoint->next->y - aPoint->y ) * ( aPoint->next->y - aPoint->y );
715 double opp_sq_len = ( aPoint->next->x - aPoint->prev->x ) * ( aPoint->next->x - aPoint->prev->x ) +
716 ( aPoint->next->y - aPoint->prev->y ) * ( aPoint->next->y - aPoint->prev->y );
717
718 return ( prev_sq_len < min_area || next_sq_len < min_area || opp_sq_len < min_area );
719 }
720
721
731 bool isEar( VERTEX* aEar ) const
732 {
733 const VERTEX* a = aEar->prev;
734 const VERTEX* b = aEar;
735 const VERTEX* c = aEar->next;
736
737 // If the area >=0, then the three points for a concave sequence
738 // with b as the reflex point
739 if( area( a, b, c ) >= 0 )
740 return false;
741
742 // triangle bbox
743 const double minTX = std::min( a->x, std::min( b->x, c->x ) );
744 const double minTY = std::min( a->y, std::min( b->y, c->y ) );
745 const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
746 const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
747
748 // z-order range for the current triangle bounding box
749 const int32_t minZ = zOrder( minTX, minTY );
750 const int32_t maxZ = zOrder( maxTX, maxTY );
751
752 // first look for points inside the triangle in increasing z-order
753 VERTEX* p = aEar->nextZ;
754
755 while( p && p->z <= maxZ )
756 {
757 if( p != a && p != c
758 && p->inTriangle( *a, *b, *c )
759 && area( p->prev, p, p->next ) >= 0 )
760 return false;
761
762 p = p->nextZ;
763 }
764
765 // then look for points in decreasing z-order
766 p = aEar->prevZ;
767
768 while( p && p->z >= minZ )
769 {
770 if( p != a && p != c
771 && p->inTriangle( *a, *b, *c )
772 && area( p->prev, p, p->next ) >= 0 )
773 return false;
774
775 p = p->prevZ;
776 }
777
778 return true;
779 }
780
784 void subdividePolygon( VERTEX* aStart, int pass = 0 )
785 {
786 VERTEX* p = aStart;
787
788 struct VertexComparator {
789 bool operator()(const std::pair<VERTEX*,double>& a, const std::pair<VERTEX*,double>& b) const {
790 return a.second > b.second;
791 }
792 };
793
794 std::set<std::pair<VERTEX*,double>, VertexComparator> longest;
795 double avg = 0.0;
796
797 do
798 {
799 double len = ( p->x - p->next->x ) * ( p->x - p->next->x ) +
800 ( p->y - p->next->y ) * ( p->y - p->next->y );
801 longest.emplace( p, len );
802
803 avg += len;
804 p = p->next;
805 } while (p != aStart);
806
807 avg /= longest.size();
808 wxLogTrace( TRIANGULATE_TRACE, "Average length: %f", avg );
809
810 for( auto it = longest.begin(); it != longest.end() && it->second > avg; ++it )
811 {
812 wxLogTrace( TRIANGULATE_TRACE, "Subdividing edge with length %f", it->second );
813 VERTEX* a = it->first;
814 VERTEX* b = a->next;
815 VERTEX* last = a;
816
817 // We adjust the number of divisions based on the pass in order to progressively
818 // subdivide the polygon when triangulation fails
819 int divisions = avg / it->second + 2 + pass;
820 double step = 1.0 / divisions;
821
822 for( int i = 1; i < divisions; i++ )
823 {
824 double x = a->x * ( 1.0 - step * i ) + b->x * ( step * i );
825 double y = a->y * ( 1.0 - step * i ) + b->y * ( step * i );
826 last = insertVertex( VECTOR2I( x, y ), last );
827 }
828 }
829
830 // update z-order of the vertices
831 aStart->updateList();
832 }
833
840 bool splitPolygon( VERTEX* start )
841 {
842 VERTEX* origPoly = start;
843
844 // If we have fewer than 4 points, we cannot split the polygon
845 if( !start || !start->next || start->next == start->prev
846 || start->next->next == start->prev )
847 {
848 return true;
849 }
850
851 // Our first attempts to split the polygon will be at overlapping points.
852 // These are natural split points and we only need to switch the loop directions
853 // to generate two new loops. Since they are overlapping, we are do not
854 // need to create a new segment to disconnect the two loops.
855 do
856 {
857 std::vector<VERTEX*> overlapPoints;
858 VERTEX* z_pt = origPoly;
859
860 while ( z_pt->prevZ && *z_pt->prevZ == *origPoly )
861 z_pt = z_pt->prevZ;
862
863 overlapPoints.push_back( z_pt );
864
865 while( z_pt->nextZ && *z_pt->nextZ == *origPoly )
866 {
867 z_pt = z_pt->nextZ;
868 overlapPoints.push_back( z_pt );
869 }
870
871 if( overlapPoints.size() != 2 || overlapPoints[0]->next == overlapPoints[1]
872 || overlapPoints[0]->prev == overlapPoints[1] )
873 {
874 origPoly = origPoly->next;
875 continue;
876 }
877
878 if( overlapPoints[0]->area( overlapPoints[1] ) < 0 || overlapPoints[1]->area( overlapPoints[0] ) < 0 )
879 {
880 wxLogTrace( TRIANGULATE_TRACE, "Split generated a hole, skipping" );
881 origPoly = origPoly->next;
882 continue;
883 }
884
885 wxLogTrace( TRIANGULATE_TRACE, "Splitting at overlap point %f, %f", overlapPoints[0]->x, overlapPoints[0]->y );
886 std::swap( overlapPoints[0]->next, overlapPoints[1]->next );
887 overlapPoints[0]->next->prev = overlapPoints[0];
888 overlapPoints[1]->next->prev = overlapPoints[1];
889
890 overlapPoints[0]->updateList();
891 overlapPoints[1]->updateList();
892 logVertices( overlapPoints[0], nullptr );
893 logVertices( overlapPoints[1], nullptr );
894 bool retval = earcutList( overlapPoints[0] ) && earcutList( overlapPoints[1] );
895
896 wxLogTrace( TRIANGULATE_TRACE, "%s at first overlap split", retval ? "Success" : "Failed" );
897 return retval;
898
899
900 } while ( origPoly != start );
901
902 // If we've made it through the split algorithm and we still haven't found a
903 // set of overlapping points, we need to create a new segment to split the polygon
904 // into two separate polygons. We do this by finding the two vertices that form
905 // a valid line (does not cross the existing polygon)
906 do
907 {
908 VERTEX* marker = origPoly->next->next;
909
910 while( marker != origPoly->prev )
911 {
912 // Find a diagonal line that is wholly enclosed by the polygon interior
913 if( origPoly->next && origPoly->i != marker->i && goodSplit( origPoly, marker ) )
914 {
915 VERTEX* newPoly = origPoly->split( marker );
916
917 origPoly->updateList();
918 newPoly->updateList();
919
920 bool retval = earcutList( origPoly ) && earcutList( newPoly );
921
922 wxLogTrace( TRIANGULATE_TRACE, "%s at split", retval ? "Success" : "Failed" );
923 return retval;
924 }
925
926 marker = marker->next;
927 }
928
929 origPoly = origPoly->next;
930 } while( origPoly != start );
931
932 wxLogTrace( TRIANGULATE_TRACE, "Could not find a valid split point" );
933 return false;
934 }
935
945 bool goodSplit( const VERTEX* a, const VERTEX* b ) const
946 {
947 bool a_on_edge = ( a->nextZ && *a == *a->nextZ ) || ( a->prevZ && *a == *a->prevZ );
948 bool b_on_edge = ( b->nextZ && *b == *b->nextZ ) || ( b->prevZ && *b == *b->prevZ );
949 bool no_intersect = a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon( a, b );
950 bool local_split = locallyInside( a, b ) && locallyInside( b, a ) && middleInside( a, b );
951 bool same_dir = area( a->prev, a, b->prev ) != 0.0 || area( a, b->prev, b ) != 0.0;
952 bool has_len = ( *a == *b ) && area( a->prev, a, a->next ) > 0 && area( b->prev, b, b->next ) > 0;
953 bool pos_area = a->area( b ) > 0 && b->area( a ) > 0;
954
955 return no_intersect && local_split && ( same_dir || has_len ) && !a_on_edge && !b_on_edge && pos_area;
956
957 }
958
962 double area( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const
963 {
964 return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
965 }
966
967
968 constexpr int sign( double aVal ) const
969 {
970 return ( aVal > 0 ) - ( aVal < 0 );
971 }
972
976 constexpr bool overlapping( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const
977 {
978 return q->x <= std::max( p->x, r->x ) &&
979 q->x >= std::min( p->x, r->x ) &&
980 q->y <= std::max( p->y, r->y ) &&
981 q->y >= std::min( p->y, r->y );
982 }
983
989 bool intersects( const VERTEX* p1, const VERTEX* q1, const VERTEX* p2, const VERTEX* q2 ) const
990 {
991 int sign1 = sign( area( p1, q1, p2 ) );
992 int sign2 = sign( area( p1, q1, q2 ) );
993 int sign3 = sign( area( p2, q2, p1 ) );
994 int sign4 = sign( area( p2, q2, q1 ) );
995
996 if( sign1 != sign2 && sign3 != sign4 )
997 return true;
998
999 if( sign1 == 0 && overlapping( p1, p2, q1 ) )
1000 return true;
1001
1002 if( sign2 == 0 && overlapping( p1, q2, q1 ) )
1003 return true;
1004
1005 if( sign3 == 0 && overlapping( p2, p1, q2 ) )
1006 return true;
1007
1008 if( sign4 == 0 && overlapping( p2, q1, q2 ) )
1009 return true;
1010
1011
1012 return false;
1013 }
1014
1021 bool intersectsPolygon( const VERTEX* a, const VERTEX* b ) const
1022 {
1023 for( size_t ii = 0; ii < m_vertices_original_size; ii++ )
1024 {
1025 const VERTEX* p = &m_vertices[ii];
1026 const VERTEX* q = &m_vertices[( ii + 1 ) % m_vertices_original_size];
1027
1028 if( p->i == a->i || p->i == b->i || q->i == a->i || q->i == b->i )
1029 continue;
1030
1031 if( intersects( p, q, a, b ) )
1032 return true;
1033 }
1034
1035 return false;
1036 }
1037
1047 bool locallyInside( const VERTEX* a, const VERTEX* b ) const
1048 {
1049 if( area( a->prev, a, a->next ) < 0 )
1050 return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
1051 else
1052 return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
1053 }
1054
1058 bool middleInside( const VERTEX* a, const VERTEX* b ) const
1059 {
1060 const VERTEX* p = a;
1061 bool inside = false;
1062 double px = ( a->x + b->x ) / 2;
1063 double py = ( a->y + b->y ) / 2;
1064
1065 do
1066 {
1067 if( ( ( p->y > py ) != ( p->next->y > py ) )
1068 && ( px < ( p->next->x - p->x ) * ( py - p->y ) / ( p->next->y - p->y ) + p->x ) )
1069 inside = !inside;
1070
1071 p = p->next;
1072 } while( p != a );
1073
1074 return inside;
1075 }
1076
1083 VERTEX* insertVertex( const VECTOR2I& pt, VERTEX* last )
1084 {
1085 m_result.AddVertex( pt );
1086 m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
1087
1088 VERTEX* p = &m_vertices.back();
1089
1090 if( !last )
1091 {
1092 p->prev = p;
1093 p->next = p;
1094 }
1095 else
1096 {
1097 p->next = last->next;
1098 p->prev = last;
1099 last->next->prev = p;
1100 last->next = p;
1101 }
1102 return p;
1103 }
1104
1105private:
1107 std::deque<VERTEX> m_vertices;
1110};
1111
1112#endif //__POLYGON_TRIANGULATION_H
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
coord_type GetHeight() const
Definition: box2.h:189
coord_type GetY() const
Definition: box2.h:182
coord_type GetWidth() const
Definition: box2.h:188
coord_type GetX() const
Definition: box2.h:181
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
bool middleInside(const VERTEX *a, const VERTEX *b) const
Check to see if the segment halfway point between a and b is inside the polygon.
bool intersects(const VERTEX *p1, const VERTEX *q1, const VERTEX *p2, const VERTEX *q2) const
Check for intersection between two segments, end points included.
bool splitPolygon(VERTEX *start)
If we cannot find an ear to slice in the current polygon list, we use this to split the polygon into ...
bool isEar(VERTEX *aEar) const
Check whether the given vertex is in the middle of an ear.
constexpr int sign(double aVal) const
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks....
std::deque< VERTEX > m_vertices
void logVertices(VERTEX *aStart, std::set< VERTEX * > *aSeen)
bool goodSplit(const VERTEX *a, const VERTEX *b) const
Check if a segment joining two vertices lies fully inside the polygon.
VERTEX * simplifyList(VERTEX *aStart)
Simplify the line chain by removing points that are too close to each other.
POLYGON_TRIANGULATION(SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
double area(const VERTEX *p, const VERTEX *q, const VERTEX *r) const
Return the twice the signed area of the triangle formed by vertices p, q, and r.
constexpr bool overlapping(const VERTEX *p, const VERTEX *q, const VERTEX *r) const
If p, q, and r are collinear and r lies between p and q, then return true.
bool locallyInside(const VERTEX *a, const VERTEX *b) const
Check whether the segment from vertex a -> vertex b is inside the polygon around the immediate area o...
VERTEX * insertVertex(const VECTOR2I &pt, VERTEX *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...
void logRemaining()
Outputs a list of vertices that have not yet been triangulated.
VERTEX * removeNullTriangles(VERTEX *aStart)
Iterate through the list to remove NULL triangles if they exist.
bool intersectsPolygon(const VERTEX *a, const VERTEX *b) const
Check whether the segment from vertex a -> vertex b crosses any of the segments of the polygon of whi...
bool isTooSmall(const VERTEX *aPoint) const
Check whether a given vertex is too small to matter.
bool earcutList(VERTEX *aPoint, int pass=0)
Walk through a circular linked list starting at aPoint.
void subdividePolygon(VERTEX *aStart, int pass=0)
Inserts a new vertex halfway between each existing pair of vertices.
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON *aHintData)
VERTEX * createList(const SHAPE_LINE_CHAIN &points)
Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
int PointCount() const
Return the number of points (vertices) in this line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
void AddVertex(const VECTOR2I &aP)
const std::deque< VECTOR2I > & Vertices() const
const std::deque< TRI > & Triangles() const
void AddTriangle(int a, int b, int c)
void SetTriangles(const std::deque< TRI > &aTriangles)
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:272
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:72
int m_TriangulateSimplificationLevel
The number of internal units that will be allowed to deflect from the base segment when creating a ne...
int m_TriangulateMinimumArea
The minimum area of a polygon that can be left over after triangulation and still consider the triang...
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:424
#define TRIANGULATE_TRACE
CITER next(CITER it)
Definition: ptree.cpp:126
void updateList()
After inserting or changing nodes, this function should be called to remove duplicate vertices and en...
double area(const VERTEX *aEnd=nullptr) const
Returns the signed area of the polygon connected to the current vertex, optionally ending at a specif...
VERTEX * split(VERTEX *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...
VERTEX(size_t aIndex, double aX, double aY, POLYGON_TRIANGULATION *aParent)
bool operator!=(const VERTEX &rhs) const
VERTEX & operator=(const VERTEX &)=delete
VERTEX & operator=(VERTEX &&)=delete
void zSort()
Sort all vertices in this vertex's list by their Morton code.
bool inTriangle(const VERTEX &a, const VERTEX &b, const VERTEX &c)
Check to see if triangle surrounds our current vertex.
void remove()
Remove the node from the linked list and z-ordered linked list.
bool operator==(const VERTEX &rhs) const
VECTOR2< double > VECTOR2D
Definition: vector2d.h:587
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588