Package georegression.delaunay

Class DelaunayIncrementalWalk

java.lang.Object

georegression.delaunay.DelaunayIncrementalWalk

All Implemented Interfaces:

VerbosePrint

public class DelaunayIncrementalWalk
extends Object
implements VerbosePrint

Incremental Delaunay triangulation based on [1]. The triangle which contains each point is found by walking through the graph. The points are automatically shuffled to avoid degenerate configurations.

• Triangles corners are in counter-clockwise order.

Citations:

1. L. J. Guibas, D. E. Knuth, M. Sharir, "Randomized incremental construction of Delaunay and Voronoi diagrams" Algorithmica, 7, 1992, 381-413

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	DelaunayIncrementalWalk.CandidateTriangle
protected static class	DelaunayIncrementalWalk.OtherSide

Constructor Summary

Constructors

Constructor	Description
DelaunayIncrementalWalk()

Method Summary

Modifier and Type	Method	Description
protected void	addInitialLargeTriangles()
protected void	checkThenSwapEdge(int triangleID, int side, double px, double py)
protected void	insertPointInTriangle(DelaunayIncrementalWalk.CandidateTriangle candidate, int pointID, double px, double py)
protected void	insertPointOnLine(DelaunayIncrementalWalk.CandidateTriangle candidate, int side, int pointID, double px, double py)
void	process(AccessList<Point2D_F64> points, int size)
protected void	removeInitialLargeTriangles()
void	setRandomSeed(long seed)
void	setVerbose(@Nullable PrintStream out, @Nullable Set<String> configuration)
protected void	shufflePointIndexes(int size)
Mesh2D_F64	toMesh(@Nullable Mesh2D_F64 mesh)
protected void	traverseThenInsert(int pointID)
protected int	triangleOnOtherSide(int triangleID, int side, DelaunayIncrementalWalk.OtherSide results)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

DelaunayIncrementalWalk

public DelaunayIncrementalWalk()

Method Details

setRandomSeed

public void setRandomSeed(long seed)

process

public void process(AccessList<Point2D_F64> points,
 int size)

toMesh

public Mesh2D_F64 toMesh(@Nullable
 @Nullable Mesh2D_F64 mesh)

addInitialLargeTriangles

protected void addInitialLargeTriangles()

removeInitialLargeTriangles

protected void removeInitialLargeTriangles()

shufflePointIndexes

protected void shufflePointIndexes(int size)

traverseThenInsert

protected void traverseThenInsert(int pointID)

insertPointInTriangle

protected void insertPointInTriangle(DelaunayIncrementalWalk.CandidateTriangle candidate,
 int pointID,
 double px,
 double py)

insertPointOnLine

protected void insertPointOnLine(DelaunayIncrementalWalk.CandidateTriangle candidate,
 int side,
 int pointID,
 double px,
 double py)

checkThenSwapEdge

protected void checkThenSwapEdge(int triangleID,
 int side,
 double px,
 double py)

triangleOnOtherSide

protected int triangleOnOtherSide(int triangleID,
 int side,
 DelaunayIncrementalWalk.OtherSide results)

setVerbose

public void setVerbose(@Nullable
 @Nullable PrintStream out,
 @Nullable
 @Nullable Set<String> configuration)

Specified by:

setVerbose in interface VerbosePrint