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

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