1 |
|
---|
2 | /*
|
---|
3 | * The JTS Topology Suite is a collection of Java classes that
|
---|
4 | * implement the fundamental operations required to validate a given
|
---|
5 | * geo-spatial data set to a known topological specification.
|
---|
6 | *
|
---|
7 | * Copyright (C) 2001 Vivid Solutions
|
---|
8 | *
|
---|
9 | * This library is free software; you can redistribute it and/or
|
---|
10 | * modify it under the terms of the GNU Lesser General Public
|
---|
11 | * License as published by the Free Software Foundation; either
|
---|
12 | * version 2.1 of the License, or (at your option) any later version.
|
---|
13 | *
|
---|
14 | * This library is distributed in the hope that it will be useful,
|
---|
15 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
16 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
---|
17 | * Lesser General Public License for more details.
|
---|
18 | *
|
---|
19 | * You should have received a copy of the GNU Lesser General Public
|
---|
20 | * License along with this library; if not, write to the Free Software
|
---|
21 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
|
---|
22 | *
|
---|
23 | * For more information, contact:
|
---|
24 | *
|
---|
25 | * Vivid Solutions
|
---|
26 | * Suite #1A
|
---|
27 | * 2328 Government Street
|
---|
28 | * Victoria BC V8T 5G5
|
---|
29 | * Canada
|
---|
30 | *
|
---|
31 | * (250)385-6040
|
---|
32 | * www.vividsolutions.com
|
---|
33 | */
|
---|
34 | package com.vividsolutions.jts.index.quadtree;
|
---|
35 |
|
---|
36 | import com.vividsolutions.jts.geom.Coordinate;
|
---|
37 | import com.vividsolutions.jts.geom.Envelope;
|
---|
38 | import com.vividsolutions.jts.util.Assert;
|
---|
39 |
|
---|
40 | /**
|
---|
41 | * QuadRoot is the root of a single Quadtree. It is centred at the origin,
|
---|
42 | * and does not have a defined extent.
|
---|
43 | *
|
---|
44 | * @version 1.7
|
---|
45 | */
|
---|
46 | public class Root
|
---|
47 | extends NodeBase
|
---|
48 | {
|
---|
49 |
|
---|
50 | // the singleton root quad is centred at the origin.
|
---|
51 | private static final Coordinate origin = new Coordinate(0.0, 0.0);
|
---|
52 |
|
---|
53 | public Root()
|
---|
54 | {
|
---|
55 | }
|
---|
56 |
|
---|
57 | /**
|
---|
58 | * Insert an item into the quadtree this is the root of.
|
---|
59 | */
|
---|
60 | public void insert(Envelope itemEnv, Object item)
|
---|
61 | {
|
---|
62 | int index = getSubnodeIndex(itemEnv, origin);
|
---|
63 | // if index is -1, itemEnv must cross the X or Y axis.
|
---|
64 | if (index == -1) {
|
---|
65 | add(item);
|
---|
66 | return;
|
---|
67 | }
|
---|
68 | /**
|
---|
69 | * the item must be contained in one quadrant, so insert it into the
|
---|
70 | * tree for that quadrant (which may not yet exist)
|
---|
71 | */
|
---|
72 | Node node = subnode[index];
|
---|
73 | /**
|
---|
74 | * If the subquad doesn't exist or this item is not contained in it,
|
---|
75 | * have to expand the tree upward to contain the item.
|
---|
76 | */
|
---|
77 |
|
---|
78 | if (node == null || ! node.getEnvelope().contains(itemEnv)) {
|
---|
79 | Node largerNode = Node.createExpanded(node, itemEnv);
|
---|
80 | subnode[index] = largerNode;
|
---|
81 | }
|
---|
82 | /**
|
---|
83 | * At this point we have a subquad which exists and must contain
|
---|
84 | * contains the env for the item. Insert the item into the tree.
|
---|
85 | */
|
---|
86 | insertContained(subnode[index], itemEnv, item);
|
---|
87 | //System.out.println("depth = " + root.depth() + " size = " + root.size());
|
---|
88 | //System.out.println(" size = " + size());
|
---|
89 | }
|
---|
90 |
|
---|
91 | /**
|
---|
92 | * insert an item which is known to be contained in the tree rooted at
|
---|
93 | * the given QuadNode root. Lower levels of the tree will be created
|
---|
94 | * if necessary to hold the item.
|
---|
95 | */
|
---|
96 | private void insertContained(Node tree, Envelope itemEnv, Object item)
|
---|
97 | {
|
---|
98 | Assert.isTrue(tree.getEnvelope().contains(itemEnv));
|
---|
99 | /**
|
---|
100 | * Do NOT create a new quad for zero-area envelopes - this would lead
|
---|
101 | * to infinite recursion. Instead, use a heuristic of simply returning
|
---|
102 | * the smallest existing quad containing the query
|
---|
103 | */
|
---|
104 | boolean isZeroX = IntervalSize.isZeroWidth(itemEnv.getMinX(), itemEnv.getMaxX());
|
---|
105 | boolean isZeroY = IntervalSize.isZeroWidth(itemEnv.getMinY(), itemEnv.getMaxY());
|
---|
106 | NodeBase node;
|
---|
107 | if (isZeroX || isZeroY)
|
---|
108 | node = tree.find(itemEnv);
|
---|
109 | else
|
---|
110 | node = tree.getNode(itemEnv);
|
---|
111 | node.add(item);
|
---|
112 | }
|
---|
113 |
|
---|
114 | protected boolean isSearchMatch(Envelope searchEnv)
|
---|
115 | {
|
---|
116 | return true;
|
---|
117 | }
|
---|
118 |
|
---|
119 |
|
---|
120 | }
|
---|