Package org.tinfour.semivirtual

Class SemiVirtualStochasticLawsonsWalk

java.lang.Object

org.tinfour.semivirtual.SemiVirtualStochasticLawsonsWalk

public class SemiVirtualStochasticLawsonsWalk
extends Object

Methods and definitions to perform a stochastic Lawson's walk. The walk uses randomization to prevent getting trapped in infinite loops in the case of imperfections in Delaunay triangulations.

A good review of walk algorithms for point location is provided by Soukal, R.; Málková, Kolingerová (2012) "Walking algorithms for point location in TIN models", Computational Geoscience 16:853-869.

The randomization in this class uses a custom implementation of the XORShift Random Number Generator which was discovered by George Marsaglia in 2003. This method is faster than the java.util.Random class. While it is slower than Java's ThreadLocalRandom, that Java class has the disadvantage that there is no way to set the seed value for the random sequence. For debugging and development purposes, the Tinfour team requires that the behavior of the code be reproduced every time it is run. The sequence produced by ThreadLocalRandom is always different. The exact form used here is taken from http://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.WEC2g7IrJQL The technique used here were studied extensively by Sebastiano Vigna see An experimental exploration of Marsaglia's xorshift generators, scrambled at http://vigna.di.unimi.it/ftp/papers/xorshift.pdf

Constructor Summary

Constructors

Constructor	Description
SemiVirtualStochasticLawsonsWalk()	Constructs an instance with a nominal point spacing of 1.
SemiVirtualStochasticLawsonsWalk(double nominalPointSpacing)	Construct an instance based on the specified nominal point spacing.

Method Summary

Modifier and Type	Method	Description
SemiVirtualEdge	findAnEdgeFromEnclosingTriangle(SemiVirtualEdge startingEdge, double x, double y)	Find an edge from the triangle enclosing the specified coordinates
SemiVirtualEdge	findAnEdgeFromEnclosingTriangleInternal(SemiVirtualEdge edge, double x, double y)	Search the mesh beginning at the specified edge position to find the triangle that contains the specified coordinates.
void	printDiagnostics(PrintStream ps)	Print diagnostic information about the walk behavior to output stream.
void	reset()	Reset the random seed for the stochastic functions to zero.

Methods inherited from class java.lang.Object

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

Constructor Detail

SemiVirtualStochasticLawsonsWalk

public SemiVirtualStochasticLawsonsWalk(double nominalPointSpacing)

Construct an instance based on the specified nominal point spacing.

Parameters:

nominalPointSpacing - a value greater than zero giving an indication of the magnitude of the distances between vertices.

SemiVirtualStochasticLawsonsWalk

public SemiVirtualStochasticLawsonsWalk()

Constructs an instance with a nominal point spacing of 1.

Method Detail

findAnEdgeFromEnclosingTriangle

public SemiVirtualEdge findAnEdgeFromEnclosingTriangle(SemiVirtualEdge startingEdge,
                                                       double x,
                                                       double y)

Find an edge from the triangle enclosing the specified coordinates

Parameters:

startingEdge - a valid edge from the semivirtual incremental TIN to be used as a starting position for the search.

x - a valid Cartesian coordinate

y - a valid Cartesian coordinate

Returns:

an edge (not necessarily the closest one) of a triangle that contains the specified coordinates, or the nearest exterior-side edge if the point lies outside the convex hull of the TIN.

findAnEdgeFromEnclosingTriangleInternal

public SemiVirtualEdge findAnEdgeFromEnclosingTriangleInternal(SemiVirtualEdge edge,
                                                               double x,
                                                               double y)

Search the mesh beginning at the specified edge position to find the triangle that contains the specified coordinates.

The algorithm requires the initial edge to be an interior-side edge of the TIN. If necessary, the initial edge is replaced with its dual in order to ensure that this condition is met before beginning the walk.

Parameters:

edge - the edge giving both the starting point of the search and storing the ultimate destination.

x - the x coordinate of interest

y - the y coordinate of interest

Returns:

an edge (not necessarily the closest one) of a triangle that contains the specified coordinates, or the nearest exterior-side edge if the point lies outside the convex hull of the TIN.

printDiagnostics

public void printDiagnostics(PrintStream ps)

Print diagnostic information about the walk behavior to output stream.

Parameters:

ps - a valid print stream.

reset

public void reset()

Reset the random seed for the stochastic functions to zero.