001    //$HeadURL: svn+ssh://jwilden@svn.wald.intevation.org/deegree/base/branches/2.5_testing/src/org/deegree/processing/raster/interpolation/InverseDistanceToPower.java $
002    /*----------------------------------------------------------------------------
003     This file is part of deegree, http://deegree.org/
004     Copyright (C) 2001-2009 by:
005       Department of Geography, University of Bonn
006     and
007       lat/lon GmbH
008    
009     This library is free software; you can redistribute it and/or modify it under
010     the terms of the GNU Lesser General Public License as published by the Free
011     Software Foundation; either version 2.1 of the License, or (at your option)
012     any later version.
013     This library is distributed in the hope that it will be useful, but WITHOUT
014     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
015     FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
016     details.
017     You should have received a copy of the GNU Lesser General Public License
018     along with this library; if not, write to the Free Software Foundation, Inc.,
019     59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
020    
021     Contact information:
022    
023     lat/lon GmbH
024     Aennchenstr. 19, 53177 Bonn
025     Germany
026     http://lat-lon.de/
027    
028     Department of Geography, University of Bonn
029     Prof. Dr. Klaus Greve
030     Postfach 1147, 53001 Bonn
031     Germany
032     http://www.geographie.uni-bonn.de/deegree/
033    
034     e-mail: info@deegree.org
035    ----------------------------------------------------------------------------*/
036    package org.deegree.processing.raster.interpolation;
037    
038    import java.util.ArrayList;
039    import java.util.Collections;
040    import java.util.List;
041    
042    import org.deegree.datatypes.values.Interval;
043    import org.deegree.datatypes.values.Values;
044    import org.deegree.io.quadtree.IndexException;
045    import org.deegree.io.quadtree.Quadtree;
046    import org.deegree.model.spatialschema.Envelope;
047    import org.deegree.model.spatialschema.GeometryFactory;
048    
049    /**
050     * Class for interpolating a set of data tuples (x, y, value) onto a grid using Inverse Distance to
051     * Power algorithm
052     *
053     * @author <a href="mailto:poth@lat-lon.de">Andreas Poth</a>
054     * @author last edited by: $Author: mschneider $
055     *
056     * @version $Revision: 18195 $, $Date: 2009-06-18 17:55:39 +0200 (Do, 18 Jun 2009) $
057     */
058    public class InverseDistanceToPower extends Interpolation {
059    
060        private double power = 2;
061    
062        /**
063         *
064         * @param data
065         * @param power
066         */
067        public InverseDistanceToPower( Quadtree<?> data, double power ) {
068            super( data );
069            this.power = power;
070        }
071    
072        /**
073         *
074         * @param data
075         * @param ignoreValues
076         * @param power
077         */
078        public InverseDistanceToPower( Quadtree<?> data, Values ignoreValues, double power ) {
079            super( data, ignoreValues );
080            this.power = power;
081        }
082    
083        /**
084         *
085         * @param data
086         * @param ignoreValues
087         * @param searchRadius1
088         * @param searchRadius2
089         * @param searchRadiusAngle
090         * @param minData
091         * @param maxData
092         * @param noValue
093         * @param autoincreaseSearchRadius1
094         * @param autoincreaseSearchRadius2
095         * @param power
096         */
097        public InverseDistanceToPower( Quadtree<?> data, Values ignoreValues, double searchRadius1, double searchRadius2,
098                                       double searchRadiusAngle, int minData, int maxData, double noValue,
099                                       double autoincreaseSearchRadius1, double autoincreaseSearchRadius2, double power ) {
100            super( data, ignoreValues, searchRadius1, searchRadius2, searchRadiusAngle, minData, maxData, noValue,
101                   autoincreaseSearchRadius1, autoincreaseSearchRadius2 );
102            this.power = power;
103        }
104    
105        /**
106         * calculates the interpolated value for a position defined by x and y
107         *
108         * @param x
109         * @param y
110         * @return the interpolated value
111         * @throws InterpolationException
112         */
113        @Override
114        public double calcInterpolatedValue( double x, double y, double searchRadius1, double searchRadius2 )
115                                throws InterpolationException {
116            double tmpSR1 = searchRadius1;
117            double tmpSR2 = searchRadius2;
118    
119            try {
120                Envelope searchRadius = GeometryFactory.createEnvelope( x - tmpSR1, y - tmpSR2, x + tmpSR1, y + tmpSR2,
121                                                                        null );
122                List<?> foundValues = data.query( searchRadius );
123    
124                List<DataTuple> values = new ArrayList<DataTuple>();
125                for ( Object obj : foundValues ) {
126                    DataTuple tuple = (DataTuple) obj;
127    
128                    boolean ignore = false;
129    
130                    if ( ignoreValues != null && ignoreValues.getInterval().length > 0 ) {
131                        for ( Interval interval : ignoreValues.getInterval() ) {
132                            double min = Double.parseDouble( interval.getMin().getValue() );
133                            double max = Double.parseDouble( interval.getMax().getValue() );
134                            if ( tuple.value > min && tuple.value < max ) {
135                                ignore = true;
136                            }
137                        }
138                    }
139    
140                    if ( !ignore ) {
141                        double dx = Math.abs( tuple.x - x );
142                        double dy = Math.abs( tuple.y - y );
143                        /*
144                         * if ( dx == 0 && dy == 0 ) { // System.out.println( "Call with already
145                         * existing value!" ); return tuple.value; }
146                         */
147                        double dist = Math.sqrt( dx * dx + dy * dy );
148                        double weight = Math.pow( dist, power );
149                        values.add( new DataTuple( dist, tuple.value, weight ) );
150                    }
151                }
152    
153                if ( values.size() < minData ) {
154                    if ( autoincreaseSearchRadius1 == 0 && autoincreaseSearchRadius2 == 0 ) {
155                        return noValue;
156                    }
157    
158                    tmpSR1 += autoincreaseSearchRadius1;
159                    tmpSR2 += autoincreaseSearchRadius2;
160                    // System.out.print( " Increasing the search radius to " + tmpSR1 + " and " + tmpSR2
161                    // +"\r" );
162                    return calcInterpolatedValue( x, y, tmpSR1, tmpSR2 );
163                }
164    
165                if ( values.size() > maxData ) {
166                    Collections.sort( values );
167                    values = values.subList( 0, maxData );
168                }
169    
170                double valueSum = 0;
171    
172                double weightSum = 0;
173    
174                for ( Object obj : values ) {
175                    // in the data tuple, x is interpreted as the distance, y is the value and
176                    // "value" is the weight
177                    DataTuple tuple = (DataTuple) obj;
178                    valueSum += ( tuple.y / tuple.value );
179                    weightSum += ( 1 / tuple.value );
180                }
181    
182                double result = ( valueSum / weightSum );
183    
184                if ( Double.isInfinite( result ) ) {
185                    return noValue;
186                }
187    
188                if ( Double.isNaN( result ) ) {
189                    return noValue;
190                }
191    
192                return result;
193            } catch ( IndexException e ) {
194                throw new InterpolationException( e );
195            }
196        }
197    }