0
# Spatial Utilities
1

2
Additional spatial utility functions for envelope calculation, circle conversion, and bit manipulation operations. These utilities provide advanced spatial operations and low-level optimization functions for geometric computations.
3

4
## Capabilities
5

6
### SpatialEnvelopeVisitor
7

8
Determines the spatial envelope (bounding box) of geometries with support for both Cartesian and geographic coordinate systems.
9

10
```java { .api }
11
/**
12
 * Calculates the spatial envelope (bounding box) of a geometry
13
 * @param geometry the geometry to analyze
14
 * @return Optional containing the bounding rectangle, or empty if geometry is empty
15
 */
16
public static Optional<Rectangle> visit(Geometry geometry)
17

18
/**
19
 * Visitor pattern implementation for envelope calculation
20
 * @param <E> exception type that may be thrown during processing
21
 */
22
public class SpatialEnvelopeVisitor<E extends Exception> implements GeometryVisitor<Optional<Rectangle>, E> {
23
    
24
    /**
25
     * Creates a cartesian envelope visitor
26
     * @return visitor for cartesian coordinate systems
27
     */
28
    public static SpatialEnvelopeVisitor<RuntimeException> cartesian()
29
    
30
    /**
31
     * Creates a geographic envelope visitor with dateline wrapping
32
     * @return visitor for geographic coordinate systems
33
     */
34
    public static SpatialEnvelopeVisitor<RuntimeException> geographic()
35
    
36
    /**
37
     * Creates a geographic envelope visitor with optional dateline wrapping
38
     * @param wrapLongitude whether to consider longitude wrapping around dateline
39
     * @return visitor for geographic coordinate systems
40
     */
41
    public static SpatialEnvelopeVisitor<RuntimeException> geographic(boolean wrapLongitude)
42
}
43
```
44

45
**Usage Examples:**
46

47
```java
48
import org.elasticsearch.geometry.utils.SpatialEnvelopeVisitor;
49
import java.util.Optional;
50

51
// Calculate envelope for any geometry
52
Polygon complexPolygon = createComplexPolygon();
53
Optional<Rectangle> envelope = SpatialEnvelopeVisitor.visit(complexPolygon);
54

55
if (envelope.isPresent()) {
56
    Rectangle bbox = envelope.get();
57
    double width = bbox.getMaxX() - bbox.getMinX();
58
    double height = bbox.getMaxY() - bbox.getMinY();
59
    System.out.println("Bounding box: " + width + " x " + height);
60
}
61

62
// Use specific coordinate system visitor
63
SpatialEnvelopeVisitor<RuntimeException> cartesianVisitor = SpatialEnvelopeVisitor.cartesian();
64
Optional<Rectangle> cartesianEnvelope = complexPolygon.visit(cartesianVisitor);
65

66
// Geographic visitor with dateline wrapping consideration
67
SpatialEnvelopeVisitor<RuntimeException> geoVisitor = SpatialEnvelopeVisitor.geographic(true);
68
Optional<Rectangle> geoEnvelope = complexPolygon.visit(geoVisitor);
69
```
70

71
### CircleUtils
72

73
Utilities for converting circles to polygon approximations and performing spatial calculations.
74

75
```java { .api }
76
/**
77
 * Minimum number of sides for circle-to-polygon conversion
78
 */
79
public static final int CIRCLE_TO_POLYGON_MINIMUM_NUMBER_OF_SIDES = 4;
80

81
/**
82
 * Maximum number of sides for circle-to-polygon conversion
83
 */
84
public static final int CIRCLE_TO_POLYGON_MAXIMUM_NUMBER_OF_SIDES = 1000;
85

86
/**
87
 * Converts a circle to a regular polygon approximation
88
 * @param circle the circle to convert
89
 * @param gons number of sides for the polygon (4-1000)
90
 * @return polygon approximating the circle
91
 * @throws IllegalArgumentException if circle contains a pole or gons is invalid
92
 */
93
public static Polygon createRegularGeoShapePolygon(Circle circle, int gons)
94

95
/**
96
 * Calculates haversine distance between two points (internal utility)
97
 * @param lat1 latitude of first point
98
 * @param lon1 longitude of first point  
99
 * @param lat2 latitude of second point
100
 * @param lon2 longitude of second point
101
 * @return distance in meters
102
 */
103
private static double slowHaversin(double lat1, double lon1, double lat2, double lon2)
104
```
105

106
**Usage Examples:**
107

108
```java
109
import org.elasticsearch.geometry.utils.CircleUtils;
110

111
// Convert circle to polygon with 64 sides
112
Circle circle = new Circle(-73.935, 40.730, 1000.0); // 1km radius
113
Polygon circlePolygon = CircleUtils.createRegularGeoShapePolygon(circle, 64);
114

115
// Lower precision for performance (minimum 4 sides)
116
Polygon simplePolygon = CircleUtils.createRegularGeoShapePolygon(circle, 8);
117

118
// High precision approximation (maximum 1000 sides)
119
Polygon precisePolygon = CircleUtils.createRegularGeoShapePolygon(circle, 1000);
120

121
// Error handling for polar circles
122
try {
123
    Circle polarCircle = new Circle(0, 89, 200000); // Large circle near north pole
124
    Polygon result = CircleUtils.createRegularGeoShapePolygon(polarCircle, 32);
125
} catch (IllegalArgumentException e) {
126
    System.err.println("Circle contains pole: " + e.getMessage());
127
}
128
```
129

130
### BitUtil
131

132
Low-level bit manipulation utilities for spatial indexing and Morton encoding operations.
133

134
```java { .api }
135
/**
136
 * Interleaves the first 32 bits of two integer values
137
 * @param even the even-positioned bits (usually x coordinate)
138
 * @param odd the odd-positioned bits (usually y coordinate)  
139
 * @return interleaved long value with bits from both inputs
140
 */
141
public static long interleave(int even, int odd)
142

143
/**
144
 * Deinterleaves a long value to extract even-positioned bits
145
 * @param interleaved the interleaved long value
146
 * @return integer containing the even-positioned bits
147
 */
148
public static int deinterleave(long interleaved)
149

150
/**
151
 * Deinterleaves a long value to extract odd-positioned bits  
152
 * @param interleaved the interleaved long value
153
 * @return integer containing the odd-positioned bits
154
 */
155
public static int deinterleaveOdd(long interleaved)
156

157
/**
158
 * Flips all bits in an integer value
159
 * @param value the integer to flip
160
 * @return integer with all bits flipped
161
 */
162
public static int flipBits(int value)
163

164
/**
165
 * Counts the number of set bits in an integer
166
 * @param value the integer to analyze
167
 * @return number of bits set to 1
168
 */
169
public static int popCount(int value)
170
```
171

172
**Usage Examples:**
173

174
```java
175
import org.elasticsearch.geometry.utils.BitUtil;
176

177
// Spatial indexing with Morton encoding
178
int xCoord = 12345;
179
int yCoord = 67890;
180

181
// Interleave coordinates for Z-order curve
182
long mortonCode = BitUtil.interleave(xCoord, yCoord);
183

184
// Extract coordinates back from Morton code
185
int extractedX = BitUtil.deinterleave(mortonCode);
186
int extractedY = BitUtil.deinterleaveOdd(mortonCode);
187

188
assert extractedX == xCoord;
189
assert extractedY == yCoord;
190

191
// Bit manipulation operations
192
int value = 0b10110010;
193
int flipped = BitUtil.flipBits(value);        // 0b01001101
194
int setBits = BitUtil.popCount(value);        // 4 (number of 1s)
195

196
// Geospatial indexing example
197
double longitude = -73.935242;
198
double latitude = 40.730610;
199

200
// Convert to integer coordinates (simplified example)
201
int lonBits = (int) ((longitude + 180.0) * 1000000);
202
int latBits = (int) ((latitude + 90.0) * 1000000);
203

204
// Create spatial index key
205
long spatialKey = BitUtil.interleave(lonBits, latBits);
206
```
207

208
## Advanced Usage Patterns
209

210
### Combined Envelope and Circle Conversion
211

212
```java
213
// Get envelope, convert to circle, then to polygon
214
MultiPolygon complexGeometry = createComplexMultiPolygon();
215

216
// Calculate bounding envelope
217
Optional<Rectangle> envelope = SpatialEnvelopeVisitor.visit(complexGeometry);
218

219
if (envelope.isPresent()) {
220
    Rectangle bbox = envelope.get();
221
    
222
    // Create circle that covers the envelope
223
    double centerLon = (bbox.getMinX() + bbox.getMaxX()) / 2;
224
    double centerLat = (bbox.getMinY() + bbox.getMaxY()) / 2;
225
    double width = bbox.getMaxX() - bbox.getMinX();
226
    double height = bbox.getMaxY() - bbox.getMinY();
227
    double radius = Math.sqrt(width * width + height * height) * 111320 / 2; // approx meters
228
    
229
    Circle boundingCircle = new Circle(centerLon, centerLat, radius);
230
    
231
    // Convert to polygon approximation
232
    Polygon approximation = CircleUtils.createRegularGeoShapePolygon(boundingCircle, 32);
233
}
234
```
235

236
### Spatial Grid Indexing with BitUtil
237

238
```java
239
// Create spatial grid index using Morton encoding
240
public class SpatialGrid {
241
    private static final double WORLD_WIDTH = 360.0;
242
    private static final double WORLD_HEIGHT = 180.0;
243
    private final int resolution;
244
    
245
    public SpatialGrid(int resolution) {
246
        this.resolution = resolution;
247
    }
248
    
249
    public long encode(double longitude, double latitude) {
250
        // Normalize coordinates to grid
251
        int x = (int) ((longitude + 180.0) / WORLD_WIDTH * resolution);
252
        int y = (int) ((latitude + 90.0) / WORLD_HEIGHT * resolution);
253
        
254
        // Clamp to bounds
255
        x = Math.max(0, Math.min(resolution - 1, x));
256
        y = Math.max(0, Math.min(resolution - 1, y));
257
        
258
        return BitUtil.interleave(x, y);
259
    }
260
    
261
    public Point decode(long mortonCode) {
262
        int x = BitUtil.deinterleave(mortonCode);
263
        int y = BitUtil.deinterleaveOdd(mortonCode);
264
        
265
        double longitude = (double) x / resolution * WORLD_WIDTH - 180.0;
266
        double latitude = (double) y / resolution * WORLD_HEIGHT - 90.0;
267
        
268
        return new Point(longitude, latitude);
269
    }
270
}
271

272
// Usage
273
SpatialGrid grid = new SpatialGrid(1024);
274
long gridKey = grid.encode(-73.935242, 40.730610);
275
Point gridCenter = grid.decode(gridKey);
276
```
277

278
### Geographic vs Cartesian Envelope Calculation
279

280
```java
281
// Different envelope calculations for different coordinate systems
282
Polygon antimeridianPolygon = createAntimeridianSpanningPolygon();
283

284
// Cartesian envelope (treats coordinates as planar)
285
Optional<Rectangle> cartesianEnv = antimeridianPolygon.visit(
286
    SpatialEnvelopeVisitor.cartesian()
287
);
288

289
// Geographic envelope without dateline wrapping  
290
Optional<Rectangle> geoEnvNoWrap = antimeridianPolygon.visit(
291
    SpatialEnvelopeVisitor.geographic(false)
292
);
293

294
// Geographic envelope with dateline wrapping (smaller bbox)
295
Optional<Rectangle> geoEnvWrap = antimeridianPolygon.visit(
296
    SpatialEnvelopeVisitor.geographic(true)
297
);
298

299
// Compare envelope sizes to choose optimal representation
300
if (geoEnvWrap.isPresent() && geoEnvNoWrap.isPresent()) {
301
    Rectangle wrapped = geoEnvWrap.get();
302
    Rectangle unwrapped = geoEnvNoWrap.get();
303
    
304
    double wrappedArea = (wrapped.getMaxX() - wrapped.getMinX()) * 
305
                        (wrapped.getMaxY() - wrapped.getMinY());
306
    double unwrappedArea = (unwrapped.getMaxX() - unwrapped.getMinX()) * 
307
                          (unwrapped.getMaxY() - unwrapped.getMinY());
308
    
309
    Rectangle optimal = wrappedArea < unwrappedArea ? wrapped : unwrapped;
310
}
311
```