content: // Spatial Index Library
  //
  // Copyright (C) 2002  Navel Ltd.
  //
  // This library is free software; you can redistribute it and/or
  // modify it under the terms of the GNU Lesser General Public
  // License as published by the Free Software Foundation; either
  // version 2.1 of the License, or (at your option) any later version.
  //
  // This library is distributed in the hope that it will be useful,
  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  // Lesser General Public License for more details.
  //
  // You should have received a copy of the GNU Lesser General Public
  // License along with this library; if not, write to the Free Software
  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  //
  // Contact information:
  //  Mailing address:
  //    Marios Hadjieleftheriou
  //    University of California, Riverside
  //    Department of Computer Science
  //    Surge Building, Room 310
  //    Riverside, CA 92521
  //
  //  Email:
  //    marioh@cs.ucr.edu
  
  package sil.spatialindex;
  
  public class Region implements IShape
  {
  	public double[] m_pLow = null;
  	public double[] m_pHigh = null;
  
  	public Region()
  	{
  	}
  
  	public Region(final double[] pLow, final double[] pHigh)
  	{
  		if (pLow.length != pHigh.length) throw new IllegalArgumentException("Region: arguments have different number of dimensions.");
  
  		m_pLow = new double[pLow.length];
  		System.arraycopy(pLow, 0, m_pLow, 0, pLow.length);
  
  		m_pHigh = new double[pHigh.length];
  		System.arraycopy(pHigh, 0, m_pHigh, 0, pHigh.length);
  	}
  
  	public Region(final Point low, final Point high)
  	{
  		if (low.m_pCoords.length != high.m_pCoords.length) throw new IllegalArgumentException("Region: arguments have different number of dimensions.");
  
  		m_pLow = new double[low.m_pCoords.length];
  		System.arraycopy(low.m_pCoords, 0, m_pLow, 0, low.m_pCoords.length);
  		m_pHigh = new double[high.m_pCoords.length];
  		System.arraycopy(high.m_pCoords, 0, m_pHigh, 0, high.m_pCoords.length);
  	}
  
  	public Region(final Region r)
  	{
  		m_pLow = new double[r.m_pLow.length];
  		System.arraycopy(r.m_pLow, 0, m_pLow, 0, r.m_pLow.length);
  		m_pHigh = new double[r.m_pHigh.length];
  		System.arraycopy(r.m_pHigh, 0, m_pHigh, 0, r.m_pHigh.length);
  	}
  
  	public boolean equals(Object o)
  	{
  		if (o instanceof Region)
  		{
  			Region r = (Region) o;
  
  			if (r.m_pLow.length != m_pLow.length) return false;
  
  			for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  			{
  				if (m_pLow[cIndex] < r.m_pLow[cIndex] - SpatialIndex.EPSILON || m_pLow[cIndex] > r.m_pLow[cIndex] + SpatialIndex.EPSILON ||
  						m_pHigh[cIndex] < r.m_pHigh[cIndex] - SpatialIndex.EPSILON || m_pHigh[cIndex] > r.m_pHigh[cIndex] + SpatialIndex.EPSILON)
  						return false;
  			}
  			return true;
  		}
  		return false;
  	}
  
  	//
  	// Cloneable interface
  	//
  
  	public Object clone()
  	{
  		return new Region(m_pLow, m_pHigh);
  	}
  
  	//
  	// IShape interface
  	//
  
  	public boolean intersects(final IShape s)
  	{
  		if (s instanceof Region) return intersects((Region) s);
  
  		if (s instanceof Point) return contains((Point) s);
  
  		throw new IllegalStateException("intersects: Not implemented yet!");
  	}
  
  	public boolean contains(final IShape s)
  	{
  		if (s instanceof Region) return contains((Region) s);
  
  		if (s instanceof Point) return contains((Point) s);
  
  		throw new IllegalStateException("contains: Not implemented yet!");
  	}
  
  	public boolean touches(final IShape s)
  	{
  		if (s instanceof Region) return touches((Region) s);
  
  		if (s instanceof Point) return touches((Point) s);
  
  		throw new IllegalStateException("touches: Not implemented yet!");
  	}
  
  	public double[] getCenter()
  	{
  		double[] pCoords = new double[m_pLow.length];
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			pCoords[cIndex] = (m_pLow[cIndex] + m_pHigh[cIndex]) / 2.0;
  		}
  
  		return pCoords;
  	}
  
  	public long getDimension()
  	{
  		return m_pLow.length;
  	}
  
  	public Region getMBR()
  	{
  		return new Region(m_pLow, m_pHigh);
  	}
  
  	public double getArea()
  	{
  		double area = 1.0;
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			area *= m_pHigh[cIndex] - m_pLow[cIndex];
  		}
  
  		return area;
  	}
  
  	public double getMinimumDistance(final IShape s)
  	{
  		if (s instanceof Region) return getMinimumDistance((Region) s);
  
  		if (s instanceof Point) return getMinimumDistance((Point) s);
  
  		throw new IllegalStateException("getMinimumDistance: Not implemented yet!");
  	}
  
  	public boolean intersects(final Region r)
  	{
  		if (m_pLow.length != r.m_pLow.length) throw new IllegalArgumentException("intersects: Shape has the wrong number of dimensions.");
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if (m_pLow[cIndex] > r.m_pHigh[cIndex] || m_pHigh[cIndex] < r.m_pLow[cIndex]) return false;
  		}
  		return true;
  	}
  
  	public boolean contains(final Region r)
  	{
  		if (m_pLow.length != r.m_pLow.length) throw new IllegalArgumentException("contains: Shape has the wrong number of dimensions.");
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if (m_pLow[cIndex] > r.m_pLow[cIndex] || m_pHigh[cIndex] < r.m_pHigh[cIndex]) return false;
  		}
  		return true;
  	}
  
  	public boolean touches(final Region r)
  	{
  		if (m_pLow.length != r.m_pLow.length) throw new IllegalArgumentException("touches: Shape has the wrong number of dimensions.");
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if ((m_pLow[cIndex] > r.m_pLow[cIndex] - SpatialIndex.EPSILON && m_pLow[cIndex] < r.m_pLow[cIndex] + SpatialIndex.EPSILON) ||
  					(m_pHigh[cIndex] > r.m_pHigh[cIndex] - SpatialIndex.EPSILON && m_pHigh[cIndex] < r.m_pHigh[cIndex] + SpatialIndex.EPSILON))
  					return true;
  		}
  		return false;
  	}
  
  	public double getMinimumDistance(final Region r)
  	{
  		if (m_pLow.length != r.m_pLow.length) throw new IllegalArgumentException("getMinimumDistance: Shape has the wrong number of dimensions.");
  
  		double ret = 0.0;
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
      	double x = 0.0;
  
  			if (r.m_pHigh[cIndex] < m_pLow[cIndex])
  			{
        	x = Math.abs(r.m_pHigh[cIndex] - m_pLow[cIndex]);
      	}
      	else if (m_pHigh[cIndex] < r.m_pLow[cIndex])
      	{
      		x = Math.abs(r.m_pLow[cIndex] - m_pHigh[cIndex]);
      	}
  
      	ret += x * x;
    	}
  
  		return Math.sqrt(ret);
  	}
  
  	public boolean contains(final Point p)
  	{
  		if (m_pLow.length != p.m_pCoords.length) throw new IllegalArgumentException("contains: Shape has the wrong number of dimensions.");
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if (m_pLow[cIndex] > p.m_pCoords[cIndex] || m_pHigh[cIndex] < p.m_pCoords[cIndex]) return false;
  		}
  		return true;
  	}
  
  	public boolean touches(final Point p)
  	{
  		if (m_pLow.length != p.m_pCoords.length) throw new IllegalArgumentException("touches: Shape has the wrong number of dimensions.");
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if ((m_pLow[cIndex] > p.m_pCoords[cIndex] - SpatialIndex.EPSILON && m_pLow[cIndex] < p.m_pCoords[cIndex] + SpatialIndex.EPSILON) ||
  					(m_pHigh[cIndex] > p.m_pCoords[cIndex] - SpatialIndex.EPSILON && m_pHigh[cIndex] < p.m_pCoords[cIndex] + SpatialIndex.EPSILON))
  					return true;
  		}
  		return false;
  	}
  
  	public double getMinimumDistance(final Point p)
  	{
  		if (m_pLow.length != p.m_pCoords.length) throw new IllegalArgumentException("getMinimumDistance: Shape has the wrong number of dimensions.");
  
  		double ret = 0.0;
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if (p.m_pCoords[cIndex] < m_pLow[cIndex])
  			{
  				ret += Math.pow(m_pLow[cIndex] - p.m_pCoords[cIndex], 2.0);
  			}
  			else if (p.m_pCoords[cIndex] > m_pHigh[cIndex])
  			{
  				ret += Math.pow(p.m_pCoords[cIndex] - m_pHigh[cIndex], 2.0);
  			}
  		}
  
  		return Math.sqrt(ret);
  	}
  
  	public double getIntersectingArea(final Region r)
  	{
  		if (m_pLow.length != r.m_pLow.length) throw new IllegalArgumentException("getIntersectingArea: Shape has the wrong number of dimensions.");
  
  		int cIndex;
  
  		// check for intersection.
  		// marioh: avoid function call since this is called billions of times.
  		for (cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			if (m_pLow[cIndex] > r.m_pHigh[cIndex] || m_pHigh[cIndex] < r.m_pLow[cIndex]) return 0.0;
  		}
  
  		double ret = 1.0;
  		double f1, f2;
  
  		for (cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			f1 = Math.max(m_pLow[cIndex], r.m_pLow[cIndex]);
  			f2 = Math.min(m_pHigh[cIndex], r.m_pHigh[cIndex]);
  			ret *= f2 - f1;
  		}
  
  		return ret;
  	}
  
  	public Region combinedRegion(final Region r)
  	{
  		if (m_pLow.length != r.m_pLow.length) throw new IllegalArgumentException("combinedRegion: Shape has the wrong number of dimensions.");
  
  		double[] mn = new double[m_pLow.length];
  		double[] mx = new double[m_pLow.length];
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			mn[cIndex] = Math.min(m_pLow[cIndex], r.m_pLow[cIndex]);
  			mx[cIndex] = Math.max(m_pHigh[cIndex], r.m_pHigh[cIndex]);
  		}
  
  		return new Region(mn, mx);
  	}
  
  	public static Region combinedRegion(Region[] pRegions)
  	{
  		double[] mn = new double[pRegions[0].m_pLow.length];
  		double[] mx = new double[pRegions[0].m_pLow.length];
  
  		for (int cDim = 0; cDim < pRegions[0].m_pLow.length; cDim++)
  		{
  			mn[cDim] = Double.POSITIVE_INFINITY;
  			mx[cDim] = Double.NEGATIVE_INFINITY;
  
  			for (int cIndex = 0; cIndex < pRegions.length; cIndex++)
  			{
  				mn[cDim] = Math.min(mn[cDim], pRegions[cIndex].m_pLow[cDim]);
  				mx[cDim] = Math.max(mx[cDim], pRegions[cIndex].m_pHigh[cDim]);
  			}
  		}
  
  		return new Region(mn, mx);
  	}
  
  	// Modifies the first argument to include the second.
  	public static void combinedRegion(Region pToModify, final Region pConst)
  	{
  		if (pToModify.m_pLow.length != pConst.m_pLow.length) throw new IllegalArgumentException("combineRegion: Shape has the wrong number of dimensions.");
  
  		for (int cIndex = 0; cIndex < pToModify.m_pLow.length; cIndex++)
  		{
  			pToModify.m_pLow[cIndex] = Math.min(pToModify.m_pLow[cIndex], pConst.m_pLow[cIndex]);
  			pToModify.m_pHigh[cIndex] = Math.max(pToModify.m_pHigh[cIndex], pConst.m_pHigh[cIndex]);
  		}
  	}
  
  	// Returns the margin of a region. It is calcuated as the sum of  2^(d-1) * width in each dimension.
  	public double getMargin()
  	{
  		double mul = Math.pow(2.0, ((double) m_pLow.length) - 1.0);
  		double margin = 0.0;
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++)
  		{
  			margin += (m_pHigh[cIndex] - m_pLow[cIndex]) * mul;
  		}
  
  		return margin;
  	}
  
  	public double getLow(int index) throws IndexOutOfBoundsException
  	{
  		if (index >= m_pLow.length) throw new IndexOutOfBoundsException("" + index);
  		return m_pLow[index];
  	}
  
  	public double getHigh(int index) throws IndexOutOfBoundsException
  	{
  		if (index >= m_pLow.length) throw new IndexOutOfBoundsException("" + index);
  		return m_pHigh[index];
  	}
  
  	public String toString()
  	{
  		String s = "";
  
  		for (int cIndex = 0; cIndex < m_pLow.length; cIndex++) s += m_pLow[cIndex] + " ";
  
  		s += ": ";
  
  		for (int cIndex = 0; cIndex < m_pHigh.length; cIndex++) s += m_pHigh[cIndex] + " ";
  
  		return s;
  	}
  }
  