46#ifndef __POLYGON_TRIANGULATION_H
47#define __POLYGON_TRIANGULATION_H
62#define TRIANGULATE_TRACE "triangulate"
84 if( !firstVertex || firstVertex->
prev == firstVertex->
next )
107 wxLogTrace(
TRIANGULATE_TRACE,
"Tesselation failed, logging remaining vertices" );
132 return this->
x == rhs.
x && this->
y == rhs.
y;
232 std::deque<VERTEX*> queue;
234 queue.push_back(
this );
236 for(
auto p =
next; p && p !=
this; p = p->
next )
237 queue.push_back( p );
239 std::sort( queue.begin(), queue.end(), [](
const VERTEX* a,
const VERTEX* b )
253 VERTEX* prev_elem =
nullptr;
255 for(
auto elem : queue )
258 prev_elem->
nextZ = elem;
260 elem->
prevZ = prev_elem;
264 prev_elem->
nextZ =
nullptr;
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;
291 }
while( p !=
this && p != aEnd );
294 a += ( p->
x + aEnd->x ) * ( aEnd->y - p->
y );
321 int32_t
zOrder(
const double aX,
const double aY )
const
326 x = ( x | ( x << 8 ) ) & 0x00FF00FF;
327 x = ( x | ( x << 4 ) ) & 0x0F0F0F0F;
328 x = ( x | ( x << 2 ) ) & 0x33333333;
329 x = ( x | ( x << 1 ) ) & 0x55555555;
331 y = ( y | ( y << 8 ) ) & 0x00FF00FF;
332 y = ( y | ( y << 4 ) ) & 0x0F0F0F0F;
333 y = ( y | ( y << 2 ) ) & 0x33333333;
334 y = ( y | ( y << 1 ) ) & 0x55555555;
336 return x | ( y << 1 );
345 std::set<VERTEX*> seen;
346 wxLog::EnableLogging();
349 if( !p.next || p.next == &p || seen.find( &p ) != seen.end() )
358 if( aSeen && aSeen->count( aStart ) )
362 aSeen->insert( aStart );
366 wxString msg = wxString::Format(
"Vertices: %d,%d,",
static_cast<int>( aStart->
x ),
367 static_cast<int>( aStart->
y ) );
371 msg += wxString::Format(
"%d,%d,",
static_cast<int>( p->
x ),
static_cast<int>( p->
y ) );
378 }
while( p != aStart );
393 if( !aStart || aStart->
next == aStart->
prev )
428 }
while( p != aStart &&
next && p );
454 wxASSERT( aStart->
next && aStart->
prev );
458 while( p != aStart && p->
next && p->
prev )
524 for(
int i = 0; i < points.
PointCount(); i++ )
529 sum += ( ( p2.
x - p1.
x ) * ( p2.
y + p1.
y ) );
532 VECTOR2I last_pt{ std::numeric_limits<int>::max(), std::numeric_limits<int>::max() };
536 auto addVertex = [&](
int i )
549 for(
int i = points.
PointCount() - 1; i >= 0; i-- )
554 for(
int i = 0; i < points.
PointCount(); i++ )
558 if( tail && ( *tail == *tail->
next ) )
579 wxLogTrace(
TRIANGULATE_TRACE,
"earcutList starting at %p for pass %d", aPoint, pass );
587 int internal_pass = 1;
589 while( aPoint->
prev != aPoint->
next )
594 if(
isEar( aPoint ) )
618 if( *prev != *nextNext &&
intersects( prev, aPoint,
next, nextNext ) &&
623 "Local intersection detected. Merging minor triangle with area %f",
624 area( prev, aPoint, nextNext ) );
643 if( aPoint == stop && aPoint->
prev != aPoint->
next )
654 if( newPoint->
next == newPoint->
prev )
668 if( internal_pass < 4 )
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 ) +
718 return ( prev_sq_len < min_area || next_sq_len < min_area || opp_sq_len < min_area );
739 if(
area( a, b, c ) >= 0 )
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 ) );
749 const int32_t minZ =
zOrder( minTX, minTY );
750 const int32_t maxZ =
zOrder( maxTX, maxTY );
755 while( p && p->
z <= maxZ )
768 while( p && p->
z >= minZ )
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;
794 std::set<std::pair<VERTEX*,double>, VertexComparator> longest;
799 double len = ( p->
x - p->
next->
x ) * ( p->
x - p->
next->
x ) +
801 longest.emplace( p, len );
805 }
while (p != aStart);
807 avg /= longest.size();
810 for(
auto it = longest.begin(); it != longest.end() && it->second > avg; ++it )
819 int divisions = avg / it->second + 2 + pass;
820 double step = 1.0 / divisions;
822 for(
int i = 1; i < divisions; i++ )
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 );
845 if( !start || !start->
next || start->
next == start->
prev
857 std::vector<VERTEX*> overlapPoints;
860 while ( z_pt->
prevZ && *z_pt->
prevZ == *origPoly )
863 overlapPoints.push_back( z_pt );
865 while( z_pt->
nextZ && *z_pt->
nextZ == *origPoly )
868 overlapPoints.push_back( z_pt );
871 if( overlapPoints.size() != 2 || overlapPoints[0]->next == overlapPoints[1]
872 || overlapPoints[0]->prev == overlapPoints[1] )
874 origPoly = origPoly->
next;
878 if( overlapPoints[0]->
area( overlapPoints[1] ) < 0 || overlapPoints[1]->
area( overlapPoints[0] ) < 0 )
881 origPoly = origPoly->
next;
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];
890 overlapPoints[0]->updateList();
891 overlapPoints[1]->updateList();
896 wxLogTrace(
TRIANGULATE_TRACE,
"%s at first overlap split", retval ?
"Success" :
"Failed" );
900 }
while ( origPoly != start );
910 while( marker != origPoly->
prev )
913 if( origPoly->
next && origPoly->
i != marker->
i &&
goodSplit( origPoly, marker ) )
926 marker = marker->
next;
929 origPoly = origPoly->
next;
930 }
while( origPoly != start );
953 bool pos_area = a->
area( b ) > 0 && b->
area( a ) > 0;
955 return no_intersect && local_split && ( same_dir || has_len ) && !a_on_edge && !b_on_edge && pos_area;
964 return ( q->
y - p->
y ) * ( r->
x - q->
x ) - ( q->
x - p->
x ) * ( r->
y - q->
y );
968 constexpr int sign(
double aVal )
const
970 return ( aVal > 0 ) - ( aVal < 0 );
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 );
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 ) );
996 if( sign1 != sign2 && sign3 != sign4 )
1028 if( p->
i == a->
i || p->
i == b->
i || q->
i == a->
i || q->
i == b->
i )
1061 bool inside =
false;
1062 double px = ( a->
x + b->
x ) / 2;
1063 double py = ( a->
y + b->
y ) / 2;
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 ) )
static const ADVANCED_CFG & GetCfg()
Get the singleton instance's config, which is shared by all consumers.
size_type GetHeight() const
size_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.
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.
size_t m_vertices_original_size
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
size_t GetVertexCount() 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).
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
VECTOR2< double > VECTOR2D