Table of Contents

Class DtSweep

Namespace
Alis.Core.Physic.Common.Decomposition.CDT.Delaunay.Sweep
Assembly
Alis.dll

The dt sweep class

internal static class DtSweep

Inheritance

Inherited Members

Fields

Pi3Div4

The pi

private const double Pi3Div4 = 2.356194490192345

Field Value

double

PiDiv2

The pi

private const double PiDiv2 = 1.5707963267948966

Field Value

double

Methods

Angle(TriangulationPoint, TriangulationPoint, TriangulationPoint)

Angles the origin

private static double Angle(TriangulationPoint origin, TriangulationPoint pa, TriangulationPoint pb)

Parameters

origin TriangulationPoint

The origin

pa TriangulationPoint

The pa

pb TriangulationPoint

The pb

Returns

double

The angle

AngleExceeds90Degrees(TriangulationPoint, TriangulationPoint, TriangulationPoint)

Describes whether angle exceeds 90 degrees

private static bool AngleExceeds90Degrees(TriangulationPoint origin, TriangulationPoint pa, TriangulationPoint pb)

Parameters

origin TriangulationPoint

The origin

pa TriangulationPoint

The pa

pb TriangulationPoint

The pb

Returns

bool

The exceeds 90 degrees

AngleExceedsPlus90DegreesOrIsNegative(TriangulationPoint, TriangulationPoint, TriangulationPoint)

Describes whether angle exceeds plus 90 degrees or is negative

private static bool AngleExceedsPlus90DegreesOrIsNegative(TriangulationPoint origin, TriangulationPoint pa, TriangulationPoint pb)

Parameters

origin TriangulationPoint

The origin

pa TriangulationPoint

The pa

pb TriangulationPoint

The pb

Returns

bool

The exceeds plus 90 degrees or is negative

BasinAngle(AdvancingFrontNode)

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

private static double BasinAngle(AdvancingFrontNode node)

Parameters

node AdvancingFrontNode

Returns

double

EdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Edges the event using the specified tcx

private static void EdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

EdgeEvent(DTSweepContext, TriangulationPoint, TriangulationPoint, DelaunayTriangle, TriangulationPoint)

Edges the event using the specified tcx

private static void EdgeEvent(DTSweepContext tcx, TriangulationPoint ep, TriangulationPoint eq, DelaunayTriangle triangle, TriangulationPoint point)

Parameters

tcx DTSweepContext

The tcx

ep TriangulationPoint

The ep

eq TriangulationPoint

The eq

triangle DelaunayTriangle

The triangle

point TriangulationPoint

The point

Exceptions

PointOnEdgeException

EdgeEvent - Point on constrained edge not supported yet

PointOnEdgeException

EdgeEvent - Point on constrained edge not supported yet

Fill(DTSweepContext, AdvancingFrontNode)

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

private static void Fill(DTSweepContext tcx, AdvancingFrontNode node)

Parameters

tcx DTSweepContext
node AdvancingFrontNode

middle node, that is the bottom of the hole

FillAdvancingFront(DTSweepContext, AdvancingFrontNode)

Fills holes in the Advancing Front

private static void FillAdvancingFront(DTSweepContext tcx, AdvancingFrontNode n)

Parameters

tcx DTSweepContext
n AdvancingFrontNode

FillBasin(DTSweepContext, AdvancingFrontNode)

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.

private static void FillBasin(DTSweepContext tcx, AdvancingFrontNode node)

Parameters

tcx DTSweepContext
node AdvancingFrontNode

starting node, this or next node will be left node

FillBasinReq(DTSweepContext, AdvancingFrontNode)

Recursive algorithm to fill a Basin with triangles

private static void FillBasinReq(DTSweepContext tcx, AdvancingFrontNode node)

Parameters

tcx DTSweepContext
node AdvancingFrontNode

FillEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the edge event using the specified tcx

private static void FillEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillLeftAboveEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the left above edge event using the specified tcx

private static void FillLeftAboveEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillLeftBelowEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the left below edge event using the specified tcx

private static void FillLeftBelowEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillLeftConcaveEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the left concave edge event using the specified tcx

private static void FillLeftConcaveEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillLeftConvexEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the left convex edge event using the specified tcx

private static void FillLeftConvexEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillRightAboveEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the right above edge event using the specified tcx

private static void FillRightAboveEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillRightBelowEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the right below edge event using the specified tcx

private static void FillRightBelowEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillRightConcaveEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the right concave edge event using the specified tcx

private static void FillRightConcaveEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FillRightConvexEdgeEvent(DTSweepContext, DtSweepConstraint, AdvancingFrontNode)

Fills the right convex edge event using the specified tcx

private static void FillRightConvexEdgeEvent(DTSweepContext tcx, DtSweepConstraint edge, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

edge DtSweepConstraint

The edge

node AdvancingFrontNode

The node

FinalizationConvexHull(DTSweepContext)

If this is a Delaunay Triangulation of a pointset we need to fill so the triangle mesh gets a ConvexHull

private static void FinalizationConvexHull(DTSweepContext tcx)

Parameters

tcx DTSweepContext

FinalizationPolygon(DTSweepContext)

Finalizations the polygon using the specified tcx

private static void FinalizationPolygon(DTSweepContext tcx)

Parameters

tcx DTSweepContext

The tcx

FlipEdgeEvent(DTSweepContext, TriangulationPoint, TriangulationPoint, DelaunayTriangle, TriangulationPoint)

Flips the edge event using the specified tcx

private static void FlipEdgeEvent(DTSweepContext tcx, TriangulationPoint ep, TriangulationPoint eq, DelaunayTriangle t, TriangulationPoint p)

Parameters

tcx DTSweepContext

The tcx

ep TriangulationPoint

The ep

eq TriangulationPoint

The eq

t DelaunayTriangle

The

p TriangulationPoint

The

Exceptions

Exception

Intersecting Constraints

InvalidOperationException

[BUG:FIXME] FLIP failed due to missing triangle

FlipScanEdgeEvent(DTSweepContext, TriangulationPoint, TriangulationPoint, DelaunayTriangle, DelaunayTriangle, TriangulationPoint)

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

private static void FlipScanEdgeEvent(DTSweepContext tcx, TriangulationPoint ep, TriangulationPoint eq, DelaunayTriangle flipTriangle, DelaunayTriangle t, TriangulationPoint p)

Parameters

tcx DTSweepContext
ep TriangulationPoint

last point on the edge we are traversing

eq TriangulationPoint

first point on the edge we are traversing

flipTriangle DelaunayTriangle

the current triangle sharing the point eq with edge

t DelaunayTriangle
p TriangulationPoint

HoleAngle(AdvancingFrontNode)

???

private static double HoleAngle(AdvancingFrontNode node)

Parameters

node AdvancingFrontNode

middle node

Returns

double

the angle between 3 front nodes

IsEdgeSideOfTriangle(DelaunayTriangle, TriangulationPoint, TriangulationPoint)

Describes whether is edge side of triangle

private static bool IsEdgeSideOfTriangle(DelaunayTriangle triangle, TriangulationPoint ep, TriangulationPoint eq)

Parameters

triangle DelaunayTriangle

The triangle

ep TriangulationPoint

The ep

eq TriangulationPoint

The eq

Returns

bool

The bool

IsShallow(DTSweepContext, AdvancingFrontNode)

Describes whether is shallow

private static bool IsShallow(DTSweepContext tcx, AdvancingFrontNode node)

Parameters

tcx DTSweepContext

The tcx

node AdvancingFrontNode

The node

Returns

bool

The bool

LargeHole_DontFill(AdvancingFrontNode)

Describes whether large hole dont fill

private static bool LargeHole_DontFill(AdvancingFrontNode node)

Parameters

node AdvancingFrontNode

The node

Returns

bool

The bool

Legalize(DTSweepContext, DelaunayTriangle)

Returns true if triangle was legalized

private static bool Legalize(DTSweepContext tcx, DelaunayTriangle t)

Parameters

tcx DTSweepContext
t DelaunayTriangle

Returns

bool

NewFrontTriangle(DTSweepContext, TriangulationPoint, AdvancingFrontNode)

Creates a new front triangle and legalize it

private static AdvancingFrontNode NewFrontTriangle(DTSweepContext tcx, TriangulationPoint point, AdvancingFrontNode node)

Parameters

tcx DTSweepContext
point TriangulationPoint
node AdvancingFrontNode

Returns

AdvancingFrontNode

NextFlipPoint(TriangulationPoint, TriangulationPoint, DelaunayTriangle, TriangulationPoint)

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.

private static TriangulationPoint NextFlipPoint(TriangulationPoint ep, TriangulationPoint eq, DelaunayTriangle ot, TriangulationPoint op)

Parameters

ep TriangulationPoint
eq TriangulationPoint
ot DelaunayTriangle
op TriangulationPoint

Returns

TriangulationPoint

NextFlipTriangle(DTSweepContext, Orientation, DelaunayTriangle, DelaunayTriangle, TriangulationPoint, TriangulationPoint)

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

private static DelaunayTriangle NextFlipTriangle(DTSweepContext tcx, Orientation o, DelaunayTriangle t, DelaunayTriangle ot, TriangulationPoint p, TriangulationPoint op)

Parameters

tcx DTSweepContext
o Orientation

should be the result of an TriangulationUtil.orient2d( eq, op, ep )

t DelaunayTriangle

triangle 1

ot DelaunayTriangle

triangle 2

p TriangulationPoint

a point shared by both triangles

op TriangulationPoint

another point shared by both triangles

Returns

DelaunayTriangle

returns the triangle still intersecting the edge

PointEvent(DTSweepContext, TriangulationPoint)

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.

private static AdvancingFrontNode PointEvent(DTSweepContext tcx, TriangulationPoint point)

Parameters

tcx DTSweepContext
point TriangulationPoint

Returns

AdvancingFrontNode

RotateTrianglePair(DelaunayTriangle, TriangulationPoint, DelaunayTriangle, TriangulationPoint)

Rotates a triangle pair one vertex CW n2 n2 P +-----+ P +-----+ | t /| |\ t | | / | | \ | n1| / |n3 n1| \ |n3 | / | after CW | \ | |/ oT | | oT | +-----+ oP +-----+ n4 n4

private static void RotateTrianglePair(DelaunayTriangle t, TriangulationPoint p, DelaunayTriangle ot, TriangulationPoint op)

Parameters

t DelaunayTriangle
p TriangulationPoint
ot DelaunayTriangle
op TriangulationPoint

Sweep(DTSweepContext)

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

private static void Sweep(DTSweepContext tcx)

Parameters

tcx DTSweepContext

Triangulate(DTSweepContext)

Triangulate simple polygon with holes

public static void Triangulate(DTSweepContext tcx)

Parameters

tcx DTSweepContext

TurnAdvancingFrontConvex(DTSweepContext, AdvancingFrontNode, AdvancingFrontNode)

We will traverse the entire advancing front and fill it to form a convex hull.

private static void TurnAdvancingFrontConvex(DTSweepContext tcx, AdvancingFrontNode b, AdvancingFrontNode c)

Parameters

tcx DTSweepContext
b AdvancingFrontNode
c AdvancingFrontNode