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-2021 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 <clipper.hpp>
56#include <math/box2.h>
57#include <math/vector2d.h>
58
60{
61public:
63 m_result( aResult )
64 {};
65
67 {
68 m_bbox = aPoly.BBox();
70
71 if( !m_bbox.GetWidth() || !m_bbox.GetHeight() )
72 return false;
73
77 Vertex* firstVertex = createList( aPoly );
78 if( !firstVertex || firstVertex->prev == firstVertex->next )
79 return false;
80
81 firstVertex->updateList();
82
83 auto retval = earcutList( firstVertex );
84 m_vertices.clear();
85 return retval;
86 }
87
88private:
89 struct Vertex
90 {
91 Vertex( size_t aIndex, double aX, double aY, PolygonTriangulation* aParent ) :
92 i( aIndex ),
93 x( aX ),
94 y( aY ),
95 parent( aParent )
96 {
97 }
98
99 Vertex& operator=( const Vertex& ) = delete;
100 Vertex& operator=( Vertex&& ) = delete;
101
102 bool operator==( const Vertex& rhs ) const
103 {
104 return this->x == rhs.x && this->y == rhs.y;
105 }
106 bool operator!=( const Vertex& rhs ) const { return !( *this == rhs ); }
107
108
120 {
121 parent->m_vertices.emplace_back( i, x, y, parent );
122 Vertex* a2 = &parent->m_vertices.back();
123 parent->m_vertices.emplace_back( b->i, b->x, b->y, parent );
124 Vertex* b2 = &parent->m_vertices.back();
125 Vertex* an = next;
126 Vertex* bp = b->prev;
127
128 next = b;
129 b->prev = this;
130
131 a2->next = an;
132 an->prev = a2;
133
134 b2->next = a2;
135 a2->prev = b2;
136
137 bp->next = b2;
138 b2->prev = bp;
139
140 return b2;
141 }
142
146 void remove()
147 {
148 next->prev = prev;
149 prev->next = next;
150
151 if( prevZ )
152 prevZ->nextZ = nextZ;
153
154 if( nextZ )
155 nextZ->prevZ = prevZ;
156
157 next = nullptr;
158 prev = nullptr;
159 nextZ = nullptr;
160 prevZ = nullptr;
161 }
162
164 {
165 if( !z )
166 z = parent->zOrder( x, y );
167 }
168
174 {
175 Vertex* p = next;
176
177 while( p != this )
178 {
182 if( *p == *p->next )
183 {
184 p = p->prev;
185 p->next->remove();
186
187 if( p == p->next )
188 break;
189 }
190
191 p->updateOrder();
192 p = p->next;
193 };
194
195 updateOrder();
196 zSort();
197 }
198
202 void zSort()
203 {
204 std::deque<Vertex*> queue;
205
206 queue.push_back( this );
207
208 for( auto p = next; p && p != this; p = p->next )
209 queue.push_back( p );
210
211 std::sort( queue.begin(), queue.end(), []( const Vertex* a, const Vertex* b )
212 {
213 if( a->z != b->z )
214 return a->z < b->z;
215
216 if( a->x != b->x )
217 return a->x < b->x;
218
219 if( a->y != b->y )
220 return a->y < b->y;
221
222 return a->i < b->i;
223 } );
224
225 Vertex* prev_elem = nullptr;
226
227 for( auto elem : queue )
228 {
229 if( prev_elem )
230 prev_elem->nextZ = elem;
231
232 elem->prevZ = prev_elem;
233 prev_elem = elem;
234 }
235
236 prev_elem->nextZ = nullptr;
237 }
238
239
243 bool inTriangle( const Vertex& a, const Vertex& b, const Vertex& c )
244 {
245 return ( c.x - x ) * ( a.y - y ) - ( a.x - x ) * ( c.y - y ) >= 0
246 && ( a.x - x ) * ( b.y - y ) - ( b.x - x ) * ( a.y - y ) >= 0
247 && ( b.x - x ) * ( c.y - y ) - ( c.x - x ) * ( b.y - y ) >= 0;
248 }
249
250 const size_t i;
251 const double x;
252 const double y;
254
255 // previous and next vertices nodes in a polygon ring
256 Vertex* prev = nullptr;
257 Vertex* next = nullptr;
258
259 // z-order curve value
260 int32_t z = 0;
261
262 // previous and next nodes in z-order
263 Vertex* prevZ = nullptr;
264 Vertex* nextZ = nullptr;
265 };
266
272 int32_t zOrder( const double aX, const double aY ) const
273 {
274 int32_t x = static_cast<int32_t>( 32767.0 * ( aX - m_bbox.GetX() ) / m_bbox.GetWidth() );
275 int32_t y = static_cast<int32_t>( 32767.0 * ( aY - m_bbox.GetY() ) / m_bbox.GetHeight() );
276
277 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
278 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
279 x = ( x | ( x << 2 ) ) & 0x33333333;
280 x = ( x | ( x << 1 ) ) & 0x55555555;
281
282 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
283 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
284 y = ( y | ( y << 2 ) ) & 0x33333333;
285 y = ( y | ( y << 1 ) ) & 0x55555555;
286
287 return x | ( y << 1 );
288 }
289
298 {
299 Vertex* retval = nullptr;
300 Vertex* p = aStart->next;
301
302 while( p != aStart )
303 {
304 if( area( p->prev, p, p->next ) == 0.0 )
305 {
306 p = p->prev;
307 p->next->remove();
308 retval = aStart;
309
310 if( p == p->next )
311 break;
312 }
313 p = p->next;
314 };
315
316 // We needed an end point above that wouldn't be removed, so
317 // here we do the final check for this as a Steiner point
318 if( area( aStart->prev, aStart, aStart->next ) == 0.0 )
319 {
320 retval = p->next;
321 p->remove();
322 }
323
324 return retval;
325 }
326
330 Vertex* createList( const ClipperLib::Path& aPath )
331 {
332 Vertex* tail = nullptr;
333 double sum = 0.0;
334 auto len = aPath.size();
335
336 // Check for winding order
337 for( size_t i = 0; i < len; i++ )
338 {
339 auto p1 = aPath.at( i );
340 auto p2 = aPath.at( ( i + 1 ) < len ? i + 1 : 0 );
341
342 sum += ( ( p2.X - p1.X ) * ( p2.Y + p1.Y ) );
343 }
344
345 if( sum <= 0.0 )
346 {
347 for( auto point : aPath )
348 tail = insertVertex( VECTOR2I( point.X, point.Y ), tail );
349 }
350 else
351 {
352 for( size_t i = 0; i < len; i++ )
353 {
354 auto p = aPath.at( len - i - 1 );
355 tail = insertVertex( VECTOR2I( p.X, p.Y ), tail );
356 }
357 }
358
359 if( tail && ( *tail == *tail->next ) )
360 {
361 tail->next->remove();
362 }
363
364 return tail;
365
366 }
367
372 {
373 Vertex* tail = nullptr;
374 double sum = 0.0;
375
376 // Check for winding order
377 for( int i = 0; i < points.PointCount(); i++ )
378 {
379 VECTOR2D p1 = points.CPoint( i );
380 VECTOR2D p2 = points.CPoint( i + 1 );
381
382 sum += ( ( p2.x - p1.x ) * ( p2.y + p1.y ) );
383 }
384
385 if( sum > 0.0 )
386 for( int i = points.PointCount() - 1; i >= 0; i--)
387 tail = insertVertex( points.CPoint( i ), tail );
388 else
389 for( int i = 0; i < points.PointCount(); i++ )
390 tail = insertVertex( points.CPoint( i ), tail );
391
392 if( tail && ( *tail == *tail->next ) )
393 {
394 tail->next->remove();
395 }
396
397 return tail;
398 }
399
413 bool earcutList( Vertex* aPoint, int pass = 0 )
414 {
415 if( !aPoint )
416 return true;
417
418 Vertex* stop = aPoint;
419 Vertex* prev;
420 Vertex* next;
421
422 while( aPoint->prev != aPoint->next )
423 {
424 prev = aPoint->prev;
425 next = aPoint->next;
426
427 if( isEar( aPoint ) )
428 {
429 m_result.AddTriangle( prev->i, aPoint->i, next->i );
430 aPoint->remove();
431
432 // Skip one vertex as the triangle will account for the prev node
433 aPoint = next->next;
434 stop = next->next;
435
436 continue;
437 }
438
439 Vertex* nextNext = next->next;
440
441 if( *prev != *nextNext && intersects( prev, aPoint, next, nextNext ) &&
442 locallyInside( prev, nextNext ) &&
443 locallyInside( nextNext, prev ) )
444 {
445 m_result.AddTriangle( prev->i, aPoint->i, nextNext->i );
446
447 // remove two nodes involved
448 next->remove();
449 aPoint->remove();
450
451 aPoint = nextNext;
452 stop = nextNext;
453
454 continue;
455 }
456
457 aPoint = next;
458
459 /*
460 * We've searched the entire polygon for available ears and there are still
461 * un-sliced nodes remaining.
462 */
463 if( aPoint == stop )
464 {
465 // First, try to remove the remaining steiner points
466 // If aPoint is a steiner, we need to re-assign both the start and stop points
467 if( auto newPoint = removeNullTriangles( aPoint ) )
468 {
469 aPoint = newPoint;
470 stop = newPoint;
471 continue;
472 }
473
474 // If we don't have any NULL triangles left, cut the polygon in two and try again
475 splitPolygon( aPoint );
476 break;
477 }
478 }
479
480 // Check to see if we are left with only three points in the polygon
481 if( aPoint->next && aPoint->prev == aPoint->next->next )
482 {
483 // Three concave points will never be able to be triangulated because they were
484 // created by an intersecting polygon, so just drop them.
485 if( area( aPoint->prev, aPoint, aPoint->next ) >= 0 )
486 return true;
487 }
488
489 /*
490 * At this point, our polygon should be fully tessellated.
491 */
492 return( aPoint->prev == aPoint->next );
493 }
494
504 bool isEar( Vertex* aEar ) const
505 {
506 const Vertex* a = aEar->prev;
507 const Vertex* b = aEar;
508 const Vertex* c = aEar->next;
509
510 // If the area >=0, then the three points for a concave sequence
511 // with b as the reflex point
512 if( area( a, b, c ) >= 0 )
513 return false;
514
515 // triangle bbox
516 const double minTX = std::min( a->x, std::min( b->x, c->x ) );
517 const double minTY = std::min( a->y, std::min( b->y, c->y ) );
518 const double maxTX = std::max( a->x, std::max( b->x, c->x ) );
519 const double maxTY = std::max( a->y, std::max( b->y, c->y ) );
520
521 // z-order range for the current triangle bounding box
522 const int32_t minZ = zOrder( minTX, minTY );
523 const int32_t maxZ = zOrder( maxTX, maxTY );
524
525 // first look for points inside the triangle in increasing z-order
526 Vertex* p = aEar->nextZ;
527
528 while( p && p->z <= maxZ )
529 {
530 if( p != a && p != c
531 && p->inTriangle( *a, *b, *c )
532 && area( p->prev, p, p->next ) >= 0 )
533 return false;
534
535 p = p->nextZ;
536 }
537
538 // then look for points in decreasing z-order
539 p = aEar->prevZ;
540
541 while( p && p->z >= minZ )
542 {
543 if( p != a && p != c
544 && p->inTriangle( *a, *b, *c )
545 && area( p->prev, p, p->next ) >= 0 )
546 return false;
547
548 p = p->prevZ;
549 }
550
551 return true;
552 }
553
560 void splitPolygon( Vertex* start )
561 {
562 Vertex* origPoly = start;
563
564 do
565 {
566 Vertex* marker = origPoly->next->next;
567
568 while( marker != origPoly->prev )
569 {
570 // Find a diagonal line that is wholly enclosed by the polygon interior
571 if( origPoly->i != marker->i && goodSplit( origPoly, marker ) )
572 {
573 Vertex* newPoly = origPoly->split( marker );
574
575 origPoly->updateList();
576 newPoly->updateList();
577
578 earcutList( origPoly );
579 earcutList( newPoly );
580 return;
581 }
582
583 marker = marker->next;
584 }
585
586 origPoly = origPoly->next;
587 } while( origPoly != start );
588 }
589
598 bool goodSplit( const Vertex* a, const Vertex* b ) const
599 {
600 return a->next->i != b->i &&
601 a->prev->i != b->i &&
602 !intersectsPolygon( a, b ) &&
603 locallyInside( a, b );
604 }
605
609 double area( const Vertex* p, const Vertex* q, const Vertex* r ) const
610 {
611 return ( q->y - p->y ) * ( r->x - q->x ) - ( q->x - p->x ) * ( r->y - q->y );
612 }
613
619 bool intersects( const Vertex* p1, const Vertex* q1, const Vertex* p2, const Vertex* q2 ) const
620 {
621 if( ( *p1 == *q1 && *p2 == *q2 ) || ( *p1 == *q2 && *p2 == *q1 ) )
622 return true;
623
624 return ( area( p1, q1, p2 ) > 0 ) != ( area( p1, q1, q2 ) > 0 )
625 && ( area( p2, q2, p1 ) > 0 ) != ( area( p2, q2, q1 ) > 0 );
626 }
627
634 bool intersectsPolygon( const Vertex* a, const Vertex* b ) const
635 {
636 const Vertex* p = a->next;
637
638 do
639 {
640 if( p->i != a->i &&
641 p->next->i != a->i &&
642 p->i != b->i &&
643 p->next->i != b->i && intersects( p, p->next, a, b ) )
644 return true;
645
646 p = p->next;
647 } while( p != a );
648
649 return false;
650 }
651
661 bool locallyInside( const Vertex* a, const Vertex* b ) const
662 {
663 if( area( a->prev, a, a->next ) < 0 )
664 return area( a, b, a->next ) >= 0 && area( a, a->prev, b ) >= 0;
665 else
666 return area( a, b, a->prev ) < 0 || area( a, a->next, b ) < 0;
667 }
668
675 Vertex* insertVertex( const VECTOR2I& pt, Vertex* last )
676 {
677 m_result.AddVertex( pt );
678 m_vertices.emplace_back( m_result.GetVertexCount() - 1, pt.x, pt.y, this );
679
680 Vertex* p = &m_vertices.back();
681
682 if( !last )
683 {
684 p->prev = p;
685 p->next = p;
686 }
687 else
688 {
689 p->next = last->next;
690 p->prev = last;
691 last->next->prev = p;
692 last->next = p;
693 }
694 return p;
695 }
696
697private:
699 std::deque<Vertex> m_vertices;
701};
702
703#endif //__POLYGON_TRIANGULATION_H
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetY() const
Definition: box2.h:181
coord_type GetWidth() const
Definition: box2.h:187
coord_type GetX() const
Definition: box2.h:180
Vertex * createList(const SHAPE_LINE_CHAIN &points)
Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.
Vertex * removeNullTriangles(Vertex *aStart)
Iterate through the list to remove NULL triangles if they exist.
int32_t zOrder(const double aX, const double aY) const
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks....
bool goodSplit(const Vertex *a, const Vertex *b) const
Check if a segment joining two vertices lies fully inside the polygon.
std::deque< Vertex > m_vertices
bool isEar(Vertex *aEar) const
Check whether the given vertex is in the middle of an ear.
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 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 * createList(const ClipperLib::Path &aPath)
Take a Clipper path and converts it into a circular, doubly-linked list for triangulation.
SHAPE_POLY_SET::TRIANGULATED_POLYGON & m_result
void 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 earcutList(Vertex *aPoint, int pass=0)
Walk through a circular linked list starting at aPoint.
bool TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly)
Vertex * insertVertex(const VECTOR2I &pt, Vertex *last)
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existi...
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.
PolygonTriangulation(SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
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...
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)
void AddTriangle(int a, int b, int c)
CITER next(CITER it)
Definition: ptree.cpp:126
void zSort()
Sort all vertices in this vertex's list by their Morton code.
void updateList()
After inserting or changing nodes, this function should be called to remove duplicate vertices and en...
Vertex(size_t aIndex, double aX, double aY, PolygonTriangulation *aParent)
void remove()
Remove the node from the linked list and z-ordered linked list.
bool operator==(const Vertex &rhs) const
Vertex & operator=(Vertex &&)=delete
bool inTriangle(const Vertex &a, const Vertex &b, const Vertex &c)
Check to see if triangle surrounds our current vertex.
bool operator!=(const Vertex &rhs) const
Vertex & operator=(const Vertex &)=delete
Vertex * split(Vertex *b)
Split the referenced polygon between the reference point and vertex b, assuming they are in the same ...
VECTOR2< int > VECTOR2I
Definition: vector2d.h:588