bundles/org.simantics.scenegraph/src/com/infomatiq/jsi/SpatialIndex.java

   1 //   SpatialIndex.java
   2 //   Java Spatial Index Library
   3 //   Copyright (C) 2002-2005 Infomatiq Limited.
   4 //
   5 //  This library is free software; you can redistribute it and/or
   6 //  modify it under the terms of the GNU Lesser General Public
   7 //  License as published by the Free Software Foundation; either
   8 //  version 2.1 of the License, or (at your option) any later version.
   9 //
  10 //  This library is distributed in the hope that it will be useful,
  11 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 //  Lesser General Public License for more details.
  14 //
  15 //  You should have received a copy of the GNU Lesser General Public
  16 //  License along with this library; if not, write to the Free Software
  17 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18
  19 package com.infomatiq.jsi;
  20
  21 import gnu.trove.TIntProcedure;
  22
  23 import java.util.Properties;
  24
  25 /**
  26  * Defines methods that must be implemented by all
  27  * spatial indexes. This includes the RTree and its variants.
  28  *
  29  * @author  aled@sourceforge.net
  30  * @version 1.0b8
  31  */
  32 public interface SpatialIndex {
  33
  34   /**
  35    * Initializes any implementation dependent properties
  36    * of the spatial index. For example, RTree implementations
  37    * will have a NodeSize property.
  38    *
  39    * @param props The set of properties used to initialize the spatial index.
  40    */
  41   public void init(Properties props);
  42
  43   /**
  44    * Adds a new rectangle to the spatial index
  45    *
  46    * @param r  The rectangle to add to the spatial index.
  47    * @param id The ID of the rectangle to add to the spatial index.
  48    *           The result of adding more than one rectangle with
  49    *           the same ID is undefined.
  50    */
  51   public void add(Rectangle r, int id);
  52
  53   /**
  54    * Deletes a rectangle from the spatial index
  55    *
  56    * @param r  The rectangle to delete from the spatial index
  57    * @param id The ID of the rectangle to delete from the spatial
  58    *           index
  59    *
  60    * @return true  if the rectangle was deleted
  61    *         false if the rectangle was not found, or the
  62    *               rectangle was found but with a different ID
  63    */
  64   public boolean delete(Rectangle r, int id);
  65
  66   /**
  67    * Finds the nearest rectangles to the passed rectangle and calls
  68    * v.execute(id) for each one.
  69    *
  70    * If multiple rectangles are equally near, they will
  71    * all be returned.
  72    *
  73    * @param p The point for which this method finds the
  74    * nearest neighbours.
  75    *
  76    * @param v The IntProcedure whose execute() method is is called
  77    * for each nearest neighbour.
  78    *
  79    * @param furthestDistance The furthest distance away from the rectangle
  80    * to search. Rectangles further than this will not be found.
  81    *
  82    * This should be as small as possible to minimise
  83    * the search time.
  84    *
  85    * Use Float.POSITIVE_INFINITY to guarantee that the nearest rectangle is found,
  86    * no matter how far away, although this will slow down the algorithm.
  87    */
  88   public void nearest(Point p, TIntProcedure v, float furthestDistance);
  89
  90   /**
  91    * Finds the N nearest rectangles to the passed rectangle, and calls
  92    * execute(id, distance) on each one, in order of increasing distance.
  93    *
  94    * Note that fewer than N rectangles may be found if fewer entries
  95    * exist within the specified furthest distance, or more if rectangles
  96    * N and N+1 have equal distances.
  97    *
  98    * @param p The point for which this method finds the
  99    * nearest neighbours.
 100    *
 101    * @param v The IntfloatProcedure whose execute() method is is called
 102    * for each nearest neighbour.
 103    *
 104    * @param n The desired number of rectangles to find (but note that
 105    * fewer or more may be returned)
 106    *
 107    * @param distance The furthest distance away from the rectangle
 108    * to search. Rectangles further than this will not be found.
 109    *
 110    * This should be as small as possible to minimise
 111    * the search time.
 112    *
 113    * Use Float.POSITIVE_INFINITY to guarantee that the nearest rectangle is found,
 114    * no matter how far away, although this will slow down the algorithm.
 115    */
 116   public void nearestN(Point p, TIntProcedure v, int n, float distance);
 117
 118   /**
 119    * Same as nearestN, except the found rectangles are not returned
 120    * in sorted order. This will be faster, if sorting is not required
 121    */
 122   public void nearestNUnsorted(Point p, TIntProcedure v, int n, float distance);
 123
 124   /**
 125    * Finds all rectangles that intersect the passed rectangle.
 126    *
 127    * @param  r The rectangle for which this method finds
 128    *           intersecting rectangles.
 129    *
 130    * @param ip The IntProcedure whose execute() method is is called
 131    *           for each intersecting rectangle.
 132    */
 133   public void intersects(Rectangle r, TIntProcedure ip);
 134
 135   /**
 136    * Finds all rectangles contained by the passed rectangle.
 137    *
 138    * @param r The rectangle for which this method finds
 139    *           contained rectangles.
 140    *
 141    * @param ip The procedure whose visit() method is is called
 142    *           for each contained rectangle.
 143    */
 144   public void contains(Rectangle r, TIntProcedure ip);
 145
 146   /**
 147    * Returns the number of entries in the spatial index
 148    */
 149   public int size();
 150
 151
 152   /**
 153    * Returns the bounds of all the entries in the spatial index,
 154    * or null if there are no entries.
 155    */
 156   public Rectangle getBounds();
 157
 158   /**
 159    * Returns a string identifying the type of
 160    * spatial index, and the version number,
 161    * eg "SimpleIndex-0.1"
 162    */
 163   public String getVersion();
 164
 165 }