jwo.landserf.structure
Class DelaunayTriang

java.lang.Object
  jwo.landserf.structure.DelaunayTriang

All Implemented Interfaces:

Serializable, SpatialModel

public class DelaunayTriang
extends Object
implements Serializable, SpatialModel

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

Version:

2.3, 14th May, 2007.

Author:

Jo Wood.

See Also:

Triangle, Serialized Form

Field Summary

static int

OUTSIDE Indicates that a location is outside the convex hull.

Fields inherited from interface jwo.landserf.structure.SpatialModel

ADJACENT, AREA, CONTOUR, ENCLOSES, INTERSECTION, LINE, MATCHES, MSN, NO_VALUE, OUT_OF_BOUNDS, OVERLAPS, POINT, RASTER_2D, RASTER_3D, SEPARATE, TIN, UNDEFINED, UNION, UNKNOWN, UNKNOWN_MODEL, VECTOR_2D, VECTOR_3D, VOLUME, WITHIN

Constructor Summary

DelaunayTriang(DelaunayTriang triang)
Creates a new triangulation based on the contents of the the given Delaunay triangulation.

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

Method Summary

int	compare(SpatialModel other) Makes a spatial comparison between this object and another.
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	getAttribute(Footprint fp) Reports the attribute of at the given location.
Footprint	getBounds() Returns the 2d bounding rectangle of this triangulation.
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.
Header	getHeader() Reports the header information associated with this triangulation.
void	getImage(int[] img, int imgWidth) Can be used to get an image representation of this triangulation but does nothing in this case.
float	getInterpolatedHeight(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.
int	getType() Reports the type of spatial object which is always SpatialModel.TIN.
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	setBounds(Footprint footprint) Sets the bounding rectangle of this triangulation.
void	setVersion(float version) Sets the version number of this object.
SpatialModel	subset(Footprint clipRect) Creates a subset of this TIN by clipping to the given rectangle.
void	swapTest(Edge e11) Swaps candidate edges and retriangulates 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.

DelaunayTriang

public DelaunayTriang(DelaunayTriang triang)

Creates a new triangulation based on the contents of the the given Delaunay triangulation.

Parameters:

triang - Triangulation to copy.

Method Detail

compare

public int compare(SpatialModel other)

Makes a spatial comparison between this object and another. Assumes that both objects are rectangular.

Specified by:

compare in interface SpatialModel

Parameters:

other - Spatial model with which to make a comparison.

Returns:

One of five topological relations (WITHIN, MATCHES, OVERLAPS, ENCLOSES, or SEPARATE).

setBounds

public void setBounds(Footprint footprint)

Sets the bounding rectangle of this triangulation.

Specified by:

setBounds in interface SpatialModel

Parameters:

footprint - Spatial footprint to assign to this triangulation.

getBounds

public Footprint getBounds()

Returns the 2d bounding rectangle of this triangulation.

Specified by:

getBounds in interface SpatialModel

Returns:

Minimum enclosing rectangle of object.

getAttribute

public float getAttribute(Footprint fp)

Reports the attribute of at the given location. Uses the point value of the footprint's origin as the location to query. Performs a planar interpolation across a triangle facet.

Specified by:

getAttribute in interface SpatialModel

Parameters:

fp - Location to query.

Returns:

Attribute at given location. or OUT_OF_BOUNDS if outside convex hull.

getHeader

public Header getHeader()

Reports the header information associated with this triangulation.

Specified by:

getHeader in interface SpatialModel

Returns:

Header information (title only in this case).

getImage

public void getImage(int[] img,
                     int imgWidth)

Can be used to get an image representation of this triangulation but does nothing in this case. To draw the triangulation create a VectorMap that wraps this class.

Specified by:

getImage in interface SpatialModel

Parameters:

img - Image array to store colours.

imgWidth - Image width.

getType

public int getType()

Reports the type of spatial object which is always SpatialModel.TIN.

Specified by:

getType in interface SpatialModel

Returns:

Identifier corresponding to a TIN.

subset

public SpatialModel subset(Footprint clipRect)

Creates a subset of this TIN by clipping to the given rectangle. The footprint provided must be a rectangle, or no clipping will take place. Note that the new clipped TIN will have the same spatial units as the original, but will be translated to the origin (0,0).

Specified by:

subset in interface SpatialModel

Parameters:

clipRect - Clipping rectangle.

Returns:

TIN made up of vertices within the clipped bounds.

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-coordinate of the new point.

py - y-coordinate 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-coordinate of the new point.

py - y-coordinate of the new point.

pz - z-coordinate 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-coordinate of the point to delete.

py - y-coordinate 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 retriangulates 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.

getInterpolatedHeight

public float getInterpolatedHeight(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 old pre 2.0 LandSerf TIN files are to be loaded since the triangulation 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 minimum x, minimum y, maximum x and maximum y coordinates.

getNodesX

public float[] getNodesX()

Returns the x coordinates of the nodes of the triangulation. Note that coordinate is relative to the SW corner of the triangulation. To find absolute geographic location, add to origin of vector map.

Returns:

An array of x coordinates.

getNodesY

public float[] getNodesY()

Returns the y coordinates of the nodes of the triangulation. Note that coordinate is relative to the SW corner of the triangulation. To find absolute geographic location, add to origin of vector map.

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. Note that coordinate is relative to the SW corner of the triangulation. To find absolute geographic location, add to origin of vector map.

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. Note that coordinate is relative to the SW corner of the triangulation. To find absolute geographic location, add to origin of vector map.

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. Note that coordinate is relative to the SW corner of the triangulation. To find absolute geographic location, add to origin of vector map. 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. Note that coordinate is relative to the SW corner of the triangulation. To find absolute geographic location, add to origin of vector map. 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.