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 * Copyright (C) 2018 KiCad Developers, see AUTHORS.TXT for contributors.
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 3
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/gpl-3.0.html
19 * or you may search the http://www.gnu.org website for the version 3 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 <geometry/vertex_set.h>
58#include <math/box2.h>
59#include <math/vector2d.h>
60
61#include <wx/log.h>
62
63#define TRIANGULATE_TRACE "triangulate"
65{
66public:
68 VERTEX_SET( ADVANCED_CFG::GetCfg().m_TriangulateSimplificationLevel ),
69 m_vertices_original_size( 0 ), m_result( aResult )
70 {};
71
74 {
75 m_bbox = aPoly.BBox();
77
78 if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
79 return true;
80
84 VERTEX* firstVertex = createList( aPoly );
85
86 for( const VECTOR2I& pt : aPoly.CPoints() )
87 m_result.AddVertex( pt );
88
89 if( !firstVertex || firstVertex->prev == firstVertex->next )
90 return true;
91
92 wxLogTrace( TRIANGULATE_TRACE, "Created list with %f area", firstVertex->area() );
93
95 firstVertex->updateList();
96
101 if( aHintData && aHintData->Vertices().size() == m_vertices.size() )
102 {
103 m_result.SetTriangles( aHintData->Triangles() );
104 return true;
105 }
106 else
107 {
108 auto retval = earcutList( firstVertex );
109
110 if( !retval )
111 {
112 wxLogTrace( TRIANGULATE_TRACE, "Tesselation failed, logging remaining vertices" );
113 logRemaining();
114 }
115
116 m_vertices.clear();
117 return retval;
118 }
119 }
120
121private:
122
127 {
128 std::set<VERTEX*> seen;
129 wxLog::EnableLogging();
130 for( VERTEX& p : m_vertices )
131 {
132 if( !p.next || p.next == &p || seen.find( &p ) != seen.end() )
133 continue;
134
135 logVertices( &p, &seen );
136 }
137 }
138
139 void logVertices( VERTEX* aStart, std::set<VERTEX*>* aSeen )
140 {
141 if( aSeen && aSeen->count( aStart ) )
142 return;
143
144 if( aSeen )
145 aSeen->insert( aStart );
146
147 int count = 1;
148 VERTEX* p = aStart->next;
149 wxString msg = wxString::Format( "Vertices: %d,%d,", static_cast<int>( aStart->x ),
150 static_cast<int>( aStart->y ) );
151
152 do
153 {
154 msg += wxString::Format( "%d,%d,", static_cast<int>( p->x ), static_cast<int>( p->y ) );
155
156 if( aSeen )
157 aSeen->insert( p );
158
159 p = p->next;
160 count++;
161 } while( p != aStart );
162
163 if( count < 3 ) // Don't log anything that only has 2 or fewer points
164 return;
165
166 msg.RemoveLast();
167 wxLogTrace( TRIANGULATE_TRACE, msg );
168 }
169
175 {
176 if( !aStart || aStart->next == aStart->prev )
177 return aStart;
178
179 VERTEX* p = aStart;
180 VERTEX* next = p->next;
181 VERTEX* retval = aStart;
182 int count = 0;
183
185 sq_dist *= sq_dist;
186
187 do
188 {
189 VECTOR2D diff = VECTOR2D( next->x - p->x, next->y - p->y );
190
191 if( diff.SquaredEuclideanNorm() < sq_dist )
192 {
193 if( next == aStart )
194 {
195 retval = p;
196 aStart->remove();
197 count++;
198 break;
199 }
200
201 next = next->next;
202 p->next->remove();
203 count++;
204 retval = p;
205 }
206 else
207 {
208 p = next;
209 next = next->next;
210 }
211 } while( p != aStart && next && p );
212
213 wxLogTrace( TRIANGULATE_TRACE, "Removed %d points in simplifyList", count );
214
215 if( count )
216 return retval;
217
218 return nullptr;
219 }
220
221
230 {
231 VERTEX* retval = nullptr;
232 size_t count = 0;
233
234 if( ( retval = simplifyList( aStart ) ) )
235 aStart = retval;
236
237 wxASSERT( aStart->next && aStart->prev );
238
239 VERTEX* p = aStart->next;
240
241 while( p != aStart && p->next && p->prev )
242 {
243 // We make a dummy triangle that is actually part of the existing line segment
244 // and measure its area. This will not be exactly zero due to floating point
245 // errors. We then look for areas that are less than 4 times the area of the
246 // dummy triangle. For small triangles, this is a small number
247 VERTEX tmp( 0, 0.5 * ( p->prev->x + p->next->x ), 0.5 * ( p->prev->y + p->next->y ), this );
248 double null_area = 4.0 * std::abs( area( p->prev, &tmp, p->next ) );
249
250 if( *p == *( p->next ) || std::abs( area( p->prev, p, p->next ) ) <= null_area )
251 {
252 // This is a spike, remove it, leaving only one point
253 if( *( p->next ) == *( p->prev ) )
254 p->next->remove();
255
256 p = p->prev;
257 p->next->remove();
258 retval = p;
259 ++count;
260
261 if( p == p->next )
262 break;
263
264 // aStart was removed above, so we need to reset it
265 if( !aStart->next )
266 aStart = p->prev;
267
268 continue;
269 }
270
271 p = p->next;
272 };
273
275 if( !p->next || p->next == p || p->next == p->prev )
276 return p;
277
278 // We needed an end point above that wouldn't be removed, so
279 // here we do the final check for this as a Steiner point
280 VERTEX tmp( 0, 0.5 * ( p->prev->x + p->next->x ),
281 0.5 * ( p->prev->y + p->next->y ), this );
282 double null_area = 4.0 * std::abs( area( p->prev, &tmp, p->next ) );
283
284 if( std::abs( area( p->prev, p, p->next ) ) <= null_area )
285 {
286 retval = p->next;
287 p->remove();
288 ++count;
289 }
290
291 wxLogTrace( TRIANGULATE_TRACE, "Removed %zu NULL triangles", count );
292
293 return retval;
294 }
295
309 bool earcutList( VERTEX* aPoint, int pass = 0 )
310 {
311 wxLogTrace( TRIANGULATE_TRACE, "earcutList starting at %p for pass %d", aPoint, pass );
312
313 if( !aPoint )
314 return true;
315
316 VERTEX* stop = aPoint;
317 VERTEX* prev;
318 VERTEX* next;
319 int internal_pass = 1;
320
321 while( aPoint->prev != aPoint->next )
322 {
323 prev = aPoint->prev;
324 next = aPoint->next;
325
326 if( aPoint->isEar() )
327 {
328 // Tiny ears cannot be seen on the screen
329 if( !isTooSmall( aPoint ) )
330 {
331 m_result.AddTriangle( prev->i, aPoint->i, next->i );
332 }
333 else
334 {
335 wxLogTrace( TRIANGULATE_TRACE, "Ignoring tiny ear with area %f",
336 area( prev, aPoint, next ) );
337 }
338
339 aPoint->remove();
340
341 // Skip one vertex as the triangle will account for the prev node
342 aPoint = next->next;
343 stop = next->next;
344
345 continue;
346 }
347
348 VERTEX* nextNext = next->next;
349
350 if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
351 locallyInside( prev, nextNext ) &&
352 locallyInside( nextNext, prev ) )
353 {
354 wxLogTrace( TRIANGULATE_TRACE,
355 "Local intersection detected. Merging minor triangle with area %f",
356 area( prev, aPoint, nextNext ) );
357 m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
358
359 // remove two nodes involved
360 next->remove();
361 aPoint->remove();
362
363 aPoint = nextNext;
364 stop = nextNext;
365
366 continue;
367 }
368
369 aPoint = next;
370
371 /*
372 * We've searched the entire polygon for available ears and there are still
373 * un-sliced nodes remaining.
374 */
375 if( aPoint == stop && aPoint->prev != aPoint->next )
376 {
377 VERTEX* newPoint;
378
379 // Removing null triangles will remove steiner points as well as colinear points
380 // that are three in a row. Because our next step is to subdivide the polygon,
381 // we need to allow it to add the subdivided points first. This is why we only
382 // run the RemoveNullTriangles function after the first pass.
383 if( ( internal_pass == 2 ) && ( newPoint = removeNullTriangles( aPoint ) ) )
384 {
385 // There are no remaining triangles in the list
386 if( newPoint->next == newPoint->prev )
387 break;
388
389 aPoint = newPoint;
390 stop = newPoint;
391 continue;
392 }
393
394 ++internal_pass;
395
396 // This will subdivide the polygon 2 times. The first pass will add enough points
397 // such that each edge is less than the average edge length. If this doesn't work
398 // The next pass will remove the null triangles (above) and subdivide the polygon
399 // again, this time adding one point to each long edge (and thereby changing the locations)
400 if( internal_pass < 4 )
401 {
402 wxLogTrace( TRIANGULATE_TRACE, "Subdividing polygon" );
403 subdividePolygon( aPoint, internal_pass );
404 continue;
405 }
406
407 // If we don't have any NULL triangles left, cut the polygon in two and try again
408 wxLogTrace( TRIANGULATE_TRACE, "Splitting polygon" );
409
410 if( !splitPolygon( aPoint ) )
411 return false;
412
413 break;
414 }
415 }
416
417 // Check to see if we are left with only three points in the polygon
418 if( aPoint->next && aPoint->prev == aPoint->next->next )
419 {
420 // Three concave points will never be able to be triangulated because they were
421 // created by an intersecting polygon, so just drop them.
422 if( area( aPoint->prev, aPoint, aPoint->next ) >= 0 )
423 return true;
424 }
425
426 /*
427 * At this point, our polygon should be fully tessellated.
428 */
429 if( aPoint->prev != aPoint->next )
431
432 return true;
433 }
434
435
440 bool isTooSmall( const VERTEX* aPoint ) const
441 {
443 double prev_sq_len = ( aPoint->prev->x - aPoint->x ) * ( aPoint->prev->x - aPoint->x ) +
444 ( aPoint->prev->y - aPoint->y ) * ( aPoint->prev->y - aPoint->y );
445 double next_sq_len = ( aPoint->next->x - aPoint->x ) * ( aPoint->next->x - aPoint->x ) +
446 ( aPoint->next->y - aPoint->y ) * ( aPoint->next->y - aPoint->y );
447 double opp_sq_len = ( aPoint->next->x - aPoint->prev->x ) * ( aPoint->next->x - aPoint->prev->x ) +
448 ( aPoint->next->y - aPoint->prev->y ) * ( aPoint->next->y - aPoint->prev->y );
449
450 return ( prev_sq_len < min_area || next_sq_len < min_area || opp_sq_len < min_area );
451 }
452
456 void subdividePolygon( VERTEX* aStart, int pass = 0 )
457 {
458 VERTEX* p = aStart;
459
460 struct VertexComparator {
461 bool operator()(const std::pair<VERTEX*,double>& a, const std::pair<VERTEX*,double>& b) const {
462 return a.second > b.second;
463 }
464 };
465
466 std::set<std::pair<VERTEX*,double>, VertexComparator> longest;
467 double avg = 0.0;
468
469 do
470 {
471 double len = ( p->x - p->next->x ) * ( p->x - p->next->x ) +
472 ( p->y - p->next->y ) * ( p->y - p->next->y );
473 longest.emplace( p, len );
474
475 avg += len;
476 p = p->next;
477 } while (p != aStart);
478
479 avg /= longest.size();
480 wxLogTrace( TRIANGULATE_TRACE, "Average length: %f", avg );
481
482 for( auto it = longest.begin(); it != longest.end() && it->second > avg; ++it )
483 {
484 wxLogTrace( TRIANGULATE_TRACE, "Subdividing edge with length %f", it->second );
485 VERTEX* a = it->first;
486 VERTEX* b = a->next;
487 VERTEX* last = a;
488
489 // We adjust the number of divisions based on the pass in order to progressively
490 // subdivide the polygon when triangulation fails
491 int divisions = avg / it->second + 2 + pass;
492 double step = 1.0 / divisions;
493
494 for( int i = 1; i < divisions; i++ )
495 {
496 double x = a->x * ( 1.0 - step * i ) + b->x * ( step * i );
497 double y = a->y * ( 1.0 - step * i ) + b->y * ( step * i );
498 last = insertTriVertex( VECTOR2I( x, y ), last );
499 }
500 }
501
502 // update z-order of the vertices
503 aStart->updateList();
504 }
505
512 bool splitPolygon( VERTEX* start )
513 {
514 VERTEX* origPoly = start;
515
516 // If we have fewer than 4 points, we cannot split the polygon
517 if( !start || !start->next || start->next == start->prev
518 || start->next->next == start->prev )
519 {
520 return true;
521 }
522
523 // Our first attempts to split the polygon will be at overlapping points.
524 // These are natural split points and we only need to switch the loop directions
525 // to generate two new loops. Since they are overlapping, we are do not
526 // need to create a new segment to disconnect the two loops.
527 do
528 {
529 std::vector<VERTEX*> overlapPoints;
530 VERTEX* z_pt = origPoly;
531
532 while ( z_pt->prevZ && *z_pt->prevZ == *origPoly )
533 z_pt = z_pt->prevZ;
534
535 overlapPoints.push_back( z_pt );
536
537 while( z_pt->nextZ && *z_pt->nextZ == *origPoly )
538 {
539 z_pt = z_pt->nextZ;
540 overlapPoints.push_back( z_pt );
541 }
542
543 if( overlapPoints.size() != 2 || overlapPoints[0]->next == overlapPoints[1]
544 || overlapPoints[0]->prev == overlapPoints[1] )
545 {
546 origPoly = origPoly->next;
547 continue;
548 }
549
550 if( overlapPoints[0]->area( overlapPoints[1] ) < 0 || overlapPoints[1]->area( overlapPoints[0] ) < 0 )
551 {
552 wxLogTrace( TRIANGULATE_TRACE, "Split generated a hole, skipping" );
553 origPoly = origPoly->next;
554 continue;
555 }
556
557 wxLogTrace( TRIANGULATE_TRACE, "Splitting at overlap point %f, %f", overlapPoints[0]->x, overlapPoints[0]->y );
558 std::swap( overlapPoints[0]->next, overlapPoints[1]->next );
559 overlapPoints[0]->next->prev = overlapPoints[0];
560 overlapPoints[1]->next->prev = overlapPoints[1];
561
562 overlapPoints[0]->updateList();
563 overlapPoints[1]->updateList();
564 logVertices( overlapPoints[0], nullptr );
565 logVertices( overlapPoints[1], nullptr );
566 bool retval = earcutList( overlapPoints[0] ) && earcutList( overlapPoints[1] );
567
568 wxLogTrace( TRIANGULATE_TRACE, "%s at first overlap split", retval ? "Success" : "Failed" );
569 return retval;
570
571
572 } while ( origPoly != start );
573
574 // If we've made it through the split algorithm and we still haven't found a
575 // set of overlapping points, we need to create a new segment to split the polygon
576 // into two separate polygons. We do this by finding the two vertices that form
577 // a valid line (does not cross the existing polygon)
578 do
579 {
580 VERTEX* marker = origPoly->next->next;
581
582 while( marker != origPoly->prev )
583 {
584 // Find a diagonal line that is wholly enclosed by the polygon interior
585 if( origPoly->next && origPoly->i != marker->i && goodSplit( origPoly, marker ) )
586 {
587 VERTEX* newPoly = origPoly->split( marker );
588
589 origPoly->updateList();
590 newPoly->updateList();
591
592 bool retval = earcutList( origPoly ) && earcutList( newPoly );
593
594 wxLogTrace( TRIANGULATE_TRACE, "%s at split", retval ? "Success" : "Failed" );
595 return retval;
596 }
597
598 marker = marker->next;
599 }
600
601 origPoly = origPoly->next;
602 } while( origPoly != start );
603
604 wxLogTrace( TRIANGULATE_TRACE, "Could not find a valid split point" );
605 return false;
606 }
607
617 bool goodSplit( const VERTEX* a, const VERTEX* b ) const
618 {
619 bool a_on_edge = ( a->nextZ && *a == *a->nextZ ) || ( a->prevZ && *a == *a->prevZ );
620 bool b_on_edge = ( b->nextZ && *b == *b->nextZ ) || ( b->prevZ && *b == *b->prevZ );
621 bool no_intersect = a->next->i != b->i && a->prev->i != b->i && !intersectsPolygon( a, b );
622 bool local_split = locallyInside( a, b ) && locallyInside( b, a ) && middleInside( a, b );
623 bool same_dir = area( a->prev, a, b->prev ) != 0.0 || area( a, b->prev, b ) != 0.0;
624 bool has_len = ( *a == *b ) && area( a->prev, a, a->next ) > 0 && area( b->prev, b, b->next ) > 0;
625 bool pos_area = a->area( b ) > 0 && b->area( a ) > 0;
626
627 return no_intersect && local_split && ( same_dir || has_len ) && !a_on_edge && !b_on_edge && pos_area;
628
629 }
630
631
632 constexpr int sign( double aVal ) const
633 {
634 return ( aVal > 0 ) - ( aVal < 0 );
635 }
636
640 constexpr bool overlapping( const VERTEX* p, const VERTEX* q, const VERTEX* r ) const
641 {
642 return q->x <= std::max( p->x, r->x ) &&
643 q->x >= std::min( p->x, r->x ) &&
644 q->y <= std::max( p->y, r->y ) &&
645 q->y >= std::min( p->y, r->y );
646 }
647
653 bool intersects( const VERTEX* p1, const VERTEX* q1, const VERTEX* p2, const VERTEX* q2 ) const
654 {
655 int sign1 = sign( area( p1, q1, p2 ) );
656 int sign2 = sign( area( p1, q1, q2 ) );
657 int sign3 = sign( area( p2, q2, p1 ) );
658 int sign4 = sign( area( p2, q2, q1 ) );
659
660 if( sign1 != sign2 && sign3 != sign4 )
661 return true;
662
663 if( sign1 == 0 && overlapping( p1, p2, q1 ) )
664 return true;
665
666 if( sign2 == 0 && overlapping( p1, q2, q1 ) )
667 return true;
668
669 if( sign3 == 0 && overlapping( p2, p1, q2 ) )
670 return true;
671
672 if( sign4 == 0 && overlapping( p2, q1, q2 ) )
673 return true;
674
675
676 return false;
677 }
678
685 bool intersectsPolygon( const VERTEX* a, const VERTEX* b ) const
686 {
687 for( size_t ii = 0; ii < m_vertices_original_size; ii++ )
688 {
689 const VERTEX* p = &m_vertices[ii];
690 const VERTEX* q = &m_vertices[( ii + 1 ) % m_vertices_original_size];
691
692 if( p->i == a->i || p->i == b->i || q->i == a->i || q->i == b->i )
693 continue;
694
695 if( intersects( p, q, a, b ) )
696 return true;
697 }
698
699 return false;
700 }
701
709 {
710 m_result.AddVertex( pt );
711 return insertVertex( m_result.GetVertexCount() - 1, pt, nullptr );
712 }
713
714private:
717};
718
719#endif //__POLYGON_TRIANGULATION_H
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
size_type GetHeight() const
Definition: box2.h:205
size_type GetWidth() const
Definition: box2.h:204
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
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 ...
constexpr int sign(double aVal) const
void logVertices(VERTEX *aStart, std::set< VERTEX * > *aSeen)
VERTEX * insertTriVertex(const VECTOR2I &pt, VERTEX *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...
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)
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.
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)
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const std::vector< VECTOR2I > & CPoints() const
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:302
std::deque< VERTEX > m_vertices
Definition: vertex_set.h:339
bool middleInside(const VERTEX *a, const VERTEX *b) const
Check if the middle of the segment from a to b is inside the polygon.
Definition: vertex_set.cpp:162
VERTEX * createList(const SHAPE_LINE_CHAIN &points, VERTEX *aTail=nullptr, void *aUserData=nullptr)
Create a list of vertices from a line chain.
Definition: vertex_set.cpp:9
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...
Definition: vertex_set.cpp:150
BOX2I m_bbox
Definition: vertex_set.h:338
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.
Definition: vertex_set.cpp:83
VERTEX * insertVertex(int aIndex, const VECTOR2I &pt, VERTEX *last, void *aUserData=nullptr)
Insert a vertex into the vertex set.
Definition: vertex_set.cpp:187
VERTEX * split(VERTEX *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...
Definition: vertex_set.cpp:209
const double x
Definition: vertex_set.h:231
VERTEX * next
Definition: vertex_set.h:237
VERTEX * prevZ
Definition: vertex_set.h:243
void updateList()
After inserting or changing nodes, this function should be called to remove duplicate vertices and en...
Definition: vertex_set.h:121
VERTEX * nextZ
Definition: vertex_set.h:244
VERTEX * prev
Definition: vertex_set.h:236
const int i
Definition: vertex_set.h:230
void remove()
Remove the node from the linked list and z-ordered linked list.
Definition: vertex_set.h:84
bool isEar() const
Check whether the given vertex is in the middle of an ear.
Definition: vertex_set.cpp:241
double area(const VERTEX *aEnd=nullptr) const
Returns the signed area of the polygon connected to the current vertex, optionally ending at a specif...
Definition: vertex_set.h:202
const double y
Definition: vertex_set.h:232
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:390
#define TRIANGULATE_TRACE
CITER next(CITER it)
Definition: ptree.cpp:126
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:673
VECTOR2< double > VECTOR2D
Definition: vector2d.h:672