46#ifndef __POLYGON_TRIANGULATION_H
47#define __POLYGON_TRIANGULATION_H
62#define TRIANGULATE_TRACE "triangulate"
86 if( !firstVertex || firstVertex->
prev == firstVertex->
next )
102 wxLogTrace(
TRIANGULATE_TRACE,
"Tesselation failed, logging remaining vertices" );
127 return this->
x == rhs.
x && this->
y == rhs.
y;
227 std::deque<VERTEX*> queue;
229 queue.push_back(
this );
231 for(
auto p =
next; p && p !=
this; p = p->
next )
232 queue.push_back( p );
234 std::sort( queue.begin(), queue.end(), [](
const VERTEX* a,
const VERTEX* b )
248 VERTEX* prev_elem =
nullptr;
250 for(
auto elem : queue )
253 prev_elem->
nextZ = elem;
255 elem->
prevZ = prev_elem;
259 prev_elem->
nextZ =
nullptr;
268 return ( c.
x -
x ) * ( a.
y -
y ) - ( a.
x -
x ) * ( c.
y -
y ) >= 0
269 && ( a.
x -
x ) * ( b.
y -
y ) - ( b.
x -
x ) * ( a.
y -
y ) >= 0
270 && ( b.
x -
x ) * ( c.
y -
y ) - ( c.
x -
x ) * ( b.
y -
y ) >= 0;
286 }
while( p !=
this && p != aEnd );
289 a += ( p->
x + aEnd->x ) * ( aEnd->y - p->
y );
316 int32_t
zOrder(
const double aX,
const double aY )
const
321 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
322 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
323 x = ( x | ( x << 2 ) ) & 0x33333333;
324 x = ( x | ( x << 1 ) ) & 0x55555555;
326 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
327 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
328 y = ( y | ( y << 2 ) ) & 0x33333333;
329 y = ( y | ( y << 1 ) ) & 0x55555555;
331 return x | ( y << 1 );
340 std::set<VERTEX*> seen;
341 wxLog::EnableLogging();
344 if( !p.next || p.next == &p || seen.find( &p ) != seen.end() )
353 if( aSeen && aSeen->count( aStart ) )
357 aSeen->insert( aStart );
361 wxString msg = wxString::Format(
"Vertices: %d,%d,",
static_cast<int>( aStart->
x ),
362 static_cast<int>( aStart->
y ) );
366 msg += wxString::Format(
"%d,%d,",
static_cast<int>( p->
x ),
static_cast<int>( p->
y ) );
373 }
while( p != aStart );
428 0.5 * ( aStart->
prev->
y + aStart->
next->
y ),
this );
454 for(
int i = 0; i < points.
PointCount(); i++ )
459 sum += ( ( p2.
x - p1.
x ) * ( p2.
y + p1.
y ) );
462 VECTOR2I last_pt{ std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
466 auto addVertex = [&](
int i )
479 for(
int i = points.
PointCount() - 1; i >= 0; i-- )
484 for(
int i = 0; i < points.
PointCount(); i++ )
488 if( tail && ( *tail == *tail->
next ) )
509 wxLogTrace(
TRIANGULATE_TRACE,
"earcutList starting at %p for pass %d", aPoint, pass );
517 int internal_pass = 1;
519 while( aPoint->
prev != aPoint->
next )
524 if(
isEar( aPoint ) )
548 if( *prev != *nextNext &&
intersects( prev, aPoint,
next, nextNext ) &&
553 "Local intersection detected. Merging minor triangle with area %f",
554 area( prev, aPoint, nextNext ) );
594 if( internal_pass < 4 )
637 double prev_sq_len = ( aPoint->
prev->
x - aPoint->
x ) * ( aPoint->
prev->
x - aPoint->
x ) +
638 ( aPoint->
prev->
y - aPoint->
y ) * ( aPoint->
prev->
y - aPoint->
y );
639 double next_sq_len = ( aPoint->
next->
x - aPoint->
x ) * ( aPoint->
next->
x - aPoint->
x ) +
640 ( aPoint->
next->
y - aPoint->
y ) * ( aPoint->
next->
y - aPoint->
y );
641 double opp_sq_len = ( aPoint->
next->
x - aPoint->
prev->
x ) * ( aPoint->
next->
x - aPoint->
prev->
x ) +
644 return ( prev_sq_len < min_area || next_sq_len < min_area || opp_sq_len < min_area );
665 if(
area( a, b, c ) >= 0 )
669 const double minTX = std::min( a->
x, std::min( b->
x, c->
x ) );
670 const double minTY = std::min( a->
y, std::min( b->
y, c->
y ) );
671 const double maxTX = std::max( a->
x, std::max( b->
x, c->
x ) );
672 const double maxTY = std::max( a->
y, std::max( b->
y, c->
y ) );
675 const int32_t minZ =
zOrder( minTX, minTY );
676 const int32_t maxZ =
zOrder( maxTX, maxTY );
681 while( p && p->
z <= maxZ )
694 while( p && p->
z >= minZ )
714 struct VertexComparator {
715 bool operator()(
const std::pair<VERTEX*,double>& a,
const std::pair<VERTEX*,double>& b)
const {
716 return a.second > b.second;
720 std::set<std::pair<VERTEX*,double>, VertexComparator> longest;
725 double len = ( p->
x - p->
next->
x ) * ( p->
x - p->
next->
x ) +
727 longest.emplace( p, len );
731 }
while (p != aStart);
733 avg /= longest.size();
736 for(
auto it = longest.begin(); it != longest.end() && it->second > avg; ++it )
745 int divisions = avg / it->second + 2 + pass;
746 double step = 1.0 / divisions;
748 for(
int i = 1; i < divisions; i++ )
750 double x = a->
x * ( 1.0 - step * i ) + b->
x * ( step * i );
751 double y = a->
y * ( 1.0 - step * i ) + b->
y * ( step * i );
771 if( !start || !start->
next || start->
next == start->
prev
783 std::vector<VERTEX*> overlapPoints;
786 while ( z_pt->
prevZ && *z_pt->
prevZ == *origPoly )
789 overlapPoints.push_back( z_pt );
791 while( z_pt->
nextZ && *z_pt->
nextZ == *origPoly )
794 overlapPoints.push_back( z_pt );
797 if( overlapPoints.size() != 2 || overlapPoints[0]->next == overlapPoints[1]
798 || overlapPoints[0]->prev == overlapPoints[1] )
800 origPoly = origPoly->
next;
804 if( overlapPoints[0]->
area( overlapPoints[1] ) < 0 || overlapPoints[1]->
area( overlapPoints[0] ) < 0 )
807 origPoly = origPoly->
next;
811 wxLogTrace(
TRIANGULATE_TRACE,
"Splitting at overlap point %f, %f", overlapPoints[0]->x, overlapPoints[0]->y );
812 std::swap( overlapPoints[0]->
next, overlapPoints[1]->
next );
813 overlapPoints[0]->next->prev = overlapPoints[0];
814 overlapPoints[1]->next->prev = overlapPoints[1];
816 overlapPoints[0]->updateList();
817 overlapPoints[1]->updateList();
822 wxLogTrace(
TRIANGULATE_TRACE,
"%s at first overlap split", retval ?
"Success" :
"Failed" );
826 }
while ( origPoly != start );
836 while( marker != origPoly->
prev )
839 if( origPoly->
next && origPoly->
i != marker->
i &&
goodSplit( origPoly, marker ) )
852 marker = marker->
next;
855 origPoly = origPoly->
next;
856 }
while( origPoly != start );
879 bool pos_area = a->
area( b ) > 0 && b->
area( a ) > 0;
881 return no_intersect && local_split && ( same_dir || has_len ) && !a_on_edge && !b_on_edge && pos_area;
890 return ( q->
y - p->
y ) * ( r->
x - q->
x ) - ( q->
x - p->
x ) * ( r->
y - q->
y );
894 constexpr int sign(
double aVal )
const
896 return ( aVal > 0 ) - ( aVal < 0 );
904 return q->
x <= std::max( p->
x, r->
x ) &&
905 q->
x >= std::min( p->
x, r->
x ) &&
906 q->
y <= std::max( p->
y, r->
y ) &&
907 q->
y >= std::min( p->
y, r->
y );
917 int sign1 =
sign(
area( p1, q1, p2 ) );
918 int sign2 =
sign(
area( p1, q1, q2 ) );
919 int sign3 =
sign(
area( p2, q2, p1 ) );
920 int sign4 =
sign(
area( p2, q2, q1 ) );
922 if( sign1 != sign2 && sign3 != sign4 )
952 const VERTEX* q = &*( ++it );
954 if( p->
i == a->
i || p->
i == b->
i || q->
i == a->
i || q->
i == b->
i )
994 double px = ( a->
x + b->
x ) / 2;
995 double py = ( a->
y + b->
y ) / 2;
999 if( ( ( p->
y > py ) != ( p->
next->
y > py ) )
1000 && ( px < ( p->
next->
x - p->
x ) * ( py - p->
y ) / ( p->
next->
y - p->
y ) + p->
x ) )
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
coord_type GetHeight() const
coord_type GetWidth() const
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.
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.
std::deque< TRI > & Triangles()
void AddVertex(const VECTOR2I &aP)
size_t GetVertexCount() const
void AddTriangle(int a, int b, int c)
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
VECTOR2_TRAITS< int >::extended_type extended_type
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)
#define TRIANGULATE_TRACE
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
POLYGON_TRIANGULATION * parent
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