KiCad PCB EDA Suite
p2t::Sweep Class Reference

#include <sweep.h>

Public Member Functions

void Triangulate (SweepContext &tcx)
 Triangulate. More...
 
 ~Sweep ()
 Destructor - clean up memory. More...
 

Private Member Functions

void SweepPoints (SweepContext &tcx)
 Start sweeping the Y-sorted point set from bottom to top. More...
 
NodePointEvent (SweepContext &tcx, Point &point)
 Find closes node to the left of the new point and create a new triangle. More...
 
void EdgeEvent (SweepContext &tcx, Edge *edge, Node *node)
 
void EdgeEvent (SweepContext &tcx, Point &ep, Point &eq, Triangle *triangle, Point &point)
 
NodeNewFrontTriangle (SweepContext &tcx, Point &point, Node &node)
 Creates a new front triangle and legalize it. More...
 
void Fill (SweepContext &tcx, Node &node)
 Adds a triangle to the advancing front to fill a hole. More...
 
bool Legalize (SweepContext &tcx, Triangle &t)
 Returns true if triangle was legalized. More...
 
bool Incircle (Point &pa, Point &pb, Point &pc, Point &pd)
 Requirement:
More...
 
void RotateTrianglePair (Triangle &t, Point &p, Triangle &ot, Point &op)
 Rotates a triangle pair one vertex CW. More...
 
void FillAdvancingFront (SweepContext &tcx, Node &n)
 Fills holes in the Advancing Front. More...
 
bool LargeHole_DontFill (Node *node)
 
bool AngleExceeds90Degrees (Point *origin, Point *pa, Point *pb)
 
bool AngleExceedsPlus90DegreesOrIsNegative (Point *origin, Point *pa, Point *pb)
 
double Angle (Point &origin, Point &pa, Point &pb)
 
double HoleAngle (Node &node)
 
double BasinAngle (Node &node)
 The basin angle is decided against the horizontal line [1,0]. More...
 
void FillBasin (SweepContext &tcx, Node &node)
 Fills a basin that has formed on the Advancing Front to the right of given node. More...
 
void FillBasinReq (SweepContext &tcx, Node *node)
 Recursive algorithm to fill a Basin with triangles. More...
 
bool IsShallow (SweepContext &tcx, Node &node)
 
bool IsEdgeSideOfTriangle (Triangle &triangle, Point &ep, Point &eq)
 
void FillEdgeEvent (SweepContext &tcx, Edge *edge, Node *node)
 
void FillRightAboveEdgeEvent (SweepContext &tcx, Edge *edge, Node *node)
 
void FillRightBelowEdgeEvent (SweepContext &tcx, Edge *edge, Node &node)
 
void FillRightConcaveEdgeEvent (SweepContext &tcx, Edge *edge, Node &node)
 
void FillRightConvexEdgeEvent (SweepContext &tcx, Edge *edge, Node &node)
 
void FillLeftAboveEdgeEvent (SweepContext &tcx, Edge *edge, Node *node)
 
void FillLeftBelowEdgeEvent (SweepContext &tcx, Edge *edge, Node &node)
 
void FillLeftConcaveEdgeEvent (SweepContext &tcx, Edge *edge, Node &node)
 
void FillLeftConvexEdgeEvent (SweepContext &tcx, Edge *edge, Node &node)
 
void FlipEdgeEvent (SweepContext &tcx, Point &ep, Point &eq, Triangle *t, Point &p)
 
TriangleNextFlipTriangle (SweepContext &tcx, int o, Triangle &t, Triangle &ot, Point &p, Point &op)
 After a flip we have two triangles and know that only one will still be intersecting the edge. More...
 
PointNextFlipPoint (Point &ep, Point &eq, Triangle &ot, Point &op)
 When we need to traverse from one triangle to the next we need the point in current triangle that is the opposite point to the next triangle. More...
 
void FlipScanEdgeEvent (SweepContext &tcx, Point &ep, Point &eq, Triangle &flip_triangle, Triangle &t, Point &p)
 Scan part of the FlipScan algorithm
When a triangle pair isn't flippable we will scan for the next point that is inside the flip triangle scan area. More...
 
void FinalizationPolygon (SweepContext &tcx)
 

Private Attributes

std::vector< Node * > nodes_
 

Detailed Description

Definition at line 52 of file sweep.h.

Constructor & Destructor Documentation

p2t::Sweep::~Sweep ( )

Destructor - clean up memory.

Member Function Documentation

double p2t::Sweep::Angle ( Point origin,
Point pa,
Point pb 
)
private
bool p2t::Sweep::AngleExceeds90Degrees ( Point origin,
Point pa,
Point pb 
)
private
bool p2t::Sweep::AngleExceedsPlus90DegreesOrIsNegative ( Point origin,
Point pa,
Point pb 
)
private
double p2t::Sweep::BasinAngle ( Node node)
private

The basin angle is decided against the horizontal line [1,0].

void p2t::Sweep::EdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
Parameters
tcx
edge
node
void p2t::Sweep::EdgeEvent ( SweepContext tcx,
Point ep,
Point eq,
Triangle triangle,
Point point 
)
private
void p2t::Sweep::Fill ( SweepContext tcx,
Node node 
)
private

Adds a triangle to the advancing front to fill a hole.

Parameters
tcx
node- middle node, that is the bottom of the hole
void p2t::Sweep::FillAdvancingFront ( SweepContext tcx,
Node n 
)
private

Fills holes in the Advancing Front.

Parameters
tcx
n
void p2t::Sweep::FillBasin ( SweepContext tcx,
Node node 
)
private

Fills a basin that has formed on the Advancing Front to the right of given node.


First we decide a left,bottom and right node that forms the boundaries of the basin. Then we do a reqursive fill.

Parameters
tcx
node- starting node, this or next node will be left node
void p2t::Sweep::FillBasinReq ( SweepContext tcx,
Node node 
)
private

Recursive algorithm to fill a Basin with triangles.

Parameters
tcx
node- bottom_node
cnt- counter used to alternate on even and odd numbers
void p2t::Sweep::FillEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillLeftAboveEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillLeftBelowEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillLeftConcaveEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillLeftConvexEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillRightAboveEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillRightBelowEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillRightConcaveEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FillRightConvexEdgeEvent ( SweepContext tcx,
Edge edge,
Node node 
)
private
void p2t::Sweep::FinalizationPolygon ( SweepContext tcx)
private
void p2t::Sweep::FlipEdgeEvent ( SweepContext tcx,
Point ep,
Point eq,
Triangle t,
Point p 
)
private
void p2t::Sweep::FlipScanEdgeEvent ( SweepContext tcx,
Point ep,
Point eq,
Triangle flip_triangle,
Triangle t,
Point p 
)
private

Scan part of the FlipScan algorithm
When a triangle pair isn't flippable we will scan for the next point that is inside the flip triangle scan area.

When found we generate a new flipEdgeEvent

Parameters
tcx
ep- last point on the edge we are traversing
eq- first point on the edge we are traversing
flipTriangle- the current triangle sharing the point eq with edge
t
p
double p2t::Sweep::HoleAngle ( Node node)
private
Parameters
node- middle node
Returns
the angle between 3 front nodes
bool p2t::Sweep::Incircle ( Point pa,
Point pb,
Point pc,
Point pd 
)
private

Requirement:

  1. a,b and c form a triangle.
  2. a and d is know to be on opposite side of bc
                   a
                   +
                  / \
                 /   \
               b/     +-------+ /    d    \
             /           \
    
    Fact: d has to be in area B to have a chance to be inside the circle formed by a,b and c
    d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW
    This preknowledge gives us a way to optimize the incircle test
    Parameters
    a- triangle point, opposite d
    b- triangle point
    c- triangle point
    d- point opposite a
    Returns
    true if d is inside circle, false if on circle edge
bool p2t::Sweep::IsEdgeSideOfTriangle ( Triangle triangle,
Point ep,
Point eq 
)
private
bool p2t::Sweep::IsShallow ( SweepContext tcx,
Node node 
)
private
bool p2t::Sweep::LargeHole_DontFill ( Node node)
private
bool p2t::Sweep::Legalize ( SweepContext tcx,
Triangle t 
)
private

Returns true if triangle was legalized.

Node& p2t::Sweep::NewFrontTriangle ( SweepContext tcx,
Point point,
Node node 
)
private

Creates a new front triangle and legalize it.

Parameters
tcx
point
node
Returns
Point& p2t::Sweep::NextFlipPoint ( Point ep,
Point eq,
Triangle ot,
Point op 
)
private

When we need to traverse from one triangle to the next we need the point in current triangle that is the opposite point to the next triangle.

Parameters
ep
eq
ot
op
Returns
Triangle& p2t::Sweep::NextFlipTriangle ( SweepContext tcx,
int  o,
Triangle t,
Triangle ot,
Point p,
Point op 
)
private

After a flip we have two triangles and know that only one will still be intersecting the edge.

So decide which to contiune with and legalize the other

Parameters
tcx
o- should be the result of an orient2d( eq, op, ep )
t- triangle 1
ot- triangle 2
p- a point shared by both triangles
op- another point shared by both triangles
Returns
returns the triangle still intersecting the edge
Node& p2t::Sweep::PointEvent ( SweepContext tcx,
Point point 
)
private

Find closes node to the left of the new point and create a new triangle.

If needed new holes and basins will be filled to.

Parameters
tcx
point
Returns
void p2t::Sweep::RotateTrianglePair ( Triangle t,
Point p,
Triangle ot,
Point op 
)
private

Rotates a triangle pair one vertex CW.

       n2                    n2
  P +--—+             P +--—+
    | t  /|               |\  t |
    |   / |               | \   |
  n1|  /  |n3           n1|  \  |n3
    | /   |    after CW   |   \ |
    |/ oT |               | oT |
    +--—+ oP            +--—+
       n4                    n4
 
void p2t::Sweep::SweepPoints ( SweepContext tcx)
private

Start sweeping the Y-sorted point set from bottom to top.

Parameters
tcx
void p2t::Sweep::Triangulate ( SweepContext tcx)

Triangulate.

Parameters
tcx

Member Data Documentation

std::vector<Node*> p2t::Sweep::nodes_
private

Definition at line 279 of file sweep.h.


The documentation for this class was generated from the following file: