## 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.2, 6th August, 2003.
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_MODEL, VECTOR_2D, VECTOR_3D, VOLUME, WITHIN

 Constructor Summary 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 triagulation. 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 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

### 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 topologic 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 triagulation.

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-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.

### 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 minx,miny,maxx,maxy 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.

Copyright Jo Wood, 1996-2005, last modified, 11th March, 2005