Doc Classic

Class HPRtree

  1 /*
  2  * Copyright (c) 2019 Martin Davis.
  3  *
  4  * All rights reserved. This program and the accompanying materials
  5  * are made available under the terms of the Eclipse Public License 2.0
  6  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
  7  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
  8  * and the Eclipse Distribution License is available at
  9  *
 10  * http://www.eclipse.org/org/documents/edl-v10.php.
 11  */
 12 package org.locationtech.jts.index.hprtree;
 13  
 14 import java.util.ArrayList;
 15 import java.util.Collections;
 16 import java.util.Comparator;
 17 import java.util.List;
 18  
 19 import org.locationtech.jts.geom.Envelope;
 20 import org.locationtech.jts.geom.GeometryFactory;
 21 import org.locationtech.jts.index.ArrayListVisitor;
 22 import org.locationtech.jts.index.ItemVisitor;
 23 import org.locationtech.jts.index.SpatialIndex;
 24 import org.locationtech.jts.index.strtree.STRtree;
 25  
 26 /**
 27  * A Hilbert-Packed R-tree.  This is a static R-tree
 28  * which is packed by using the Hilbert ordering 
 29  * of the tree items.
 30  * <p>
 31  * The tree is constructed by sorting the items
 32  * by the Hilbert code of the midpoint of their envelope.  
 33  * Then, a set of internal layers is created recursively
 34  * as follows:
 35  * <ul>
 36  * <li>The items/nodes of the previous are partitioned into blocks 
 37  * of size <code>nodeCapacity</code>
 38  * <li>For each block a layer node is created with range
 39  * equal to the envelope of the items/nodess in the block
 40  * </ul>
 41  * The internal layers are stored using an array to
 42  * store the node bounds.
 43  * The link between a node and its children is 
 44  * stored implicitly in the indexes of the array.
 45  * For efficiency, the offsets to the layers
 46  * within the node array are pre-computed and stored.
 47  * <p>
 48  * NOTE: Based on performance testing, 
 49  * the HPRtree is somewhat faster than the STRtree.
 50  * It should also be more memory-efficent,
 51  * due to fewer object allocations.
 52  * However, it is not clear whether this 
 53  * will produce a significant improvement 
 54  * for use in JTS operations.
 55  * 
 56  * @see STRtree
 57  * 
 58  * 
 59  * @author Martin Davis
 60  *
 61  */
 62 public class HPRtree  
 63   implements SpatialIndex
 64 {
 65   private static final int ENV_SIZE = 4;
 66  
 67   private static final int HILBERT_LEVEL = 12;
 68  
 69   private static int DEFAULT_NODE_CAPACITY = 16;
 70   
 71   private List<Item> items = new ArrayList<Item>();
 72   
 73   private int nodeCapacity = DEFAULT_NODE_CAPACITY;
 74  
 75   private Envelope totalExtent = new Envelope();
 76  
 77   private int[] layerStartIndex;
 78  
 79   private double[] nodeBounds;
 80  
 81   private boolean isBuilt = false;
 82  
 83   //public int nodeIntersectsCount;
 84  
 85   /**
 86    * Creates a new index with the default node capacity.
 87    */
 88   public HPRtree() {
 89     this(DEFAULT_NODE_CAPACITY);
 90   }
 91   
 92   /**
 93    * Creates a new index with the given node capacity.
 94    * 
 95    * @param nodeCapacity the node capacity to use
 96    */
 97   public HPRtree(int nodeCapacity) {
 98     this.nodeCapacity = nodeCapacity;
 99   }
100   
101   /**
102    * Gets the number of items in the index.
103    * 
104    * @return the number of items
105    */
106   public int size() {
107     return items.size();
108   }
109   
110   @Override
111   public void insert(Envelope itemEnv, Object item) {
112     if (isBuilt) {
113       throw new IllegalStateException("Cannot insert items after tree is built.");
114     }
115     items.add( new Item(itemEnv, item) );
116     totalExtent.expandToInclude(itemEnv);
117   }
118  
119   @Override
120   public List query(Envelope searchEnv) {
121     build();
122     
123     if (! totalExtent.intersects(searchEnv)) 
124       return new ArrayList();
125     
126     ArrayListVisitor visitor = new ArrayListVisitor();
127     query(searchEnv, visitor);
128     return visitor.getItems();
129   }
130  
131   @Override
132   public void query(Envelope searchEnv, ItemVisitor visitor) {
133     build();
134     if (! totalExtent.intersects(searchEnv)) 
135       return;
136     if (layerStartIndex == null) {
137       queryItems(0, searchEnv, visitor);
138     }
139     else {
140       queryTopLayer(searchEnv, visitor);
141     }
142   }
143  
144   private void queryTopLayer(Envelope searchEnv, ItemVisitor visitor) {
145     int layerIndex = layerStartIndex.length - 2;
146     int layerSize = layerSize(layerIndex);
147     // query each node in layer
148     for (int i = 0; i < layerSize; i += ENV_SIZE) {
149       queryNode(layerIndex, i, searchEnv, visitor);
150     }
151   }
152  
153   private void queryNode(int layerIndex, int nodeOffset, Envelope searchEnv, ItemVisitor visitor) {
154     int layerStart = layerStartIndex[layerIndex];
155     int nodeIndex = layerStart + nodeOffset;
156     if (! intersects(nodeIndex, searchEnv)) return;
157     if (layerIndex == 0) {
158       int childNodesOffset = nodeOffset / ENV_SIZE  * nodeCapacity;
159       queryItems(childNodesOffset, searchEnv, visitor);
160     }
161     else {
162       int childNodesOffset = nodeOffset * nodeCapacity;
163       queryNodeChildren(layerIndex - 1, childNodesOffset, searchEnv, visitor);
164     }
165   }
166  
167   private boolean intersects(int nodeIndex, Envelope env) {
168     //nodeIntersectsCount++;
169     boolean isBeyond = (env.getMaxX() < nodeBounds[nodeIndex]) 
170     || (env.getMaxY() < nodeBounds[nodeIndex+1]) 
171     || (env.getMinX() > nodeBounds[nodeIndex+2]) 
172     || (env.getMinY() > nodeBounds[nodeIndex+3]);
173     return ! isBeyond;
174   }
175   
176   private void queryNodeChildren(int layerIndex, int blockOffset, Envelope searchEnv, ItemVisitor visitor) {
177     int layerStart = layerStartIndex[layerIndex];
178     int layerEnd = layerStartIndex[layerIndex + 1];
179     for (int i = 0; i < nodeCapacity; i++) {
180       int nodeOffset = blockOffset + ENV_SIZE * i; 
181       // don't query past layer end
182       if (layerStart + nodeOffset >= layerEnd) break;
183       
184       queryNode(layerIndex, nodeOffset, searchEnv, visitor);
185     }
186   }
187  
188   private void queryItems(int blockStart, Envelope searchEnv, ItemVisitor visitor) {
189     for (int i = 0; i < nodeCapacity; i++) {
190       int itemIndex = blockStart + i; 
191       // don't query past end of items
192       if (itemIndex >= items.size()) break;
193       
194       // visit the item if its envelope intersects search env
195       Item item = items.get(itemIndex);
196       //nodeIntersectsCount++;
197       if (intersects( item.getEnvelope(), searchEnv) ) {
198       //if (item.getEnvelope().intersects(searchEnv)) {
199         visitor.visitItem(item.getItem());
200       }
201     }    
202   }
203  
204   /**
205    * Tests whether two envelopes intersect.
206    * Avoids the null check in {@link Envelope#intersects(Envelope)}.
207    * 
208    * @param env1 an envelope
209    * @param env2 an envelope
210    * @return true if the envelopes intersect
211    */
212   private static boolean intersects(Envelope env1, Envelope env2) {
213     return !(env2.getMinX() > env1.getMaxX() ||
214         env2.getMaxX() < env1.getMinX() ||
215         env2.getMinY() > env1.getMaxY() ||
216         env2.getMaxY() < env1.getMinY());
217   }
218   
219   private int layerSize(int layerIndex) {
220     int layerStart = layerStartIndex[layerIndex];
221     int layerEnd = layerStartIndex[layerIndex + 1];
222     return layerEnd - layerStart;
223   }
224  
225   @Override
226   public boolean remove(Envelope itemEnv, Object item) {
227     // TODO Auto-generated method stub
228     return false;
229   }
230   
231   /**
232    * Builds the index, if not already built.
233    */
234   public synchronized void build() {
235     // skip if already built
236     if (isBuilt) return;
237     isBuilt  = true;
238     // don't need to build an empty or very small tree
239     if (items.size() <= nodeCapacity) return;
240  
241     sortItems();
242     //dumpItems(items);
243     
244     layerStartIndex = computeLayerIndices(items.size(), nodeCapacity);
245     // allocate storage
246     int nodeCount = layerStartIndex[ layerStartIndex.length - 1 ] / 4;
247     nodeBounds = createBoundsArray(nodeCount);
248     
249     // compute tree nodes
250     computeLeafNodes(layerStartIndex[1]);
251     for (int i = 1; i < layerStartIndex.length - 1; i++) {
252       computeLayerNodes(i);
253     }
254     //dumpNodes();
255   }
256  
257   /*
258   private void dumpNodes() {
259     GeometryFactory fact = new GeometryFactory();
260     for (int i = 0; i < nodeMinX.length; i++) {
261       Envelope env = new Envelope(nodeMinX[i], nodeMaxX[i], nodeMinY[i], nodeMaxY[i]);;
262       System.out.println(fact.toGeometry(env));
263     }
264   }
265 */
266   
267   private static void dumpItems(List<Item> items) {
268     GeometryFactory fact = new GeometryFactory();
269     for (Item item : items) {
270       Envelope env = item.getEnvelope();
271       System.out.println(fact.toGeometry(env));
272     }
273   }
274  
275   private static double[] createBoundsArray(int size) {
276     double[] a = new double[4*size];
277     for (int i = 0; i < size; i++) {
278       int index = 4*i;
279       a[index] = Double.MAX_VALUE;
280       a[index+1] = Double.MAX_VALUE;
281       a[index+2] = -Double.MAX_VALUE;
282       a[index+3] = -Double.MAX_VALUE;
283     }
284     return a;
285   }
286  
287   private void computeLayerNodes(int layerIndex) {
288     int layerStart = layerStartIndex[layerIndex];
289     int childLayerStart = layerStartIndex[layerIndex - 1];
290     int layerSize = layerSize(layerIndex);
291     int childLayerEnd = layerStart;
292     for (int i = 0; i < layerSize; i += ENV_SIZE) {
293       int childStart = childLayerStart + nodeCapacity * i;
294       computeNodeBounds(layerStart + i, childStart, childLayerEnd);
295       //System.out.println("Layer: " + layerIndex + " node: " + i + " - " + getNodeEnvelope(layerStart + i));
296     }
297   }
298  
299   private void computeNodeBounds(int nodeIndex, int blockStart, int nodeMaxIndex) {
300     for (int i = 0; i <= nodeCapacity; i++ ) {
301       int index = blockStart + 4 * i;
302       if (index >= nodeMaxIndex) break;
303       updateNodeBounds(nodeIndex, nodeBounds[index], nodeBounds[index+1], nodeBounds[index+2], nodeBounds[index+3]);
304     } 
305   }
306  
307   private void computeLeafNodes(int layerSize) {
308     for (int i = 0; i < layerSize; i += ENV_SIZE) {
309       computeLeafNodeBounds(i, nodeCapacity * i/4);
310     }
311   }
312  
313   private void computeLeafNodeBounds(int nodeIndex, int blockStart) {
314     for (int i = 0; i <= nodeCapacity; i++ ) {
315       int itemIndex = blockStart + i;
316       if (itemIndex >= items.size()) break;
317       Envelope env = items.get(itemIndex).getEnvelope();
318       updateNodeBounds(nodeIndex, env.getMinX(), env.getMinY(), env.getMaxX(), env.getMaxY());
319     }
320   }
321  
322   private void updateNodeBounds(int nodeIndex, double minX, double minY, double maxX, double maxY) {
323     if (minX < nodeBounds[nodeIndex]) nodeBounds[nodeIndex] = minX;
324     if (minY < nodeBounds[nodeIndex+1]) nodeBounds[nodeIndex+1] = minY;
325     if (maxX > nodeBounds[nodeIndex+2]) nodeBounds[nodeIndex+2] = maxX;
326     if (maxY > nodeBounds[nodeIndex+3]) nodeBounds[nodeIndex+3] = maxY;
327   }
328  
329   private Envelope getNodeEnvelope(int i) {
330     return new Envelope(nodeBounds[i], nodeBounds[i+1], nodeBounds[i+2], nodeBounds[i+3]);
331   }
332   
333   private static int[] computeLayerIndices(int itemSize, int nodeCapacity) {
334     List<Integer> layerIndexList = new ArrayList<Integer>();
335     int layerSize = itemSize;
336     int index = 0;
337     do {
338       layerIndexList.add(index);
339       layerSize = numNodesToCover(layerSize, nodeCapacity);
340       index += ENV_SIZE * layerSize;
341     } while (layerSize > 1);
342     return toIntArray(layerIndexList);
343   }
344   
345   /**
346    * Computes the number of blocks (nodes) required to 
347    * cover a given number of children.
348    * 
349    * @param nChild
350    * @param nodeCapacity
351    * @return the number of nodes needed to cover the children
352    */
353   private static int numNodesToCover(int nChild, int nodeCapacity) {
354     int mult = nChild / nodeCapacity;
355     int total = mult * nodeCapacity;
356     if (total == nChild) return mult;
357     return mult + 1;
358   }
359   
360   private static int[] toIntArray(List<Integer> list) {
361     int[] array = new int[list.size()];
362     for (int i = 0; i < array.length; i++) {
363       array[i] = list.get(i);
364     }
365     return array;
366   }
367  
368   /**
369    * Gets the extents of the internal index nodes
370    * 
371    * @return a list of the internal node extents
372    */
373   public Envelope[] getBounds() {
374     int numNodes = nodeBounds.length / 4;
375     Envelope[] bounds = new Envelope[numNodes];
376     // create from largest to smallest
377     for (int i = numNodes - 1; i >= 0; i--) {
378       int boundIndex = 4 * i;
379       bounds[i] = new Envelope( nodeBounds[boundIndex], nodeBounds[boundIndex+2],
380           nodeBounds[boundIndex+1], nodeBounds[boundIndex+3]);
381     }
382     return bounds;
383   }
384   
385   private void sortItems() {
386     ItemComparator comp = new ItemComparator(new HilbertEncoder(HILBERT_LEVEL, totalExtent));
387     Collections.sort(items, comp);
388   }
389   
390   static class ItemComparator implements Comparator<Item> {
391  
392     private HilbertEncoder encoder;
393     
394     public ItemComparator(HilbertEncoder encoder) {
395       this.encoder = encoder;
396     }
397  
398     @Override
399     public int compare(Item item1, Item item2) {
400       int hcode1 = encoder.encode(item1.getEnvelope());
401       int hcode2 = encoder.encode(item2.getEnvelope());
402       return Integer.compare(hcode1, hcode2);
403     }
404   }
405  
406 }
407