Doc Classic

Class Root

 1  
 2 /*
 3  * Copyright (c) 2016 Vivid Solutions.
 4  *
 5  * All rights reserved. This program and the accompanying materials
 6  * are made available under the terms of the Eclipse Public License 2.0
 7  * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 8  * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 9  * and the Eclipse Distribution License is available at
10  *
11  * http://www.eclipse.org/org/documents/edl-v10.php.
12  */
13 package org.locationtech.jts.index.quadtree;
14  
15 import org.locationtech.jts.geom.Coordinate;
16 import org.locationtech.jts.geom.Envelope;
17 import org.locationtech.jts.util.Assert;
18  
19 /**
20  * QuadRoot is the root of a single Quadtree.  It is centred at the origin,
21  * and does not have a defined extent.
22  *
23  * @version 1.7
24  */
25 public class Root
26   extends NodeBase
27 {
28  
29   // the singleton root quad is centred at the origin.
30   private static final Coordinate origin = new Coordinate(0.0, 0.0);
31  
32   public Root()
33   {
34   }
35  
36   /**
37    * Insert an item into the quadtree this is the root of.
38    */
39   public void insert(Envelope itemEnv, Object item)
40   {
41     int index = getSubnodeIndex(itemEnv, origin.x, origin.y);
42     // if index is -1, itemEnv must cross the X or Y axis.
43     if (index == -1) {
44       add(item);
45       return;
46     }
47     /**
48      * the item must be contained in one quadrant, so insert it into the
49      * tree for that quadrant (which may not yet exist)
50      */
51     Node node = subnode[index];
52     /**
53      *  If the subquad doesn't exist or this item is not contained in it,
54      *  have to expand the tree upward to contain the item.
55      */
56  
57     if (node == null || ! node.getEnvelope().contains(itemEnv)) {
58        Node largerNode = Node.createExpanded(node, itemEnv);
59        subnode[index] = largerNode;
60     }
61     /**
62      * At this point we have a subquad which exists and must contain
63      * contains the env for the item.  Insert the item into the tree.
64      */
65     insertContained(subnode[index], itemEnv, item);
66     //System.out.println("depth = " + root.depth() + " size = " + root.size());
67     //System.out.println(" size = " + size());
68   }
69  
70   /**
71    * insert an item which is known to be contained in the tree rooted at
72    * the given QuadNode root.  Lower levels of the tree will be created
73    * if necessary to hold the item.
74    */
75   private void insertContained(Node tree, Envelope itemEnv, Object item)
76   {
77     Assert.isTrue(tree.getEnvelope().contains(itemEnv));
78    /**
79     * Do NOT create a new quad for zero-area envelopes - this would lead
80     * to infinite recursion. Instead, use a heuristic of simply returning
81     * the smallest existing quad containing the query
82     */
83     boolean isZeroX = IntervalSize.isZeroWidth(itemEnv.getMinX(), itemEnv.getMaxX());
84     boolean isZeroY = IntervalSize.isZeroWidth(itemEnv.getMinY(), itemEnv.getMaxY());
85     NodeBase node;
86     if (isZeroX || isZeroY)
87       node = tree.find(itemEnv);
88     else
89       node = tree.getNode(itemEnv);
90     node.add(item);
91   }
92  
93   protected boolean isSearchMatch(Envelope searchEnv)
94   {
95     return true;
96   }
97  
98  
99 }
100