jwo.landserf.structure
Class DelaunayTriang

java.lang.Object
  |
  +--jwo.landserf.structure.DelaunayTriang

All Implemented Interfaces:

Serializable

public class DelaunayTriang

extends Object

implements Serializable

Creates and stores a Delaunay triangulation. Useful for representing TINs and calculating the Voronoi diagram. Adapted from Zhao and Saalfeld, 1996.

Version:

1.8.0, 30th May, 2000

Author:

Jo Wood.

See Also:

Triangle, Serialized Form

Field Summary

static int

OUTSIDE Indicates that a location is outside the convex hull.

Constructor Summary

DelaunayTriang(int size)
Initialises a triangulation with a given initial size.

Method Summary

void	deletePoint(float px, float py) Deletes the point nearest to the given coordinates and recalculates the trianglulation.
void	expandHull(Node nd) Adds a given node to the convex hull of the triangulation.
void	expandTriang(Edge e, Node nd, int type) Expands the triangle.
Triangle	findTriangle(Edge edge) Finds the triangle that contains the given edge.
Triangle	findTriangle(float px, float py) Finds the triangle that surrounds the given point.
Node	findTriangleNode(Edge edge) Finds the node that makes the triangle with the given edge.
Triangle[]	findTriangles(Edge edge) Finds the triangles that contain the given edge.
float[]	getEdgesX() Returns the x coordinates of the edges of the triangulation.
float[]	getEdgesY() Returns the y coordinates of the edges of the triangulation.
float[]	getEdgesZ() Returns the z coordinates of the edges of the triangulation.
float	getHeight(float px, float py) Interpolates the z value at a given location based on the plane passing though the triangle surrounding this point.
float	getHeight(float px, float py, boolean useQuad) Interpolates the z value at a given location based on the either plane or quadratic surface passing though the triangle surrounding this point.
float[]	getMER() Returns the minimum enclosing rectangle of the last triangles to be affected by the insertion or removal of a new point.
float[]	getNodesX() Returns the x coordinates of the nodes of the triangulation.
float[]	getNodesY() Returns the y coordinates of the nodes of the triangulation.
float[]	getNodesZ() Returns the z coordinates of the nodes of the triangulation.
int	getNumTriangles() Reports the number of triangles stored in the triangulation.
float[]	getTrianglesX() Returns the x coordinates of the triangles that make up the Delaunay triangulation.
float[]	getTrianglesY() Returns the y coordinates of the triangles that make up the Delaunay triangulation.
float[]	getTrianglesZ() Returns the z coordinates of the triangles that make up the Delaunay triangulation.
float	getVersion() Reports the version of the object.
void	insertPoint(float px, float py) Inserts a new 2d point into the network and recalculates the triangulation.
void	insertPoint(float px, float py, float pz) Inserts a new 3d point into the network and recalculates the triangulation.
boolean	isNearNode(float x, float y, float distance) Looks for a node within a given distance of the give point.
Node	nearestNode(float x, float y) Finds the node nearest to the given coordinates.
void	recalculateParams() Recalculates the triangle parameters.
void	resetTriangulation() Resets triangluation by removing all triangles from the network.
int	searchEdge(Edge e, Node nd) Find the active edge associated with given node.
void	setVersion(float version) Sets the version number of this object.
void	swapTest(Edge e11) Swaps candidate edges and retrianglulates if necessary.

Methods inherited from class java.lang.Object

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

Field Detail

OUTSIDE

public static final int OUTSIDE

Indicates that a location is outside the convex hull.

See Also:

Constant Field Values

Constructor Detail

DelaunayTriang

public DelaunayTriang(int size)

Initialises a triangulation with a given initial size.

Parameters:

size - Initial number of triangles in network.

Method Detail

resetTriangulation

public void resetTriangulation()

Resets triangluation by removing all triangles from the network.

insertPoint

public void insertPoint(float px,
                        float py)

Inserts a new 2d point into the network and recalculates the triangulation.

Parameters:

px - x-coord of the new point.

py - y-coord of the new point.

insertPoint

public void insertPoint(float px,
                        float py,
                        float pz)

Inserts a new 3d point into the network and recalculates the triangulation.

Parameters:

px - x-coord of the new point.

py - y-coord of the new point.

pz - z-coord of the new point.

deletePoint

public void deletePoint(float px,
                        float py)

Deletes the point nearest to the given coordinates and recalculates the trianglulation.

Parameters:

px - x-coord of the point to delete.

py - y-coord of the point to delete.

expandTriang

public void expandTriang(Edge e,
                         Node nd,
                         int type)

Expands the triangle.

Parameters:

e - Edge of triangle to expand.

nd - Node to add to the triangle.

type - Type of edge (internal or convex hull).

expandHull

public void expandHull(Node nd)

Adds a given node to the convex hull of the triangulation.

Parameters:

nd - Node to add to the hull.

searchEdge

public int searchEdge(Edge e,
                      Node nd)

Find the active edge associated with given node.

Parameters:

e - Initial edge to search from.

nd - Node to compare.

Returns:

Relationship between node and active edge (Edge.LEFT, Edge.ALIGNED, Edge.RIGHT, or Node.HULL).

See Also:

Edge, Node

swapTest

public void swapTest(Edge e11)

Swaps candidate edges and retrianglulates if necessary.

Parameters:

e11 - Candidate edge to consider.

nearestNode

public Node nearestNode(float x,
                        float y)

Finds the node nearest to the given coordinates.

Parameters:

x - x-coordinate of point.

y - y-coordinate of point.

Returns:

Nearest node to given coordinates.

isNearNode

public boolean isNearNode(float x,
                          float y,
                          float distance)

Looks for a node within a given distance of the give point.

Parameters:

x - x-coordinate of point.

y - y-coordinate of point.

distance - 'Snapping distance' to compare.

Returns:

True if close to existing node.

findTriangle

public Triangle findTriangle(float px,
                             float py)

Finds the triangle that surrounds the given point. Returns null if point not within a triangle.

Parameters:

px - x coordinate of point to query.

py - y coordinate of point to query.

Returns:

Triangle that point lies within.

findTriangle

public Triangle findTriangle(Edge edge)

Finds the triangle that contains the given edge. Supplying the inverse of the edge will cause the method to return the other triangle sharing the edge.

Parameters:

edge - edge to search from. Returns null if less than three nodes present.

Returns:

Triangle associated with the edge.

findTriangles

public Triangle[] findTriangles(Edge edge)

Finds the triangles that contain the given edge. Two triangles returned if edge is internal, 1 if it is part of the hull, or null if less than 3 nodes.

Parameters:

edge - edge to search from.

Returns:

array containing 1 or two triangles.

findTriangleNode

public Node findTriangleNode(Edge edge)

Finds the node that makes the triangle with the given edge. To find both triangle nodes associated with an edge, call this method twice, supplying the inverse of the edge the second time. Returns null if less than three nodes present.

Parameters:

edge - edge to examine.

Returns:

Node that makes up the triangle with the given edge.

getHeight

public float getHeight(float px,
                       float py)

Interpolates the z value at a given location based on the plane passing though the triangle surrounding this point. A height of 0 is returned if the point lies outside the triangulation.

Parameters:

px - x coordinate of the location to interpolate.

py - y coordinate of the location to interpolate.

Returns:

Interpolated height.

getHeight

public float getHeight(float px,
                       float py,
                       boolean useQuad)

Interpolates the z value at a given location based on the either plane or quadratic surface passing though the triangle surrounding this point. A height of 0 is returned if the point lies outside the triangulation. If quadratic interpolation requested, uses quadratic interpolation except where (i) triangle borders convex hull in which case planar interpolation used; (ii) overshoot or undershoot is outside range of local vertices in which case, value is capped to local range.

Parameters:

px - x coordinate of the location to interpolate.

py - y coordinate of the location to interpolate.

useQuad - Quadratic interpolation used if true, otherwise planar.

Returns:

Interpolated height.

recalculateParams

public void recalculateParams()

Recalculates the triangle parameters. This method need only be called if the triangulation has been serialized since the line, plane and circle parameters are not serialized.

getMER

public float[] getMER()

Returns the minimum enclosing rectangle of the last triangles to be affected by the insertion or removal of a new point.

Returns:

Array containing minx,miny,maxx,maxy coordinates.

getNodesX

public float[] getNodesX()

Returns the x coordinates of the nodes of the triangulation.

Returns:

An array of x coordinates.

getNodesY

public float[] getNodesY()

Returns the y coordinates of the nodes of the triangulation.

Returns:

An array of y coordinates.

getNodesZ

public float[] getNodesZ()

Returns the z coordinates of the nodes of the triangulation.

Returns:

An array of y coordinates.

getEdgesX

public float[] getEdgesX()

Returns the x coordinates of the edges of the triangulation. Used primarily for display and output.

Returns:

An array of x coordinates.

getEdgesY

public float[] getEdgesY()

Returns the y coordinates of the edges of the triangulation. Used primarily for display and output.

Returns:

An array of y coordinates.

getEdgesZ

public float[] getEdgesZ()

Returns the z coordinates of the edges of the triangulation. Used primarily for display and output.

Returns:

An array of z coordinates.

getNumTriangles

public int getNumTriangles()

Reports the number of triangles stored in the triangulation.

Returns:

Number of triangles in network.

getTrianglesX

public float[] getTrianglesX()

Returns the x coordinates of the triangles that make up the Delaunay triangulation. Used primarily for display and output.

Returns:

An array of x coordinates.

getTrianglesY

public float[] getTrianglesY()

Returns the y coordinates of the triangles that make up the Delaunay triangulation. Used primarily for display and output.

Returns:

An array of y coordinates.

getTrianglesZ

public float[] getTrianglesZ()

Returns the z coordinates of the triangles that make up the Delaunay triangulation. Used primarily for display and output.

Returns:

An array of z coordinates.

getVersion

public float getVersion()

Reports the version of the object. This can be useful when serialising future (changed) versions of this class.

Returns:

Version number of this object.

setVersion

public void setVersion(float version)

Sets the version number of this object.

Parameters:

version - Version number of this object.