Package org.tinfour.interpolation

Class NaturalNeighborInterpolator

  • All Implemented Interfaces:
    IProcessUsingTin, IInterpolatorOverTin
    public class NaturalNeighborInterpolator
extends Object
implements IInterpolatorOverTin
    Provides interpolations based on Sibson's Natural Neighbor Interpolation method. See Sibson, Robin, "A Brief Description of Natural Neighbor Interpolation". Interpreting Multivariate Data. Ed. Barnett, Vic. England. John Wiley & Sons (1981).

    • Constructor Detail

      • NaturalNeighborInterpolator

        public NaturalNeighborInterpolator​(IIncrementalTin tin)
        Construct an interpolator that operates on the specified TIN. Because the interpolator will access the TIN on a read-only basis, it is possible to construct multiple instances of this class and allow them to operate in parallel threads.

        Important Synchronization Issue

        To improve performance, the classes in this package frequently maintain state-data about the TIN that can be reused for query to query. They also avoid run-time overhead by not implementing any kind of Java synchronization or or even the concurrent-modification testing provided by the Java collection classes. If an application modifies the TIN, instances of this class will not be aware of the change. In such cases, interpolation methods may fail by either throwing an exception or, worse, returning an incorrect value. The onus is on the calling application to manage the use of this class and to ensure that no modifications are made to the TIN between interpolation operations. If the TIN is modified, the internal state data for this class must be reset using a call to resetForChangeToTIN().

        Parameters:
        tin - a valid instance of an incremental TIN.

    • Method Detail

      • resetForChangeToTin

        public void resetForChangeToTin()
        Used by an application to reset the state data within the interpolator when the content of the TIN may have changed. Resetting the state data unnecessarily may result in a minor performance reduction when processing a large number of interpolations, but is otherwise harmless.
        Specified by:
        resetForChangeToTin in interface IProcessUsingTin

      • interpolate

        public double interpolate​(double x,
                          double y,
                          IVertexValuator valuator)
        Perform interpolation using Sibson's C0 method. This interpolation develops a continuous surface, and provides first derivative continuity at all except the input vertex points.

        The domain of the interpolator is limited to the interior of the convex hull. Methods for extending to the edge of the TIN or beyond are being investigated.

        The interpolation is treated as undefined at points that lie directly on a constrained edge.

        Specified by:
        interpolate in interface IInterpolatorOverTin
        Parameters:
        x - the x coordinate for the interpolation point
        y - the y coordinate for the interpolation point
        valuator - a valid valuator for interpreting the z value of each vertex or a null value to use the default.
        Returns:
        if the interpolation is successful, a valid floating point value; otherwise, a Double.NaN.

      • getBarycentricCoordinateDeviation

        public double getBarycentricCoordinateDeviation()
        Gets the deviation of the computed equivalent of the input query (x,y) coordinates based on barycentric coordinates. As a byproduct, Sibson's method can be used to compute the coordinates of the query point by combining the normalized interpolating weights with the coordinates of the vertices. The normalized weights are, in fact, Barycentric Coordinates for the query point. While the computed equivalent should be an exact match for the query point, errors in implementation or numeric errors due to float-point precision limitations would result in a deviation. Thus, this method provides a diagnostic on the most recent interpolation. A large non-zero value would indicate a potential implementation problem. A consistently small value would be indicative of a successful implementation. At this time, tests on a large number of input data sets have always produced small deviation values.
        Returns:
        a positive value, ideally zero but usually a small number slightly larger than that.

      • getBowyerWatsonEnvelope

        public List<IQuadEdge> getBowyerWatsonEnvelope​(double x,
                                               double y)
        Gets a list of edges for the polygonal cavity that would be created as part of the Bowyer-Watson insertion algorithm. If the list is empty, it indicates that TIN was not bootstrapped or the query was to the exterior of the TIN.

        The vertices associated with the resulting edge list are the natural neighbors of the point given by the input coordinates.

        Parameters:
        x - A Cartesian coordinate in the coordinate system used for the TIN
        y - A Cartesian coordinate in the coordinate system used for the TIN
        Returns:
        a valid, potentially empty, list.

      • getMethod

        public String getMethod()
        Description copied from interface: IInterpolatorOverTin
        Gets a string describing the interpolation method that can be used for labeling graphs and printouts. Because this string may be used as a column header in a table, its length should be kept short.
        Specified by:
        getMethod in interface IInterpolatorOverTin
        Returns:
        A valid string

      • isSurfaceNormalSupported

        public boolean isSurfaceNormalSupported()
        Description copied from interface: IInterpolatorOverTin
        Indicates whether the interpolation class supports the computation of surface normals through the getUnitNormal() method.
        Specified by:
        isSurfaceNormalSupported in interface IInterpolatorOverTin
        Returns:
        true if the class implements the ability to compute surface normals; otherwise, false.

      • getSurfaceNormal

        public double[] getSurfaceNormal()
        Not implemented at this time. Gets the unit normal to the surface at the position of the most recent interpolation. The unit normal is computed based on the partial derivatives of the surface polynomial evaluated at the coordinates of the query point. Note that this method assumes that the vertical and horizontal coordinates of the input sample points are isotropic.
        Specified by:
        getSurfaceNormal in interface IInterpolatorOverTin
        Returns:
        if defined, a valid array of dimension 3 giving the x, y, and z components of the unit normal, respectively; otherwise, a zero-sized array.

      • getSibsonCoordinates

        public double[] getSibsonCoordinates​(List<IQuadEdge> polygon,
                                     double x,
                                     double y)
        Given a reference point enclosed by a polygon defining its natural neighbors, computes an array of Sibson's local coordinates giving the computed weighting factors for the vertices that comprise the polygon. Sibson coordinates are often represented using the Greek letter lambda. The coordinate are normalized so that their sum is 1.0.

        This method works only if the input polygon represents the set of natural neighbors of the reference point given in counterclockwise order. This polygon will be a simple, non-self-intersecting loop. Other polygons will not necessarily produce correct results.

        Using Sibson's coordinates as a self-test for this implementation

        Sibson's coordinates are generalized Barycentric coordinates (Bobach, 2009, pg. 7). Consequently, the weighting factors computed using this method should be able to compute the Cartesian coordinates of the reference point to a high degree of accuracy (within the limits of floating-point precision). Thus, the results of this calculation can be used as a figure of merit for any interpolation operation using Sibson coordinates. By backward computing the (x,y) coordinates of the reference point from the (x,y) coordinates of the natural neighbors and their weights, and then comparing the result against the original, this method derives a value that Tinfour calls the "Barycentric deviation". This deviation is stored internally to instances of this class and may be fetched after a calculation by calling the getBarycentricDeviation() method. If the interpolation logic works well, the deviation would be zero or close to zero, resulting a favorable figure of merit.

        If the point is not inside the polygon or if the polygon is not a proper set of natural neighbors, the results are undefined and the method may return a null array or a meaningless result. If the point is on the perimeter of the polygon, this method will return a null array.

        For a rigorous discussion of the equivalence of Sibson's local coordinates and Barycentric coordinates, see Bobach, T (2009). Natural Neighbor Interpolation -- Critical Assessment and New Contributions (Doctoral dissertation).

        Parameters:
        polygon - list of edges defining a non-self-intersecting, potentially non-convex polygon composed of natural neighbor vertices,
        x - the x coordinate of the reference point
        y - the y coordinate of the reference point
        Returns:
        if successful, a valid array; otherwise a null.

      • printDiagnostics

        public void printDiagnostics​(PrintStream ps)
        Prints a set of diagnostic information describing the operations used to interpolate points.
        Parameters:
        ps - a valid print stream such as System.out.

      • clearDiagnostics

        public void clearDiagnostics()
        Clears any diagnostic information accumulated during processing.

      • getNaturalNeighborElements

        public NaturalNeighborElements getNaturalNeighborElements​(double x,
                                                          double y)
        Gets an instance containing the natural neighbors and associated Sibson coordinates for a specified query location.
        Parameters:
        x - the x Cartesian coordinate for the query point
        y - the y Cartesian coordinate for the query point
        Returns:
        a valid instance.