-
Notifications
You must be signed in to change notification settings - Fork 165
/
ShapeCollection.java
228 lines (197 loc) · 7.15 KB
/
ShapeCollection.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
/*******************************************************************************
* Copyright (c) 2015 Voyager Search and MITRE
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Apache License, Version 2.0 which
* accompanies this distribution and is available at
* http://www.apache.org/licenses/LICENSE-2.0.txt
******************************************************************************/
package org.locationtech.spatial4j.shape;
import org.locationtech.spatial4j.context.SpatialContext;
import org.locationtech.spatial4j.shape.impl.BBoxCalculator;
import java.util.*;
import static org.locationtech.spatial4j.shape.SpatialRelation.CONTAINS;
import static org.locationtech.spatial4j.shape.SpatialRelation.INTERSECTS;
/**
* A collection of Shape objects, analogous to an OGC GeometryCollection. The
* implementation demands a List (with random access) so that the order can be
* retained if an application requires it, although logically it's treated as an
* unordered Set, mostly.
* <p>
* Ideally, {@link #relate(Shape)} should return the same result no matter what
* the shape order is, although the default implementation can be order
* dependent when the shapes overlap; see {@link #relateContainsShortCircuits()}.
* To improve performance slightly, the caller could order the shapes by
* largest first so that relate() will have a greater chance of
* short-circuit'ing sooner. As the Shape contract states; it may return
* intersects when the best answer is actually contains or within. If any shape
* intersects the provided shape then that is the answer.
* <p>
* This implementation is not optimized for a large number of shapes; relate is
* O(N). A more sophisticated implementation might do an R-Tree based on
* bbox'es, for example.
*/
public class ShapeCollection<S extends Shape> extends AbstractList<S> implements Shape {
protected final SpatialContext ctx;
protected final List<S> shapes;
protected final Rectangle bbox;
/**
* WARNING: {@code shapes} is copied by reference.
* @param shapes Copied by reference! (make a defensive copy if caller modifies)
*/
public ShapeCollection(List<S> shapes, SpatialContext ctx) {
if (!(shapes instanceof RandomAccess))
throw new IllegalArgumentException("Shapes arg must implement RandomAccess: "+shapes.getClass());
this.shapes = shapes;
this.ctx = ctx;
this.bbox = computeBoundingBox(shapes, ctx);
}
protected Rectangle computeBoundingBox(Collection<? extends Shape> shapes, SpatialContext ctx) {
if (shapes.isEmpty())
return ctx.makeRectangle(Double.NaN, Double.NaN, Double.NaN, Double.NaN);
BBoxCalculator bboxCalc = new BBoxCalculator(ctx);
for (Shape geom : shapes) {
bboxCalc.expandRange(geom.getBoundingBox());
}
return bboxCalc.getBoundary();
}
public List<S> getShapes() {
return shapes;
}
@Override
public S get(int index) {
return shapes.get(index);
}
@Override
public int size() {
return shapes.size();
}
@Override
public Rectangle getBoundingBox() {
return bbox;
}
@Override
public Point getCenter() {
return bbox.getCenter();
}
@Override
public boolean hasArea() {
for (Shape geom : shapes) {
if( geom.hasArea() ) {
return true;
}
}
return false;
}
@Override
public ShapeCollection getBuffered(double distance, SpatialContext ctx) {
List<Shape> bufColl = new ArrayList<>(size());
for (Shape shape : shapes) {
bufColl.add(shape.getBuffered(distance, ctx));
}
return ctx.makeCollection(bufColl);
}
@Override
public SpatialRelation relate(Shape other) {
final SpatialRelation bboxSect = bbox.relate(other);
if (bboxSect == SpatialRelation.DISJOINT || bboxSect == SpatialRelation.WITHIN)
return bboxSect;
final boolean containsWillShortCircuit = (other instanceof Point) ||
relateContainsShortCircuits();
SpatialRelation sect = null;
for (Shape shape : shapes) {
SpatialRelation nextSect = shape.relate(other);
if (sect == null) {//first pass
sect = nextSect;
} else {
sect = sect.combine(nextSect);
}
if (sect == INTERSECTS)
return INTERSECTS;
if (sect == CONTAINS && containsWillShortCircuit)
return CONTAINS;
}
return sect;
}
/**
* Called by relate() to determine whether to return early if it finds
* CONTAINS, instead of checking the remaining shapes. It will do so without
* calling this method if the "other" shape is a Point. If a remaining shape
* finds INTERSECTS, then INTERSECTS will be returned. The only problem with
* this returning true is that if some of the shapes overlap, it's possible
* that the result of relate() could be dependent on the order of the shapes,
* which could be unexpected / wrong depending on the application. The default
* implementation returns true because it probably doesn't matter. If it
* does, a subclass could add a boolean flag that this method could return.
* That flag could be initialized to true only if the shapes are mutually
* disjoint.
*
* @see #computeMutualDisjoint(java.util.List) .
*/
protected boolean relateContainsShortCircuits() {
return true;
}
/**
* Computes whether the shapes are mutually disjoint. This is a utility method
* offered for use by a subclass implementing {@link #relateContainsShortCircuits()}.
* <b>Beware: this is an O(N^2) algorithm.</b>. Consequently, consider safely
* assuming non-disjoint if shapes.size() > 10 or something. And if all shapes
* are a Point then the result of this method doesn't ultimately matter.
*/
protected static boolean computeMutualDisjoint(List<? extends Shape> shapes) {
//WARNING: this is an O(n^2) algorithm.
//loop through each shape and see if it intersects any shape before it
for (int i = 1; i < shapes.size(); i++) {
Shape shapeI = shapes.get(i);
for (int j = 0; j < i; j++) {
Shape shapeJ = shapes.get(j);
if (shapeJ.relate(shapeI).intersects())
return false;
}
}
return true;
}
@Override
public double getArea(SpatialContext ctx) {
double MAX_AREA = bbox.getArea(ctx);
double sum = 0;
for (Shape geom : shapes) {
sum += geom.getArea(ctx);
if (sum >= MAX_AREA)
return MAX_AREA;
}
return sum;
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder(100);
buf.append("ShapeCollection(");
int i = 0;
for (Shape shape : shapes) {
if (i++ > 0)
buf.append(", ");
buf.append(shape);
if (buf.length() > 150) {
buf.append(" ...").append(shapes.size());
break;
}
}
buf.append(")");
return buf.toString();
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
ShapeCollection that = (ShapeCollection) o;
if (!shapes.equals(that.shapes)) return false;
return true;
}
@Override
public int hashCode() {
return shapes.hashCode();
}
@Override
public SpatialContext getContext() {
return ctx;
}
}