Doc Classic

Class Node

  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.Envelope;
 16 import org.locationtech.jts.util.Assert;
 17  
 18 /**
 19  * Represents a node of a {@link Quadtree}.  Nodes contain
 20  * items which have a spatial extent corresponding to the node's position
 21  * in the quadtree.
 22  *
 23  * @version 1.7
 24  */
 25 public class Node
 26   extends NodeBase
 27 {
 28   public static Node createNode(Envelope env)
 29   {
 30     Key key = new Key(env);
 31     Node node = new Node(key.getEnvelope(), key.getLevel());
 32     return node;
 33   }
 34  
 35   public static Node createExpanded(Node node, Envelope addEnv)
 36   {
 37     Envelope expandEnv = new Envelope(addEnv);
 38     if (node != null) expandEnv.expandToInclude(node.env);
 39  
 40     Node largerNode = createNode(expandEnv);
 41     if (node != null) largerNode.insertNode(node);
 42     return largerNode;
 43   }
 44  
 45   private Envelope env;
 46   private double centrex;
 47   private double centrey;
 48   private int level;
 49  
 50   public Node(Envelope env, int level)
 51   {
 52     //this.parent = parent;
 53     this.env = env;
 54     this.level = level;
 55     centrex = (env.getMinX() + env.getMaxX()) / 2;
 56     centrey = (env.getMinY() + env.getMaxY()) / 2;
 57   }
 58  
 59   public Envelope getEnvelope() { return env; }
 60  
 61   protected boolean isSearchMatch(Envelope searchEnv)
 62   {
 63       if (searchEnv == null) return false;
 64     return env.intersects(searchEnv);
 65   }
 66  
 67   /**
 68    * Returns the subquad containing the envelope <tt>searchEnv</tt>.
 69    * Creates the subquad if
 70    * it does not already exist.
 71    * 
 72    * @return the subquad containing the search envelope
 73    */
 74   public Node getNode(Envelope searchEnv)
 75   {
 76     int subnodeIndex = getSubnodeIndex(searchEnv, centrex, centrey);
 77     // if subquadIndex is -1 searchEnv is not contained in a subquad
 78     if (subnodeIndex != -1) {
 79       // create the quad if it does not exist
 80       Node node = getSubnode(subnodeIndex);
 81       // recursively search the found/created quad
 82       return node.getNode(searchEnv);
 83     }
 84     else {
 85       return this;
 86     }
 87   }
 88  
 89   /**
 90    * Returns the smallest <i>existing</i>
 91    * node containing the envelope.
 92    */
 93   public NodeBase find(Envelope searchEnv)
 94   {
 95     int subnodeIndex = getSubnodeIndex(searchEnv, centrex, centrey);
 96     if (subnodeIndex == -1)
 97       return this;
 98     if (subnode[subnodeIndex] != null) {
 99       // query lies in subquad, so search it
100       Node node = subnode[subnodeIndex];
101       return node.find(searchEnv);
102     }
103     // no existing subquad, so return this one anyway
104     return this;
105   }
106  
107   void insertNode(Node node)
108   {
109     Assert.isTrue(env == null || env.contains(node.env));
110 //System.out.println(env);
111 //System.out.println(quad.env);
112     int index = getSubnodeIndex(node.env, centrex, centrey);
113 //System.out.println(index);
114     if (node.level == level - 1) {
115       subnode[index] = node;
116 //System.out.println("inserted");
117     }
118     else {
119       // the quad is not a direct child, so make a new child quad to contain it
120       // and recursively insert the quad
121       Node childNode = createSubnode(index);
122       childNode.insertNode(node);
123       subnode[index] = childNode;
124     }
125   }
126  
127   /**
128    * get the subquad for the index.
129    * If it doesn't exist, create it
130    */
131   private Node getSubnode(int index)
132   {
133     if (subnode[index] == null) {
134       subnode[index] = createSubnode(index);
135     }
136     return subnode[index];
137   }
138  
139   private Node createSubnode(int index)
140   {
141         // create a new subquad in the appropriate quadrant
142  
143       double minx = 0.0;
144       double maxx = 0.0;
145       double miny = 0.0;
146       double maxy = 0.0;
147  
148       switch (index) {
149       case 0:
150         minx = env.getMinX();
151         maxx = centrex;
152         miny = env.getMinY();
153         maxy = centrey;
154         break;
155       case 1:
156         minx = centrex;
157         maxx = env.getMaxX();
158         miny = env.getMinY();
159         maxy = centrey;
160         break;
161       case 2:
162         minx = env.getMinX();
163         maxx = centrex;
164         miny = centrey;
165         maxy = env.getMaxY();
166         break;
167       case 3:
168         minx = centrex;
169         maxx = env.getMaxX();
170         miny = centrey;
171         maxy = env.getMaxY();
172         break;
173       }
174       Envelope sqEnv = new Envelope(minx, maxx, miny, maxy);
175       Node node = new Node(sqEnv, level - 1);
176     return node;
177   }
178  
179 }
180