KiCad PCB EDA Suite
|
#include <polygon_triangulation.h>
Classes | |
struct | Vertex |
Public Member Functions | |
PolygonTriangulation (SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult) | |
bool | TesselatePolygon (const SHAPE_LINE_CHAIN &aPoly) |
Private Member Functions | |
int32_t | zOrder (const double aX, const double aY) const |
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN. More... | |
Vertex * | removeNullTriangles (Vertex *aStart) |
Iterate through the list to remove NULL triangles if they exist. More... | |
Vertex * | createList (const ClipperLib::Path &aPath) |
Take a Clipper path and converts it into a circular, doubly-linked list for triangulation. More... | |
Vertex * | createList (const SHAPE_LINE_CHAIN &points) |
Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list. More... | |
bool | earcutList (Vertex *aPoint, int pass=0) |
Walk through a circular linked list starting at aPoint. More... | |
bool | isEar (Vertex *aEar) const |
Check whether the given vertex is in the middle of an ear. More... | |
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 two separate lists and slice them each independently. More... | |
bool | goodSplit (const Vertex *a, const Vertex *b) const |
Check if a segment joining two vertices lies fully inside the polygon. More... | |
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. More... | |
bool | intersects (const Vertex *p1, const Vertex *q1, const Vertex *p2, const Vertex *q2) const |
Check for intersection between two segments, end points included. More... | |
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 which vertex a is a member. More... | |
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 of vertex a. More... | |
Vertex * | insertVertex (const VECTOR2I &pt, Vertex *last) |
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existing linked list. More... | |
Private Attributes | |
BOX2I | m_bbox |
std::deque< Vertex > | m_vertices |
SHAPE_POLY_SET::TRIANGULATED_POLYGON & | m_result |
Definition at line 59 of file polygon_triangulation.h.
|
inline |
Definition at line 62 of file polygon_triangulation.h.
|
inlineprivate |
Return the twice the signed area of the triangle formed by vertices p, q, and r.
Definition at line 609 of file polygon_triangulation.h.
References PolygonTriangulation::Vertex::x, and PolygonTriangulation::Vertex::y.
Referenced by earcutList(), intersects(), isEar(), locallyInside(), and removeNullTriangles().
|
inlineprivate |
Take a Clipper path and converts it into a circular, doubly-linked list for triangulation.
Definition at line 330 of file polygon_triangulation.h.
References insertVertex(), PolygonTriangulation::Vertex::next, and PolygonTriangulation::Vertex::remove().
Referenced by TesselatePolygon().
|
inlineprivate |
Take a SHAPE_LINE_CHAIN and links each point into a circular, doubly-linked list.
Definition at line 371 of file polygon_triangulation.h.
References SHAPE_LINE_CHAIN::CPoint(), insertVertex(), PolygonTriangulation::Vertex::next, SHAPE_LINE_CHAIN::PointCount(), PolygonTriangulation::Vertex::remove(), VECTOR2< T >::x, and VECTOR2< T >::y.
|
inlineprivate |
Walk through a circular linked list starting at aPoint.
For each point, test to see if the adjacent points form a triangle that is completely enclosed by the remaining polygon (an "ear" sticking off the polygon). If the three points form an ear, we log the ear's location and remove the center point from the linked list.
This function can be called recursively in the case of difficult polygons. In cases where there is an intersection (not technically allowed by KiCad, but could exist in an edited file), we create a single triangle and remove both vertices before attempting to.
Definition at line 413 of file polygon_triangulation.h.
References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddTriangle(), area(), PolygonTriangulation::Vertex::i, intersects(), isEar(), locallyInside(), m_result, next(), PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, PolygonTriangulation::Vertex::remove(), removeNullTriangles(), and splitPolygon().
Referenced by splitPolygon(), and TesselatePolygon().
Check if a segment joining two vertices lies fully inside the polygon.
To do this, we first ensure that the line isn't along the polygon edge. Next, we know that if the line doesn't intersect the polygon, then it is either fully inside or fully outside the polygon. Finally, by checking whether the segment is enclosed by the local triangles, we distinguish between these two cases and no further checks are needed.
Definition at line 598 of file polygon_triangulation.h.
References PolygonTriangulation::Vertex::i, intersectsPolygon(), locallyInside(), PolygonTriangulation::Vertex::next, and PolygonTriangulation::Vertex::prev.
Referenced by splitPolygon().
Create an entry in the vertices lookup and optionally inserts the newly created vertex into an existing linked list.
Definition at line 675 of file polygon_triangulation.h.
References SHAPE_POLY_SET::TRIANGULATED_POLYGON::AddVertex(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::GetVertexCount(), m_result, m_vertices, PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, VECTOR2< T >::x, and VECTOR2< T >::y.
Referenced by createList().
|
inlineprivate |
Check for intersection between two segments, end points included.
Definition at line 619 of file polygon_triangulation.h.
References area().
Referenced by earcutList(), and intersectsPolygon().
|
inlineprivate |
Check whether the segment from vertex a -> vertex b crosses any of the segments of the polygon of which vertex a is a member.
Definition at line 634 of file polygon_triangulation.h.
References PolygonTriangulation::Vertex::i, intersects(), and PolygonTriangulation::Vertex::next.
Referenced by goodSplit().
|
inlineprivate |
Check whether the given vertex is in the middle of an ear.
This works by walking forward and backward in zOrder to the limits of the minimal bounding box formed around the triangle, checking whether any points are located inside the given triangle.
Definition at line 504 of file polygon_triangulation.h.
References area(), PolygonTriangulation::Vertex::inTriangle(), PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::nextZ, PolygonTriangulation::Vertex::prev, PolygonTriangulation::Vertex::prevZ, PolygonTriangulation::Vertex::x, PolygonTriangulation::Vertex::y, PolygonTriangulation::Vertex::z, and zOrder().
Referenced by earcutList().
Check whether the segment from vertex a -> vertex b is inside the polygon around the immediate area of vertex a.
We don't define the exact area over which the segment is inside but it is guaranteed to be inside the polygon immediately adjacent to vertex a.
Definition at line 661 of file polygon_triangulation.h.
References area(), PolygonTriangulation::Vertex::next, and PolygonTriangulation::Vertex::prev.
Referenced by earcutList(), and goodSplit().
Iterate through the list to remove NULL triangles if they exist.
This should only be called as a last resort when tesselation fails as the NULL triangles are inserted as Steiner points to improve the triangulation regularity of polygons
Definition at line 297 of file polygon_triangulation.h.
References area(), PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, and PolygonTriangulation::Vertex::remove().
Referenced by earcutList().
|
inlineprivate |
If we cannot find an ear to slice in the current polygon list, we use this to split the polygon into two separate lists and slice them each independently.
This is assured to generate at least one new ear if the split is successful
Definition at line 560 of file polygon_triangulation.h.
References earcutList(), goodSplit(), PolygonTriangulation::Vertex::i, PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, PolygonTriangulation::Vertex::split(), and PolygonTriangulation::Vertex::updateList().
Referenced by earcutList().
|
inline |
Place the polygon Vertices into a circular linked list and check for lists that have only 0, 1 or 2 elements and therefore cannot be polygons
Definition at line 66 of file polygon_triangulation.h.
References SHAPE_LINE_CHAIN::BBox(), SHAPE_POLY_SET::TRIANGULATED_POLYGON::Clear(), createList(), earcutList(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), m_bbox, m_result, m_vertices, PolygonTriangulation::Vertex::next, PolygonTriangulation::Vertex::prev, and PolygonTriangulation::Vertex::updateList().
Referenced by SHAPE_POLY_SET::CacheTriangulation().
|
inlineprivate |
Calculate the Morton code of the Vertex http://www.graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN.
Definition at line 272 of file polygon_triangulation.h.
References BOX2< Vec >::GetHeight(), BOX2< Vec >::GetWidth(), BOX2< Vec >::GetX(), BOX2< Vec >::GetY(), and m_bbox.
Referenced by isEar(), and PolygonTriangulation::Vertex::updateOrder().
|
private |
Definition at line 698 of file polygon_triangulation.h.
Referenced by TesselatePolygon(), and zOrder().
|
private |
Definition at line 700 of file polygon_triangulation.h.
Referenced by earcutList(), insertVertex(), and TesselatePolygon().
|
private |
Definition at line 699 of file polygon_triangulation.h.
Referenced by insertVertex(), PolygonTriangulation::Vertex::split(), and TesselatePolygon().