1 /* 2 * Copyright (c) 2016 Vivid Solutions. 3 * 4 * All rights reserved. This program and the accompanying materials 5 * are made available under the terms of the Eclipse Public License 2.0 6 * and Eclipse Distribution License v. 1.0 which accompanies this distribution. 7 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html 8 * and the Eclipse Distribution License is available at 9 * 10 * http://www.eclipse.org/org/documents/edl-v10.php. 11 */ 12 package org.locationtech.jts.geom; 13 14 import java.io.Serializable; 15 import java.util.Collection; 16 import java.util.Iterator; 17 18 import org.locationtech.jts.algorithm.Centroid; 19 import org.locationtech.jts.algorithm.ConvexHull; 20 import org.locationtech.jts.algorithm.InteriorPoint; 21 import org.locationtech.jts.geom.util.GeometryCollectionMapper; 22 import org.locationtech.jts.geom.util.GeometryMapper; 23 import org.locationtech.jts.io.WKTWriter; 24 import org.locationtech.jts.operation.IsSimpleOp; 25 import org.locationtech.jts.operation.buffer.BufferOp; 26 import org.locationtech.jts.operation.distance.DistanceOp; 27 import org.locationtech.jts.operation.linemerge.LineMerger; 28 import org.locationtech.jts.operation.overlay.OverlayOp; 29 import org.locationtech.jts.operation.overlay.snap.SnapIfNeededOverlayOp; 30 import org.locationtech.jts.operation.predicate.RectangleContains; 31 import org.locationtech.jts.operation.predicate.RectangleIntersects; 32 import org.locationtech.jts.operation.relate.RelateOp; 33 import org.locationtech.jts.operation.union.UnaryUnionOp; 34 import org.locationtech.jts.operation.valid.IsValidOp; 35 import org.locationtech.jts.util.Assert; 36 37 38 /** 39 * A representation of a planar, linear vector geometry. 40 * <P> 41 * 42 * <H3>Binary Predicates</H3> 43 * Because it is not clear at this time 44 * what semantics for spatial 45 * analysis methods involving <code>GeometryCollection</code>s would be useful, 46 * <code>GeometryCollection</code>s are not supported as arguments to binary 47 * predicates or the <code>relate</code> 48 * method. 49 * 50 * <H3>Overlay Methods</H3> 51 * 52 * The overlay methods 53 * return the most specific class possible to represent the result. If the 54 * result is homogeneous, a <code>Point</code>, <code>LineString</code>, or 55 * <code>Polygon</code> will be returned if the result contains a single 56 * element; otherwise, a <code>MultiPoint</code>, <code>MultiLineString</code>, 57 * or <code>MultiPolygon</code> will be returned. If the result is 58 * heterogeneous a <code>GeometryCollection</code> will be returned. <P> 59 * 60 * Because it is not clear at this time what semantics for set-theoretic 61 * methods involving <code>GeometryCollection</code>s would be useful, 62 * <code>GeometryCollections</code> 63 * are not supported as arguments to the set-theoretic methods. 64 * 65 * <H4>Representation of Computed Geometries </H4> 66 * 67 * The SFS states that the result 68 * of a set-theoretic method is the "point-set" result of the usual 69 * set-theoretic definition of the operation (SFS 3.2.21.1). However, there are 70 * sometimes many ways of representing a point set as a <code>Geometry</code>. 71 * <P> 72 * 73 * The SFS does not specify an unambiguous representation of a given point set 74 * returned from a spatial analysis method. One goal of JTS is to make this 75 * specification precise and unambiguous. JTS uses a canonical form for 76 * <code>Geometry</code>s returned from overlay methods. The canonical 77 * form is a <code>Geometry</code> which is simple and noded: 78 * <UL> 79 * <LI> Simple means that the Geometry returned will be simple according to 80 * the JTS definition of <code>isSimple</code>. 81 * <LI> Noded applies only to overlays involving <code>LineString</code>s. It 82 * means that all intersection points on <code>LineString</code>s will be 83 * present as endpoints of <code>LineString</code>s in the result. 84 * </UL> 85 * This definition implies that non-simple geometries which are arguments to 86 * spatial analysis methods must be subjected to a line-dissolve process to 87 * ensure that the results are simple. 88 * 89 * <H4> Constructed Points And The Precision Model </H4> 90 * 91 * The results computed by the set-theoretic methods may 92 * contain constructed points which are not present in the input <code>Geometry</code> 93 * s. These new points arise from intersections between line segments in the 94 * edges of the input <code>Geometry</code>s. In the general case it is not 95 * possible to represent constructed points exactly. This is due to the fact 96 * that the coordinates of an intersection point may contain twice as many bits 97 * of precision as the coordinates of the input line segments. In order to 98 * represent these constructed points explicitly, JTS must truncate them to fit 99 * the <code>PrecisionModel</code>. <P> 100 * 101 * Unfortunately, truncating coordinates moves them slightly. Line segments 102 * which would not be coincident in the exact result may become coincident in 103 * the truncated representation. This in turn leads to "topology collapses" -- 104 * situations where a computed element has a lower dimension than it would in 105 * the exact result. <P> 106 * 107 * When JTS detects topology collapses during the computation of spatial 108 * analysis methods, it will throw an exception. If possible the exception will 109 * report the location of the collapse. <P> 110 * 111 * <h3>Geometry Equality</h3> 112 * 113 * There are two ways of comparing geometries for equality: 114 * <b>structural equality</b> and <b>topological equality</b>. 115 * 116 * <h4>Structural Equality</h4> 117 * 118 * Structural Equality is provided by the 119 * {@link #equalsExact(Geometry)} method. 120 * This implements a comparison based on exact, structural pointwise 121 * equality. 122 * The {@link #equals(Object)} is a synonym for this method, 123 * to provide structural equality semantics for 124 * use in Java collections. 125 * It is important to note that structural pointwise equality 126 * is easily affected by things like 127 * ring order and component order. In many situations 128 * it will be desirable to normalize geometries before 129 * comparing them (using the {@link #norm()} 130 * or {@link #normalize()} methods). 131 * {@link #equalsNorm(Geometry)} is provided 132 * as a convenience method to compute equality over 133 * normalized geometries, but it is expensive to use. 134 * Finally, {@link #equalsExact(Geometry, double)} 135 * allows using a tolerance value for point comparison. 136 * 137 * 138 * <h4>Topological Equality</h4> 139 * 140 * Topological Equality is provided by the 141 * {@link #equalsTopo(Geometry)} method. 142 * It implements the SFS definition of point-set equality 143 * defined in terms of the DE-9IM matrix. 144 * To support the SFS naming convention, the method 145 * {@link #equals(Geometry)} is also provided as a synonym. 146 * However, due to the potential for confusion with {@link #equals(Object)} 147 * its use is discouraged. 148 * <p> 149 * Since {@link #equals(Object)} and {@link #hashCode()} are overridden, 150 * Geometries can be used effectively in Java collections. 151 * 152 *@version 1.7 153 */ 154 public abstract class Geometry 155 implements Cloneable, Comparable, Serializable 156 { 157 private static final long serialVersionUID = 8763622679187376702L; 158 159 protected static final int TYPECODE_POINT = 0; 160 protected static final int TYPECODE_MULTIPOINT = 1; 161 protected static final int TYPECODE_LINESTRING = 2; 162 protected static final int TYPECODE_LINEARRING = 3; 163 protected static final int TYPECODE_MULTILINESTRING = 4; 164 protected static final int TYPECODE_POLYGON = 5; 165 protected static final int TYPECODE_MULTIPOLYGON = 6; 166 protected static final int TYPECODE_GEOMETRYCOLLECTION = 7; 167 168 public static final String TYPENAME_POINT = "Point"; 169 public static final String TYPENAME_MULTIPOINT = "MultiPoint"; 170 public static final String TYPENAME_LINESTRING = "LineString"; 171 public static final String TYPENAME_LINEARRING = "LinearRing"; 172 public static final String TYPENAME_MULTILINESTRING = "MultiLineString"; 173 public static final String TYPENAME_POLYGON = "Polygon"; 174 public static final String TYPENAME_MULTIPOLYGON = "MultiPolygon"; 175 public static final String TYPENAME_GEOMETRYCOLLECTION = "GeometryCollection"; 176 177 private final static GeometryComponentFilter geometryChangedFilter = new GeometryComponentFilter() { 178 public void filter(Geometry geom) { 179 geom.geometryChangedAction(); 180 } 181 }; 182 183 /** 184 * The bounding box of this <code>Geometry</code>. 185 */ 186 protected Envelope envelope; 187 188 /** 189 * The {@link GeometryFactory} used to create this Geometry 190 */ 191 protected final GeometryFactory factory; 192 193 /** 194 * The ID of the Spatial Reference System used by this <code>Geometry</code> 195 */ 196 protected int SRID; 197 198 /** 199 * An object reference which can be used to carry ancillary data defined 200 * by the client. 201 */ 202 private Object userData = null; 203 204 /** 205 * Creates a new <code>Geometry</code> via the specified GeometryFactory. 206 * 207 * @param factory 208 */ Geometry(GeometryFactory factory)209 public Geometry(GeometryFactory factory) { 210 this.factory = factory; 211 this.SRID = factory.getSRID(); 212 } 213 214 /** 215 * Returns the name of this Geometry's actual class. 216 * 217 *@return the name of this <code>Geometry</code>s actual class 218 */ getGeometryType()219 public abstract String getGeometryType(); 220 221 /** 222 * Returns true if the array contains any non-empty <code>Geometry</code>s. 223 * 224 *@param geometries an array of <code>Geometry</code>s; no elements may be 225 * <code>null</code> 226 *@return <code>true</code> if any of the <code>Geometry</code>s 227 * <code>isEmpty</code> methods return <code>false</code> 228 */ hasNonEmptyElements(Geometry[] geometries)229 protected static boolean hasNonEmptyElements(Geometry[] geometries) { 230 for (int i = 0; i < geometries.length; i++) { 231 if (!geometries[i].isEmpty()) { 232 return true; 233 } 234 } 235 return false; 236 } 237 238 /** 239 * Returns true if the array contains any <code>null</code> elements. 240 * 241 *@param array an array to validate 242 *@return <code>true</code> if any of <code>array</code>s elements are 243 * <code>null</code> 244 */ hasNullElements(Object[] array)245 protected static boolean hasNullElements(Object[] array) { 246 for (int i = 0; i < array.length; i++) { 247 if (array[i] == null) { 248 return true; 249 } 250 } 251 return false; 252 } 253 254 /** 255 * Returns the ID of the Spatial Reference System used by the <code>Geometry</code>. 256 * <P> 257 * 258 * JTS supports Spatial Reference System information in the simple way 259 * defined in the SFS. A Spatial Reference System ID (SRID) is present in 260 * each <code>Geometry</code> object. <code>Geometry</code> provides basic 261 * accessor operations for this field, but no others. The SRID is represented 262 * as an integer. 263 * 264 *@return the ID of the coordinate space in which the <code>Geometry</code> 265 * is defined. 266 * 267 */ getSRID()268 public int getSRID() { 269 return SRID; 270 } 271 /** 272 * Sets the ID of the Spatial Reference System used by the <code>Geometry</code>. 273 * <p> 274 * <b>NOTE:</b> This method should only be used for exceptional circumstances or 275 * for backwards compatibility. Normally the SRID should be set on the 276 * {@link GeometryFactory} used to create the geometry. 277 * SRIDs set using this method will <i>not</i> be propagated to 278 * geometries returned by constructive methods. 279 * 280 * @see GeometryFactory 281 */ setSRID(int SRID)282 public void setSRID(int SRID) { 283 this.SRID = SRID; 284 } 285 286 /** 287 * Gets the factory which contains the context in which this geometry was created. 288 * 289 * @return the factory for this geometry 290 */ getFactory()291 public GeometryFactory getFactory() { 292 return factory; 293 } 294 295 /** 296 * Gets the user data object for this geometry, if any. 297 * 298 * @return the user data object, or <code>null</code> if none set 299 */ getUserData()300 public Object getUserData() { 301 return userData; 302 } 303 304 /** 305 * Returns the number of {@link Geometry}s in a {@link GeometryCollection} 306 * (or 1, if the geometry is not a collection). 307 * 308 * @return the number of geometries contained in this geometry 309 */ getNumGeometries()310 public int getNumGeometries() { 311 return 1; 312 } 313 314 /** 315 * Returns an element {@link Geometry} from a {@link GeometryCollection} 316 * (or <code>this</code>, if the geometry is not a collection). 317 * 318 * @param n the index of the geometry element 319 * @return the n'th geometry contained in this geometry 320 */ getGeometryN(int n)321 public Geometry getGeometryN(int n) { 322 return this; 323 } 324 325 326 /** 327 * A simple scheme for applications to add their own custom data to a Geometry. 328 * An example use might be to add an object representing a Coordinate Reference System. 329 * <p> 330 * Note that user data objects are not present in geometries created by 331 * construction methods. 332 * 333 * @param userData an object, the semantics for which are defined by the 334 * application using this Geometry 335 */ setUserData(Object userData)336 public void setUserData(Object userData) { 337 this.userData = userData; 338 } 339 340 341 /** 342 * Returns the <code>PrecisionModel</code> used by the <code>Geometry</code>. 343 * 344 *@return the specification of the grid of allowable points, for this 345 * <code>Geometry</code> and all other <code>Geometry</code>s 346 */ getPrecisionModel()347 public PrecisionModel getPrecisionModel() { 348 return factory.getPrecisionModel(); 349 } 350 351 /** 352 * Returns a vertex of this <code>Geometry</code> 353 * (usually, but not necessarily, the first one). 354 * The returned coordinate should not be assumed 355 * to be an actual Coordinate object used in 356 * the internal representation. 357 * 358 *@return a {@link Coordinate} which is a vertex of this <code>Geometry</code>. 359 *@return null if this Geometry is empty 360 */ getCoordinate()361 public abstract Coordinate getCoordinate(); 362 363 /** 364 * Returns an array containing the values of all the vertices for 365 * this geometry. 366 * If the geometry is a composite, the array will contain all the vertices 367 * for the components, in the order in which the components occur in the geometry. 368 * <p> 369 * In general, the array cannot be assumed to be the actual internal 370 * storage for the vertices. Thus modifying the array 371 * may not modify the geometry itself. 372 * Use the {@link CoordinateSequence#setOrdinate} method 373 * (possibly on the components) to modify the underlying data. 374 * If the coordinates are modified, 375 * {@link #geometryChanged} must be called afterwards. 376 * 377 *@return the vertices of this <code>Geometry</code> 378 *@see #geometryChanged 379 *@see CoordinateSequence#setOrdinate 380 */ getCoordinates()381 public abstract Coordinate[] getCoordinates(); 382 383 /** 384 * Returns the count of this <code>Geometry</code>s vertices. The <code>Geometry</code> 385 * s contained by composite <code>Geometry</code>s must be 386 * Geometry's; that is, they must implement <code>getNumPoints</code> 387 * 388 *@return the number of vertices in this <code>Geometry</code> 389 */ getNumPoints()390 public abstract int getNumPoints(); 391 392 /** 393 * Tests whether this {@link Geometry} is simple. 394 * The SFS definition of simplicity 395 * follows the general rule that a Geometry is simple if it has no points of 396 * self-tangency, self-intersection or other anomalous points. 397 * <p> 398 * Simplicity is defined for each {@link Geometry} subclass as follows: 399 * <ul> 400 * <li>Valid polygonal geometries are simple, since their rings 401 * must not self-intersect. <code>isSimple</code> 402 * tests for this condition and reports <code>false</code> if it is not met. 403 * (This is a looser test than checking for validity). 404 * <li>Linear rings have the same semantics. 405 * <li>Linear geometries are simple iff they do not self-intersect at points 406 * other than boundary points. 407 * <li>Zero-dimensional geometries (points) are simple iff they have no 408 * repeated points. 409 * <li>Empty <code>Geometry</code>s are always simple. 410 * </ul> 411 * 412 * @return <code>true</code> if this <code>Geometry</code> is simple 413 * @see #isValid 414 */ isSimple()415 public boolean isSimple() 416 { 417 IsSimpleOp op = new IsSimpleOp(this); 418 return op.isSimple(); 419 } 420 421 /** 422 * Tests whether this <code>Geometry</code> 423 * is topologically valid, according to the OGC SFS specification. 424 * <p> 425 * For validity rules see the Javadoc for the specific Geometry subclass. 426 * 427 *@return <code>true</code> if this <code>Geometry</code> is valid 428 * 429 * @see IsValidOp 430 */ isValid()431 public boolean isValid() 432 { 433 return IsValidOp.isValid(this); 434 } 435 436 /** 437 * Tests whether the set of points covered by this <code>Geometry</code> is 438 * empty. 439 * 440 *@return <code>true</code> if this <code>Geometry</code> does not cover any points 441 */ isEmpty()442 public abstract boolean isEmpty(); 443 444 /** 445 * Returns the minimum distance between this <code>Geometry</code> 446 * and another <code>Geometry</code>. 447 * 448 * @param g the <code>Geometry</code> from which to compute the distance 449 * @return the distance between the geometries 450 * @return 0 if either input geometry is empty 451 * @throws IllegalArgumentException if g is null 452 */ distance(Geometry g)453 public double distance(Geometry g) 454 { 455 return DistanceOp.distance(this, g); 456 } 457 458 /** 459 * Tests whether the distance from this <code>Geometry</code> 460 * to another is less than or equal to a specified value. 461 * 462 * @param geom the Geometry to check the distance to 463 * @param distance the distance value to compare 464 * @return <code>true</code> if the geometries are less than <code>distance</code> apart. 465 */ isWithinDistance(Geometry geom, double distance)466 public boolean isWithinDistance(Geometry geom, double distance) 467 { 468 return DistanceOp.isWithinDistance(this, geom, distance); 469 } 470 471 /** 472 * Tests whether this is a rectangular {@link Polygon}. 473 * 474 * @return true if the geometry is a rectangle. 475 */ isRectangle()476 public boolean isRectangle() 477 { 478 // Polygon overrides to check for actual rectangle 479 return false; 480 } 481 482 /** 483 * Returns the area of this <code>Geometry</code>. 484 * Areal Geometries have a non-zero area. 485 * They override this function to compute the area. 486 * Others return 0.0 487 * 488 *@return the area of the Geometry 489 */ getArea()490 public double getArea() 491 { 492 return 0.0; 493 } 494 495 /** 496 * Returns the length of this <code>Geometry</code>. 497 * Linear geometries return their length. 498 * Areal geometries return their perimeter. 499 * They override this function to compute the area. 500 * Others return 0.0 501 * 502 *@return the length of the Geometry 503 */ getLength()504 public double getLength() 505 { 506 return 0.0; 507 } 508 509 /** 510 * Computes the centroid of this <code>Geometry</code>. 511 * The centroid 512 * is equal to the centroid of the set of component Geometries of highest 513 * dimension (since the lower-dimension geometries contribute zero 514 * "weight" to the centroid). 515 * <p> 516 * The centroid of an empty geometry is <code>POINT EMPTY</code>. 517 * 518 * @return a {@link Point} which is the centroid of this Geometry 519 */ getCentroid()520 public Point getCentroid() 521 { 522 if (isEmpty()) 523 return factory.createPoint(); 524 Coordinate centPt = Centroid.getCentroid(this); 525 return createPointFromInternalCoord(centPt, this); 526 } 527 528 /** 529 * Computes an interior point of this <code>Geometry</code>. 530 * An interior point is guaranteed to lie in the interior of the Geometry, 531 * if it possible to calculate such a point exactly. Otherwise, 532 * the point may lie on the boundary of the geometry. 533 * <p> 534 * The interior point of an empty geometry is <code>POINT EMPTY</code>. 535 * 536 * @return a {@link Point} which is in the interior of this Geometry 537 */ getInteriorPoint()538 public Point getInteriorPoint() 539 { 540 if (isEmpty()) return factory.createPoint(); 541 Coordinate pt = InteriorPoint.getInteriorPoint(this); 542 return createPointFromInternalCoord(pt, this); 543 } 544 545 /** 546 * Returns the dimension of this geometry. 547 * The dimension of a geometry is is the topological 548 * dimension of its embedding in the 2-D Euclidean plane. 549 * In the JTS spatial model, dimension values are in the set {0,1,2}. 550 * <p> 551 * Note that this is a different concept to the dimension of 552 * the vertex {@link Coordinate}s. 553 * The geometry dimension can never be greater than the coordinate dimension. 554 * For example, a 0-dimensional geometry (e.g. a Point) 555 * may have a coordinate dimension of 3 (X,Y,Z). 556 * 557 *@return the topological dimension of this geometry. 558 */ getDimension()559 public abstract int getDimension(); 560 561 /** 562 * Returns the boundary, or an empty geometry of appropriate dimension 563 * if this <code>Geometry</code> is empty. 564 * (In the case of zero-dimensional geometries, ' 565 * an empty GeometryCollection is returned.) 566 * For a discussion of this function, see the OpenGIS Simple 567 * Features Specification. As stated in SFS Section 2.1.13.1, "the boundary 568 * of a Geometry is a set of Geometries of the next lower dimension." 569 * 570 *@return the closure of the combinatorial boundary of this <code>Geometry</code> 571 */ getBoundary()572 public abstract Geometry getBoundary(); 573 574 /** 575 * Returns the dimension of this <code>Geometry</code>s inherent boundary. 576 * 577 *@return the dimension of the boundary of the class implementing this 578 * interface, whether or not this object is the empty geometry. Returns 579 * <code>Dimension.FALSE</code> if the boundary is the empty geometry. 580 */ getBoundaryDimension()581 public abstract int getBoundaryDimension(); 582 583 /** 584 * Gets a Geometry representing the envelope (bounding box) of 585 * this <code>Geometry</code>. 586 * <p> 587 * If this <code>Geometry</code> is: 588 * <ul> 589 * <li>empty, returns an empty <code>Point</code>. 590 * <li>a point, returns a <code>Point</code>. 591 * <li>a line parallel to an axis, a two-vertex <code>LineString</code> 592 * <li>otherwise, returns a 593 * <code>Polygon</code> whose vertices are (minx miny, minx maxy, 594 * maxx maxy, maxx miny, minx miny). 595 * </ul> 596 * 597 *@return a Geometry representing the envelope of this Geometry 598 * 599 * @see GeometryFactory#toGeometry(Envelope) 600 */ getEnvelope()601 public Geometry getEnvelope() { 602 return getFactory().toGeometry(getEnvelopeInternal()); 603 } 604 605 /** 606 * Gets an {@link Envelope} containing 607 * the minimum and maximum x and y values in this <code>Geometry</code>. 608 * If the geometry is empty, an empty <code>Envelope</code> 609 * is returned. 610 * <p> 611 * The returned object is a copy of the one maintained internally, 612 * to avoid aliasing issues. 613 * For best performance, clients which access this 614 * envelope frequently should cache the return value. 615 * 616 *@return the envelope of this <code>Geometry</code>. 617 *@return an empty Envelope if this Geometry is empty 618 */ getEnvelopeInternal()619 public Envelope getEnvelopeInternal() { 620 if (envelope == null) { 621 envelope = computeEnvelopeInternal(); 622 } 623 return new Envelope(envelope); 624 } 625 626 /** 627 * Notifies this geometry that its coordinates have been changed by an external 628 * party (for example, via a {@link CoordinateFilter}). 629 * When this method is called the geometry will flush 630 * and/or update any derived information it has cached (such as its {@link Envelope} ). 631 * The operation is applied to all component Geometries. 632 */ geometryChanged()633 public void geometryChanged() { 634 apply(geometryChangedFilter); 635 } 636 637 /** 638 * Notifies this Geometry that its Coordinates have been changed by an external 639 * party. When #geometryChanged is called, this method will be called for 640 * this Geometry and its component Geometries. 641 * 642 * @see #apply(GeometryComponentFilter) 643 */ geometryChangedAction()644 protected void geometryChangedAction() { 645 envelope = null; 646 } 647 648 /** 649 * Tests whether this geometry is disjoint from the argument geometry. 650 * <p> 651 * The <code>disjoint</code> predicate has the following equivalent definitions: 652 * <ul> 653 * <li>The two geometries have no point in common 654 * <li>The DE-9IM Intersection Matrix for the two geometries matches 655 * <code>[FF*FF****]</code> 656 * <li><code>! g.intersects(this) = true</code> 657 * <br>(<code>disjoint</code> is the inverse of <code>intersects</code>) 658 * </ul> 659 * 660 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 661 *@return <code>true</code> if the two <code>Geometry</code>s are 662 * disjoint 663 * 664 * @see Geometry#intersects 665 */ disjoint(Geometry g)666 public boolean disjoint(Geometry g) { 667 return ! intersects(g); 668 } 669 670 /** 671 * Tests whether this geometry touches the 672 * argument geometry. 673 * <p> 674 * The <code>touches</code> predicate has the following equivalent definitions: 675 * <ul> 676 * <li>The geometries have at least one point in common, 677 * but their interiors do not intersect. 678 * <li>The DE-9IM Intersection Matrix for the two geometries matches 679 * at least one of the following patterns 680 * <ul> 681 * <li><code>[FT*******]</code> 682 * <li><code>[F**T*****]</code> 683 * <li><code>[F***T****]</code> 684 * </ul> 685 * </ul> 686 * If both geometries have dimension 0, the predicate returns <code>false</code>, 687 * since points have only interiors. 688 * This predicate is symmetric. 689 * 690 * 691 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 692 *@return <code>true</code> if the two <code>Geometry</code>s touch; 693 * Returns <code>false</code> if both <code>Geometry</code>s are points 694 */ touches(Geometry g)695 public boolean touches(Geometry g) { 696 // short-circuit test 697 if (! getEnvelopeInternal().intersects(g.getEnvelopeInternal())) 698 return false; 699 return relate(g).isTouches(getDimension(), g.getDimension()); 700 } 701 702 /** 703 * Tests whether this geometry intersects the argument geometry. 704 * <p> 705 * The <code>intersects</code> predicate has the following equivalent definitions: 706 * <ul> 707 * <li>The two geometries have at least one point in common 708 * <li>The DE-9IM Intersection Matrix for the two geometries matches 709 * at least one of the patterns 710 * <ul> 711 * <li><code>[T********]</code> 712 * <li><code>[*T*******]</code> 713 * <li><code>[***T*****]</code> 714 * <li><code>[****T****]</code> 715 * </ul> 716 * <li><code>! g.disjoint(this) = true</code> 717 * <br>(<code>intersects</code> is the inverse of <code>disjoint</code>) 718 * </ul> 719 * 720 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 721 *@return <code>true</code> if the two <code>Geometry</code>s intersect 722 * 723 * @see Geometry#disjoint 724 */ intersects(Geometry g)725 public boolean intersects(Geometry g) { 726 727 // short-circuit envelope test 728 if (! getEnvelopeInternal().intersects(g.getEnvelopeInternal())) 729 return false; 730 731 /** 732 * TODO: (MD) Add optimizations: 733 * 734 * - for P-A case: 735 * If P is in env(A), test for point-in-poly 736 * 737 * - for A-A case: 738 * If env(A1).overlaps(env(A2)) 739 * test for overlaps via point-in-poly first (both ways) 740 * Possibly optimize selection of point to test by finding point of A1 741 * closest to centre of env(A2). 742 * (Is there a test where we shouldn't bother - e.g. if env A 743 * is much smaller than env B, maybe there's no point in testing 744 * pt(B) in env(A)? 745 */ 746 747 // optimization for rectangle arguments 748 if (isRectangle()) { 749 return RectangleIntersects.intersects((Polygon) this, g); 750 } 751 if (g.isRectangle()) { 752 return RectangleIntersects.intersects((Polygon) g, this); 753 } 754 if (isGeometryCollection() || g.isGeometryCollection()) { 755 for (int i = 0 ; i < getNumGeometries() ; i++) { 756 for (int j = 0 ; j < g.getNumGeometries() ; j++) { 757 if (getGeometryN(i).intersects(g.getGeometryN(j))) { 758 return true; 759 } 760 } 761 } 762 return false; 763 } 764 // general case 765 return relate(g).isIntersects(); 766 } 767 768 /** 769 * Tests whether this geometry crosses the 770 * argument geometry. 771 * <p> 772 * The <code>crosses</code> predicate has the following equivalent definitions: 773 * <ul> 774 * <li>The geometries have some but not all interior points in common. 775 * <li>The DE-9IM Intersection Matrix for the two geometries matches 776 * one of the following patterns: 777 * <ul> 778 * <li><code>[T*T******]</code> (for P/L, P/A, and L/A situations) 779 * <li><code>[T*****T**]</code> (for L/P, A/P, and A/L situations) 780 * <li><code>[0********]</code> (for L/L situations) 781 * </ul> 782 * </ul> 783 * For any other combination of dimensions this predicate returns <code>false</code>. 784 * <p> 785 * The SFS defined this predicate only for P/L, P/A, L/L, and L/A situations. 786 * In order to make the relation symmetric, 787 * JTS extends the definition to apply to L/P, A/P and A/L situations as well. 788 * 789 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 790 *@return <code>true</code> if the two <code>Geometry</code>s cross. 791 */ crosses(Geometry g)792 public boolean crosses(Geometry g) { 793 // short-circuit test 794 if (! getEnvelopeInternal().intersects(g.getEnvelopeInternal())) 795 return false; 796 return relate(g).isCrosses(getDimension(), g.getDimension()); 797 } 798 799 /** 800 * Tests whether this geometry is within the 801 * specified geometry. 802 * <p> 803 * The <code>within</code> predicate has the following equivalent definitions: 804 * <ul> 805 * <li>Every point of this geometry is a point of the other geometry, 806 * and the interiors of the two geometries have at least one point in common. 807 * <li>The DE-9IM Intersection Matrix for the two geometries matches 808 * <code>[T*F**F***]</code> 809 * <li><code>g.contains(this) = true</code> 810 * <br>(<code>within</code> is the converse of {@link #contains}) 811 * </ul> 812 * An implication of the definition is that 813 * "The boundary of a Geometry is not within the Geometry". 814 * In other words, if a geometry A is a subset of 815 * the points in the boundary of a geometry B, <code>A.within(B) = false</code> 816 * (As a concrete example, take A to be a LineString which lies in the boundary of a Polygon B.) 817 * For a predicate with similar behaviour but avoiding 818 * this subtle limitation, see {@link #coveredBy}. 819 * 820 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 821 *@return <code>true</code> if this <code>Geometry</code> is within 822 * <code>g</code> 823 * 824 * @see Geometry#contains 825 * @see Geometry#coveredBy 826 */ within(Geometry g)827 public boolean within(Geometry g) { 828 return g.contains(this); 829 } 830 831 /** 832 * Tests whether this geometry contains the 833 * argument geometry. 834 * <p> 835 * The <code>contains</code> predicate has the following equivalent definitions: 836 * <ul> 837 * <li>Every point of the other geometry is a point of this geometry, 838 * and the interiors of the two geometries have at least one point in common. 839 * <li>The DE-9IM Intersection Matrix for the two geometries matches 840 * the pattern 841 * <code>[T*****FF*]</code> 842 * <li><code>g.within(this) = true</code> 843 * <br>(<code>contains</code> is the converse of {@link #within} ) 844 * </ul> 845 * An implication of the definition is that "Geometries do not 846 * contain their boundary". In other words, if a geometry A is a subset of 847 * the points in the boundary of a geometry B, <code>B.contains(A) = false</code>. 848 * (As a concrete example, take A to be a LineString which lies in the boundary of a Polygon B.) 849 * For a predicate with similar behaviour but avoiding 850 * this subtle limitation, see {@link #covers}. 851 * 852 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 853 *@return <code>true</code> if this <code>Geometry</code> contains <code>g</code> 854 * 855 * @see Geometry#within 856 * @see Geometry#covers 857 */ contains(Geometry g)858 public boolean contains(Geometry g) { 859 // optimization - lower dimension cannot contain areas 860 if (g.getDimension() == 2 && getDimension() < 2) { 861 return false; 862 } 863 // optimization - P cannot contain a non-zero-length L 864 // Note that a point can contain a zero-length lineal geometry, 865 // since the line has no boundary due to Mod-2 Boundary Rule 866 if (g.getDimension() == 1 && getDimension() < 1 && g.getLength() > 0.0) { 867 return false; 868 } 869 // optimization - envelope test 870 if (! getEnvelopeInternal().contains(g.getEnvelopeInternal())) 871 return false; 872 // optimization for rectangle arguments 873 if (isRectangle()) { 874 return RectangleContains.contains((Polygon) this, g); 875 } 876 // general case 877 return relate(g).isContains(); 878 } 879 880 /** 881 * Tests whether this geometry overlaps the 882 * specified geometry. 883 * <p> 884 * The <code>overlaps</code> predicate has the following equivalent definitions: 885 * <ul> 886 * <li>The geometries have at least one point each not shared by the other 887 * (or equivalently neither covers the other), 888 * they have the same dimension, 889 * and the intersection of the interiors of the two geometries has 890 * the same dimension as the geometries themselves. 891 * <li>The DE-9IM Intersection Matrix for the two geometries matches 892 * <code>[T*T***T**]</code> (for two points or two surfaces) 893 * or <code>[1*T***T**]</code> (for two curves) 894 * </ul> 895 * If the geometries are of different dimension this predicate returns <code>false</code>. 896 * This predicate is symmetric. 897 * 898 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 899 *@return <code>true</code> if the two <code>Geometry</code>s overlap. 900 */ overlaps(Geometry g)901 public boolean overlaps(Geometry g) { 902 // short-circuit test 903 if (! getEnvelopeInternal().intersects(g.getEnvelopeInternal())) 904 return false; 905 return relate(g).isOverlaps(getDimension(), g.getDimension()); 906 } 907 908 /** 909 * Tests whether this geometry covers the 910 * argument geometry. 911 * <p> 912 * The <code>covers</code> predicate has the following equivalent definitions: 913 * <ul> 914 * <li>Every point of the other geometry is a point of this geometry. 915 * <li>The DE-9IM Intersection Matrix for the two geometries matches 916 * at least one of the following patterns: 917 * <ul> 918 * <li><code>[T*****FF*]</code> 919 * <li><code>[*T****FF*]</code> 920 * <li><code>[***T**FF*]</code> 921 * <li><code>[****T*FF*]</code> 922 * </ul> 923 * <li><code>g.coveredBy(this) = true</code> 924 * <br>(<code>covers</code> is the converse of {@link #coveredBy}) 925 * </ul> 926 * If either geometry is empty, the value of this predicate is <code>false</code>. 927 * <p> 928 * This predicate is similar to {@link #contains}, 929 * but is more inclusive (i.e. returns <code>true</code> for more cases). 930 * In particular, unlike <code>contains</code> it does not distinguish between 931 * points in the boundary and in the interior of geometries. 932 * For most situations, <code>covers</code> should be used in preference to <code>contains</code>. 933 * As an added benefit, <code>covers</code> is more amenable to optimization, 934 * and hence should be more performant. 935 * 936 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 937 *@return <code>true</code> if this <code>Geometry</code> covers <code>g</code> 938 * 939 * @see Geometry#contains 940 * @see Geometry#coveredBy 941 */ covers(Geometry g)942 public boolean covers(Geometry g) { 943 // optimization - lower dimension cannot cover areas 944 if (g.getDimension() == 2 && getDimension() < 2) { 945 return false; 946 } 947 // optimization - P cannot cover a non-zero-length L 948 // Note that a point can cover a zero-length lineal geometry 949 if (g.getDimension() == 1 && getDimension() < 1 && g.getLength() > 0.0) { 950 return false; 951 } 952 // optimization - envelope test 953 if (! getEnvelopeInternal().covers(g.getEnvelopeInternal())) 954 return false; 955 // optimization for rectangle arguments 956 if (isRectangle()) { 957 // since we have already tested that the test envelope is covered 958 return true; 959 } 960 return relate(g).isCovers(); 961 } 962 963 /** 964 * Tests whether this geometry is covered by the 965 * argument geometry. 966 * <p> 967 * The <code>coveredBy</code> predicate has the following equivalent definitions: 968 * <ul> 969 * <li>Every point of this geometry is a point of the other geometry. 970 * <li>The DE-9IM Intersection Matrix for the two geometries matches 971 * at least one of the following patterns: 972 * <ul> 973 * <li><code>[T*F**F***]</code> 974 * <li><code>[*TF**F***]</code> 975 * <li><code>[**FT*F***]</code> 976 * <li><code>[**F*TF***]</code> 977 * </ul> 978 * <li><code>g.covers(this) = true</code> 979 * <br>(<code>coveredBy</code> is the converse of {@link #covers}) 980 * </ul> 981 * If either geometry is empty, the value of this predicate is <code>false</code>. 982 * <p> 983 * This predicate is similar to {@link #within}, 984 * but is more inclusive (i.e. returns <code>true</code> for more cases). 985 * 986 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 987 *@return <code>true</code> if this <code>Geometry</code> is covered by <code>g</code> 988 * 989 * @see Geometry#within 990 * @see Geometry#covers 991 */ coveredBy(Geometry g)992 public boolean coveredBy(Geometry g) { 993 return g.covers(this); 994 } 995 996 /** 997 * Tests whether the elements in the DE-9IM 998 * {@link IntersectionMatrix} for the two <code>Geometry</code>s match the elements in <code>intersectionPattern</code>. 999 * The pattern is a 9-character string, with symbols drawn from the following set: 1000 * <UL> 1001 * <LI> 0 (dimension 0) 1002 * <LI> 1 (dimension 1) 1003 * <LI> 2 (dimension 2) 1004 * <LI> T ( matches 0, 1 or 2) 1005 * <LI> F ( matches FALSE) 1006 * <LI> * ( matches any value) 1007 * </UL> 1008 * For more information on the DE-9IM, see the <i>OpenGIS Simple Features 1009 * Specification</i>. 1010 * 1011 *@param g the <code>Geometry</code> with which to compare 1012 * this <code>Geometry</code> 1013 *@param intersectionPattern the pattern against which to check the 1014 * intersection matrix for the two <code>Geometry</code>s 1015 *@return <code>true</code> if the DE-9IM intersection 1016 * matrix for the two <code>Geometry</code>s match <code>intersectionPattern</code> 1017 * @see IntersectionMatrix 1018 */ relate(Geometry g, String intersectionPattern)1019 public boolean relate(Geometry g, String intersectionPattern) { 1020 return relate(g).matches(intersectionPattern); 1021 } 1022 1023 /** 1024 * Returns the DE-9IM {@link IntersectionMatrix} for the two <code>Geometry</code>s. 1025 * 1026 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 1027 *@return an {@link IntersectionMatrix} describing the intersections of the interiors, 1028 * boundaries and exteriors of the two <code>Geometry</code>s 1029 */ relate(Geometry g)1030 public IntersectionMatrix relate(Geometry g) { 1031 checkNotGeometryCollection(this); 1032 checkNotGeometryCollection(g); 1033 return RelateOp.relate(this, g); 1034 } 1035 1036 /** 1037 * Tests whether this geometry is 1038 * topologically equal to the argument geometry. 1039 * <p> 1040 * This method is included for backward compatibility reasons. 1041 * It has been superseded by the {@link #equalsTopo(Geometry)} method, 1042 * which has been named to clearly denote its functionality. 1043 * <p> 1044 * This method should NOT be confused with the method 1045 * {@link #equals(Object)}, which implements 1046 * an exact equality comparison. 1047 * 1048 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 1049 *@return true if the two <code>Geometry</code>s are topologically equal 1050 * 1051 *@see #equalsTopo(Geometry) 1052 */ equals(Geometry g)1053 public boolean equals(Geometry g) { 1054 if (g == null) return false; 1055 return equalsTopo(g); 1056 } 1057 1058 /** 1059 * Tests whether this geometry is topologically equal to the argument geometry 1060 * as defined by the SFS <code>equals</code> predicate. 1061 * <p> 1062 * The SFS <code>equals</code> predicate has the following equivalent definitions: 1063 * <ul> 1064 * <li>The two geometries have at least one point in common, 1065 * and no point of either geometry lies in the exterior of the other geometry. 1066 * <li>The DE-9IM Intersection Matrix for the two geometries matches 1067 * the pattern <code>T*F**FFF*</code> 1068 * <pre> 1069 * T*F 1070 * **F 1071 * FF* 1072 * </pre> 1073 * </ul> 1074 * <b>Note</b> that this method computes <b>topologically equality</b>. 1075 * For structural equality, see {@link #equalsExact(Geometry)}. 1076 * 1077 *@param g the <code>Geometry</code> with which to compare this <code>Geometry</code> 1078 *@return <code>true</code> if the two <code>Geometry</code>s are topologically equal 1079 * 1080 *@see #equalsExact(Geometry) 1081 */ equalsTopo(Geometry g)1082 public boolean equalsTopo(Geometry g) 1083 { 1084 // short-circuit test 1085 if (! getEnvelopeInternal().equals(g.getEnvelopeInternal())) 1086 return false; 1087 return relate(g).isEquals(getDimension(), g.getDimension()); 1088 } 1089 1090 /** 1091 * Tests whether this geometry is structurally and numerically equal 1092 * to a given <code>Object</code>. 1093 * If the argument <code>Object</code> is not a <code>Geometry</code>, 1094 * the result is <code>false</code>. 1095 * Otherwise, the result is computed using 1096 * {@link #equalsExact(Geometry)}. 1097 * <p> 1098 * This method is provided to fulfill the Java contract 1099 * for value-based object equality. 1100 * In conjunction with {@link #hashCode()} 1101 * it provides semantics which are most useful 1102 * for using 1103 * <code>Geometry</code>s as keys and values in Java collections. 1104 * <p> 1105 * Note that to produce the expected result the input geometries 1106 * should be in normal form. It is the caller's 1107 * responsibility to perform this where required 1108 * (using {@link Geometry#norm()} 1109 * or {@link #normalize()} as appropriate). 1110 * 1111 * @param o the Object to compare 1112 * @return true if this geometry is exactly equal to the argument 1113 * 1114 * @see #equalsExact(Geometry) 1115 * @see #hashCode() 1116 * @see #norm() 1117 * @see #normalize() 1118 */ equals(Object o)1119 public boolean equals(Object o) 1120 { 1121 if (! (o instanceof Geometry)) return false; 1122 Geometry g = (Geometry) o; 1123 return equalsExact(g); 1124 } 1125 1126 /** 1127 * Gets a hash code for the Geometry. 1128 * 1129 * @return an integer value suitable for use as a hashcode 1130 */ hashCode()1131 public int hashCode() 1132 { 1133 return getEnvelopeInternal().hashCode(); 1134 } 1135 toString()1136 public String toString() { 1137 return toText(); 1138 } 1139 1140 /** 1141 * Returns the Well-known Text representation of this <code>Geometry</code>. 1142 * For a definition of the Well-known Text format, see the OpenGIS Simple 1143 * Features Specification. 1144 * 1145 *@return the Well-known Text representation of this <code>Geometry</code> 1146 */ toText()1147 public String toText() { 1148 WKTWriter writer = new WKTWriter(); 1149 return writer.write(this); 1150 } 1151 1152 /** 1153 * Computes a buffer area around this geometry having the given width. The 1154 * buffer of a Geometry is the Minkowski sum or difference of the geometry 1155 * with a disc of radius <code>abs(distance)</code>. 1156 * <p> 1157 * Mathematically-exact buffer area boundaries can contain circular arcs. 1158 * To represent these arcs using linear geometry they must be approximated with line segments. 1159 * The buffer geometry is constructed using 8 segments per quadrant to approximate 1160 * the circular arcs. 1161 * The end cap style is <code>CAP_ROUND</code>. 1162 * <p> 1163 * The buffer operation always returns a polygonal result. The negative or 1164 * zero-distance buffer of lines and points is always an empty {@link Polygon}. 1165 * This is also the result for the buffers of degenerate (zero-area) polygons. 1166 * 1167 * @param distance 1168 * the width of the buffer (may be positive, negative or 0) 1169 * @return a polygonal geometry representing the buffer region (which may be 1170 * empty) 1171 * 1172 * @throws TopologyException 1173 * if a robustness error occurs 1174 * 1175 * @see #buffer(double, int) 1176 * @see #buffer(double, int, int) 1177 */ buffer(double distance)1178 public Geometry buffer(double distance) { 1179 return BufferOp.bufferOp(this, distance); 1180 } 1181 1182 /** 1183 * Computes a buffer area around this geometry having the given width and with 1184 * a specified accuracy of approximation for circular arcs. 1185 * <p> 1186 * Mathematically-exact buffer area boundaries can contain circular arcs. 1187 * To represent these arcs 1188 * using linear geometry they must be approximated with line segments. The 1189 * <code>quadrantSegments</code> argument allows controlling the accuracy of 1190 * the approximation by specifying the number of line segments used to 1191 * represent a quadrant of a circle 1192 * <p> 1193 * The buffer operation always returns a polygonal result. The negative or 1194 * zero-distance buffer of lines and points is always an empty {@link Polygon}. 1195 * This is also the result for the buffers of degenerate (zero-area) polygons. 1196 * 1197 * @param distance 1198 * the width of the buffer (may be positive, negative or 0) 1199 * @param quadrantSegments 1200 * the number of line segments used to represent a quadrant of a 1201 * circle 1202 * @return a polygonal geometry representing the buffer region (which may be 1203 * empty) 1204 * 1205 * @throws TopologyException 1206 * if a robustness error occurs 1207 * 1208 * @see #buffer(double) 1209 * @see #buffer(double, int, int) 1210 */ buffer(double distance, int quadrantSegments)1211 public Geometry buffer(double distance, int quadrantSegments) { 1212 return BufferOp.bufferOp(this, distance, quadrantSegments); 1213 } 1214 1215 /** 1216 * Computes a buffer area around this geometry having the given 1217 * width and with a specified accuracy of approximation for circular arcs, 1218 * and using a specified end cap style. 1219 * <p> 1220 * Mathematically-exact buffer area boundaries can contain circular arcs. 1221 * To represent these arcs using linear geometry they must be approximated with line segments. 1222 * The <code>quadrantSegments</code> argument allows controlling the 1223 * accuracy of the approximation 1224 * by specifying the number of line segments used to represent a quadrant of a circle 1225 * <p> 1226 * The end cap style specifies the buffer geometry that will be 1227 * created at the ends of linestrings. The styles provided are: 1228 * <ul> 1229 * <li><code>BufferOp.CAP_ROUND</code> - (default) a semi-circle 1230 * <li><code>BufferOp.CAP_BUTT</code> - a straight line perpendicular to the end segment 1231 * <li><code>BufferOp.CAP_SQUARE</code> - a half-square 1232 * </ul> 1233 * <p> 1234 * The buffer operation always returns a polygonal result. The negative or 1235 * zero-distance buffer of lines and points is always an empty {@link Polygon}. 1236 * This is also the result for the buffers of degenerate (zero-area) polygons. 1237 * 1238 *@param distance the width of the buffer (may be positive, negative or 0) 1239 *@param quadrantSegments the number of line segments used to represent a quadrant of a circle 1240 *@param endCapStyle the end cap style to use 1241 *@return a polygonal geometry representing the buffer region (which may be empty) 1242 * 1243 * @throws TopologyException if a robustness error occurs 1244 * 1245 * @see #buffer(double) 1246 * @see #buffer(double, int) 1247 * @see BufferOp 1248 */ buffer(double distance, int quadrantSegments, int endCapStyle)1249 public Geometry buffer(double distance, int quadrantSegments, int endCapStyle) { 1250 return BufferOp.bufferOp(this, distance, quadrantSegments, endCapStyle); 1251 } 1252 1253 /** 1254 * Computes the smallest convex <code>Polygon</code> that contains all the 1255 * points in the <code>Geometry</code>. This obviously applies only to <code>Geometry</code> 1256 * s which contain 3 or more points; the results for degenerate cases are 1257 * specified as follows: 1258 * <TABLE> 1259 * <TR> 1260 * <TH> Number of <code>Point</code>s in argument <code>Geometry</code> </TH> 1261 * <TH> <code>Geometry</code> class of result </TH> 1262 * </TR> 1263 * <TR> 1264 * <TD> 0 </TD> 1265 * <TD> empty <code>GeometryCollection</code> </TD> 1266 * </TR> 1267 * <TR> <TD> 1 </TD> 1268 * <TD> <code>Point</code> </TD> 1269 * </TR> 1270 * <TR> 1271 * <TD> 2 </TD> 1272 * <TD> <code>LineString</code> </TD> 1273 * </TR> 1274 * <TR> 1275 * <TD> 3 or more </TD> 1276 * <TD> <code>Polygon</code> </TD> 1277 * </TR> 1278 * </TABLE> 1279 * 1280 *@return the minimum-area convex polygon containing this <code>Geometry</code>' 1281 * s points 1282 */ convexHull()1283 public Geometry convexHull() { 1284 return (new ConvexHull(this)).getConvexHull(); 1285 } 1286 1287 /** 1288 * Computes a new geometry which has all component coordinate sequences 1289 * in reverse order (opposite orientation) to this one. 1290 * 1291 * @return a reversed geometry 1292 */ reverse()1293 public Geometry reverse() { 1294 1295 Geometry res = reverseInternal(); 1296 if (this.envelope != null) 1297 res.envelope = this.envelope.copy(); 1298 res.setSRID(getSRID()); 1299 1300 return res; 1301 } 1302 reverseInternal()1303 protected abstract Geometry reverseInternal(); 1304 1305 /** 1306 * Computes a <code>Geometry</code> representing the point-set which is 1307 * common to both this <code>Geometry</code> and the <code>other</code> Geometry. 1308 * <p> 1309 * The intersection of two geometries of different dimension produces a result 1310 * geometry of dimension less than or equal to the minimum dimension of the input 1311 * geometries. 1312 * The result geometry may be a heterogeneous {@link GeometryCollection}. 1313 * If the result is empty, it is an atomic geometry 1314 * with the dimension of the lowest input dimension. 1315 * <p> 1316 * Intersection of {@link GeometryCollection}s is supported 1317 * only for homogeneous collection types. 1318 * <p> 1319 * Non-empty heterogeneous {@link GeometryCollection} arguments are not supported. 1320 * 1321 * @param other the <code>Geometry</code> with which to compute the intersection 1322 * @return a Geometry representing the point-set common to the two <code>Geometry</code>s 1323 * @throws TopologyException if a robustness error occurs 1324 * @throws IllegalArgumentException if the argument is a non-empty heterogeneous <code>GeometryCollection</code> 1325 */ intersection(Geometry other)1326 public Geometry intersection(Geometry other) 1327 { 1328 return GeometryOverlay.intersection(this, other); 1329 } 1330 1331 /** 1332 * Computes a <code>Geometry</code> representing the point-set 1333 * which is contained in both this 1334 * <code>Geometry</code> and the <code>other</code> Geometry. 1335 * <p> 1336 * The union of two geometries of different dimension produces a result 1337 * geometry of dimension equal to the maximum dimension of the input 1338 * geometries. 1339 * The result geometry may be a heterogeneous 1340 * {@link GeometryCollection}. 1341 * If the result is empty, it is an atomic geometry 1342 * with the dimension of the highest input dimension. 1343 * <p> 1344 * Unioning {@link LineString}s has the effect of 1345 * <b>noding</b> and <b>dissolving</b> the input linework. In this context 1346 * "noding" means that there will be a node or endpoint in the result for 1347 * every endpoint or line segment crossing in the input. "Dissolving" means 1348 * that any duplicate (i.e. coincident) line segments or portions of line 1349 * segments will be reduced to a single line segment in the result. 1350 * If <b>merged</b> linework is required, the {@link LineMerger} 1351 * class can be used. 1352 * <p> 1353 * Non-empty {@link GeometryCollection} arguments are not supported. 1354 * 1355 * @param other 1356 * the <code>Geometry</code> with which to compute the union 1357 * @return a point-set combining the points of this <code>Geometry</code> and the 1358 * points of <code>other</code> 1359 * @throws TopologyException 1360 * if a robustness error occurs 1361 * @throws IllegalArgumentException 1362 * if either input is a non-empty GeometryCollection 1363 * @see LineMerger 1364 */ union(Geometry other)1365 public Geometry union(Geometry other) 1366 { 1367 return GeometryOverlay.union(this, other); 1368 } 1369 1370 /** 1371 * Computes a <code>Geometry</code> representing the closure of the point-set 1372 * of the points contained in this <code>Geometry</code> that are not contained in 1373 * the <code>other</code> Geometry. 1374 * <p> 1375 * If the result is empty, it is an atomic geometry 1376 * with the dimension of the left-hand input. 1377 * <p> 1378 * Non-empty {@link GeometryCollection} arguments are not supported. 1379 * 1380 *@param other the <code>Geometry</code> with which to compute the 1381 * difference 1382 *@return a Geometry representing the point-set difference of this <code>Geometry</code> with 1383 * <code>other</code> 1384 * @throws TopologyException if a robustness error occurs 1385 * @throws IllegalArgumentException if either input is a non-empty GeometryCollection 1386 */ difference(Geometry other)1387 public Geometry difference(Geometry other) 1388 { 1389 return GeometryOverlay.difference(this, other); 1390 } 1391 1392 /** 1393 * Computes a <code>Geometry </code> representing the closure of the point-set 1394 * which is the union of the points in this <code>Geometry</code> which are not 1395 * contained in the <code>other</code> Geometry, 1396 * with the points in the <code>other</code> Geometry not contained in this 1397 * <code>Geometry</code>. 1398 * If the result is empty, it is an atomic geometry 1399 * with the dimension of the highest input dimension. 1400 * <p> 1401 * Non-empty {@link GeometryCollection} arguments are not supported. 1402 * 1403 *@param other the <code>Geometry</code> with which to compute the symmetric 1404 * difference 1405 *@return a Geometry representing the point-set symmetric difference of this <code>Geometry</code> 1406 * with <code>other</code> 1407 * @throws TopologyException if a robustness error occurs 1408 * @throws IllegalArgumentException if either input is a non-empty GeometryCollection 1409 */ symDifference(Geometry other)1410 public Geometry symDifference(Geometry other) 1411 { 1412 return GeometryOverlay.symDifference(this, other); 1413 } 1414 1415 /** 1416 * Computes the union of all the elements of this geometry. 1417 * <p> 1418 * This method supports 1419 * {@link GeometryCollection}s 1420 * (which the other overlay operations currently do not). 1421 * <p> 1422 * The result obeys the following contract: 1423 * <ul> 1424 * <li>Unioning a set of {@link LineString}s has the effect of fully noding 1425 * and dissolving the linework. 1426 * <li>Unioning a set of {@link Polygon}s always 1427 * returns a {@link Polygonal} geometry (unlike {@link #union(Geometry)}, 1428 * which may return geometries of lower dimension if a topology collapse occurred). 1429 * </ul> 1430 * 1431 * @return the union geometry 1432 * @throws TopologyException if a robustness error occurs 1433 * 1434 * @see UnaryUnionOp 1435 */ union()1436 public Geometry union() { 1437 return GeometryOverlay.union(this); 1438 } 1439 1440 /** 1441 * Returns true if the two <code>Geometry</code>s are exactly equal, 1442 * up to a specified distance tolerance. 1443 * Two Geometries are exactly equal within a distance tolerance 1444 * if and only if: 1445 * <ul> 1446 * <li>they have the same structure 1447 * <li>they have the same values for their vertices, 1448 * within the given tolerance distance, in exactly the same order. 1449 * </ul> 1450 * This method does <i>not</i> 1451 * test the values of the <code>GeometryFactory</code>, the <code>SRID</code>, 1452 * or the <code>userData</code> fields. 1453 * <p> 1454 * To properly test equality between different geometries, 1455 * it is usually necessary to {@link #normalize()} them first. 1456 * 1457 * @param other the <code>Geometry</code> with which to compare this <code>Geometry</code> 1458 * @param tolerance distance at or below which two <code>Coordinate</code>s 1459 * are considered equal 1460 * @return <code>true</code> if this and the other <code>Geometry</code> 1461 * have identical structure and point values, up to the distance tolerance. 1462 * 1463 * @see #equalsExact(Geometry) 1464 * @see #normalize() 1465 * @see #norm() 1466 */ equalsExact(Geometry other, double tolerance)1467 public abstract boolean equalsExact(Geometry other, double tolerance); 1468 1469 /** 1470 * Returns true if the two <code>Geometry</code>s are exactly equal. 1471 * Two Geometries are exactly equal iff: 1472 * <ul> 1473 * <li>they have the same structure 1474 * <li>they have the same values for their vertices, 1475 * in exactly the same order. 1476 * </ul> 1477 * This provides a stricter test of equality than 1478 * {@link #equalsTopo(Geometry)}, which is more useful 1479 * in certain situations 1480 * (such as using geometries as keys in collections). 1481 * <p> 1482 * This method does <i>not</i> 1483 * test the values of the <code>GeometryFactory</code>, the <code>SRID</code>, 1484 * or the <code>userData</code> fields. 1485 * <p> 1486 * To properly test equality between different geometries, 1487 * it is usually necessary to {@link #normalize()} them first. 1488 * 1489 *@param other the <code>Geometry</code> with which to compare this <code>Geometry</code> 1490 *@return <code>true</code> if this and the other <code>Geometry</code> 1491 * have identical structure and point values. 1492 * 1493 * @see #equalsExact(Geometry, double) 1494 * @see #normalize() 1495 * @see #norm() 1496 */ equalsExact(Geometry other)1497 public boolean equalsExact(Geometry other) 1498 { 1499 return this == other || equalsExact(other, 0); 1500 } 1501 1502 /** 1503 * Tests whether two geometries are exactly equal 1504 * in their normalized forms. 1505 * This is a convenience method which creates normalized 1506 * versions of both geometries before computing 1507 * {@link #equalsExact(Geometry)}. 1508 * <p> 1509 * This method is relatively expensive to compute. 1510 * For maximum performance, the client 1511 * should instead perform normalization on the individual geometries 1512 * at an appropriate point during processing. 1513 * 1514 * @param g a Geometry 1515 * @return true if the input geometries are exactly equal in their normalized form 1516 */ equalsNorm(Geometry g)1517 public boolean equalsNorm(Geometry g) 1518 { 1519 if (g == null) return false; 1520 return norm().equalsExact(g.norm()); 1521 } 1522 1523 1524 /** 1525 * Performs an operation with or on this <code>Geometry</code>'s 1526 * coordinates. 1527 * If this method modifies any coordinate values, 1528 * {@link #geometryChanged} must be called to update the geometry state. 1529 * Note that you cannot use this method to 1530 * modify this Geometry if its underlying CoordinateSequence's #get method 1531 * returns a copy of the Coordinate, rather than the actual Coordinate stored 1532 * (if it even stores Coordinate objects at all). 1533 * 1534 *@param filter the filter to apply to this <code>Geometry</code>'s 1535 * coordinates 1536 */ apply(CoordinateFilter filter)1537 public abstract void apply(CoordinateFilter filter); 1538 1539 /** 1540 * Performs an operation on the coordinates in this <code>Geometry</code>'s 1541 * {@link CoordinateSequence}s. 1542 * If the filter reports that a coordinate value has been changed, 1543 * {@link #geometryChanged} will be called automatically. 1544 * 1545 *@param filter the filter to apply 1546 */ apply(CoordinateSequenceFilter filter)1547 public abstract void apply(CoordinateSequenceFilter filter); 1548 1549 /** 1550 * Performs an operation with or on this <code>Geometry</code> and its 1551 * subelement <code>Geometry</code>s (if any). 1552 * Only GeometryCollections and subclasses 1553 * have subelement Geometry's. 1554 * 1555 *@param filter the filter to apply to this <code>Geometry</code> (and 1556 * its children, if it is a <code>GeometryCollection</code>). 1557 */ apply(GeometryFilter filter)1558 public abstract void apply(GeometryFilter filter); 1559 1560 /** 1561 * Performs an operation with or on this Geometry and its 1562 * component Geometry's. Only GeometryCollections and 1563 * Polygons have component Geometry's; for Polygons they are the LinearRings 1564 * of the shell and holes. 1565 * 1566 *@param filter the filter to apply to this <code>Geometry</code>. 1567 */ apply(GeometryComponentFilter filter)1568 public abstract void apply(GeometryComponentFilter filter); 1569 1570 /** 1571 * Creates and returns a full copy of this {@link Geometry} object 1572 * (including all coordinates contained by it). 1573 * Subclasses are responsible for overriding this method and copying 1574 * their internal data. Overrides should call this method first. 1575 * 1576 * @return a clone of this instance 1577 * @deprecated 1578 */ clone()1579 public Object clone() { 1580 try { 1581 Geometry clone = (Geometry) super.clone(); 1582 if (clone.envelope != null) { clone.envelope = new Envelope(clone.envelope); } 1583 return clone; 1584 } 1585 catch (CloneNotSupportedException e) { 1586 Assert.shouldNeverReachHere(); 1587 return null; 1588 } 1589 } 1590 1591 /** 1592 * Creates a deep copy of this {@link Geometry} object. 1593 * Coordinate sequences contained in it are copied. 1594 * All instance fields are copied 1595 * (i.e. <code>envelope</code>, <tt>SRID</tt> and <tt>userData</tt>). 1596 * <p> 1597 * <b>NOTE:</b> the userData object reference (if present) is copied, 1598 * but the value itself is not copied. 1599 * If a deep copy is required this must be performed by the caller. 1600 * 1601 * @return a deep copy of this geometry 1602 */ copy()1603 public Geometry copy() { 1604 Geometry copy = copyInternal(); 1605 copy.envelope = envelope == null ? null : envelope.copy(); 1606 copy.SRID = this.SRID; 1607 copy.userData = this.userData; 1608 return copy; 1609 } 1610 1611 /** 1612 * An internal method to copy subclass-specific geometry data. 1613 * 1614 * @return a copy of the target geometry object. 1615 */ copyInternal()1616 protected abstract Geometry copyInternal(); 1617 1618 /** 1619 * Converts this <code>Geometry</code> to <b>normal form</b> (or <b> 1620 * canonical form</b> ). Normal form is a unique representation for <code>Geometry</code> 1621 * s. It can be used to test whether two <code>Geometry</code>s are equal 1622 * in a way that is independent of the ordering of the coordinates within 1623 * them. Normal form equality is a stronger condition than topological 1624 * equality, but weaker than pointwise equality. The definitions for normal 1625 * form use the standard lexicographical ordering for coordinates. "Sorted in 1626 * order of coordinates" means the obvious extension of this ordering to 1627 * sequences of coordinates. 1628 * <p> 1629 * NOTE that this method mutates the value of this geometry in-place. 1630 * If this is not safe and/or wanted, the geometry should be 1631 * cloned prior to normalization. 1632 */ normalize()1633 public abstract void normalize(); 1634 1635 /** 1636 * Creates a new Geometry which is a normalized 1637 * copy of this Geometry. 1638 * 1639 * @return a normalized copy of this geometry. 1640 * @see #normalize() 1641 */ norm()1642 public Geometry norm() 1643 { 1644 Geometry copy = copy(); 1645 copy.normalize(); 1646 return copy; 1647 } 1648 1649 /** 1650 * Returns whether this <code>Geometry</code> is greater than, equal to, 1651 * or less than another <code>Geometry</code>. <P> 1652 * 1653 * If their classes are different, they are compared using the following 1654 * ordering: 1655 * <UL> 1656 * <LI> Point (lowest) 1657 * <LI> MultiPoint 1658 * <LI> LineString 1659 * <LI> LinearRing 1660 * <LI> MultiLineString 1661 * <LI> Polygon 1662 * <LI> MultiPolygon 1663 * <LI> GeometryCollection (highest) 1664 * </UL> 1665 * If the two <code>Geometry</code>s have the same class, their first 1666 * elements are compared. If those are the same, the second elements are 1667 * compared, etc. 1668 * 1669 *@param o a <code>Geometry</code> with which to compare this <code>Geometry</code> 1670 *@return a positive number, 0, or a negative number, depending on whether 1671 * this object is greater than, equal to, or less than <code>o</code>, as 1672 * defined in "Normal Form For Geometry" in the JTS Technical 1673 * Specifications 1674 */ compareTo(Object o)1675 public int compareTo(Object o) { 1676 Geometry other = (Geometry) o; 1677 if (getTypeCode() != other.getTypeCode()) { 1678 return getTypeCode() - other.getTypeCode(); 1679 } 1680 if (isEmpty() && other.isEmpty()) { 1681 return 0; 1682 } 1683 if (isEmpty()) { 1684 return -1; 1685 } 1686 if (other.isEmpty()) { 1687 return 1; 1688 } 1689 return compareToSameClass(o); 1690 } 1691 1692 /** 1693 * Returns whether this <code>Geometry</code> is greater than, equal to, 1694 * or less than another <code>Geometry</code>, 1695 * using the given {@link CoordinateSequenceComparator}. 1696 * <P> 1697 * 1698 * If their classes are different, they are compared using the following 1699 * ordering: 1700 * <UL> 1701 * <LI> Point (lowest) 1702 * <LI> MultiPoint 1703 * <LI> LineString 1704 * <LI> LinearRing 1705 * <LI> MultiLineString 1706 * <LI> Polygon 1707 * <LI> MultiPolygon 1708 * <LI> GeometryCollection (highest) 1709 * </UL> 1710 * If the two <code>Geometry</code>s have the same class, their first 1711 * elements are compared. If those are the same, the second elements are 1712 * compared, etc. 1713 * 1714 *@param o a <code>Geometry</code> with which to compare this <code>Geometry</code> 1715 *@param comp a <code>CoordinateSequenceComparator</code> 1716 * 1717 *@return a positive number, 0, or a negative number, depending on whether 1718 * this object is greater than, equal to, or less than <code>o</code>, as 1719 * defined in "Normal Form For Geometry" in the JTS Technical 1720 * Specifications 1721 */ compareTo(Object o, CoordinateSequenceComparator comp)1722 public int compareTo(Object o, CoordinateSequenceComparator comp) { 1723 Geometry other = (Geometry) o; 1724 if (getTypeCode() != other.getTypeCode()) { 1725 return getTypeCode() - other.getTypeCode(); 1726 } 1727 if (isEmpty() && other.isEmpty()) { 1728 return 0; 1729 } 1730 if (isEmpty()) { 1731 return -1; 1732 } 1733 if (other.isEmpty()) { 1734 return 1; 1735 } 1736 return compareToSameClass(o, comp); 1737 } 1738 1739 /** 1740 * Returns whether the two <code>Geometry</code>s are equal, from the point 1741 * of view of the <code>equalsExact</code> method. Called by <code>equalsExact</code> 1742 * . In general, two <code>Geometry</code> classes are considered to be 1743 * "equivalent" only if they are the same class. An exception is <code>LineString</code> 1744 * , which is considered to be equivalent to its subclasses. 1745 * 1746 *@param other the <code>Geometry</code> with which to compare this <code>Geometry</code> 1747 * for equality 1748 *@return <code>true</code> if the classes of the two <code>Geometry</code> 1749 * s are considered to be equal by the <code>equalsExact</code> method. 1750 */ isEquivalentClass(Geometry other)1751 protected boolean isEquivalentClass(Geometry other) { 1752 return this.getClass().getName().equals(other.getClass().getName()); 1753 } 1754 1755 /** 1756 * Throws an exception if <code>g</code>'s type is a <code>GeometryCollection</code>. 1757 * (Its subclasses do not trigger an exception). 1758 * 1759 *@param g the <code>Geometry</code> to check 1760 *@throws IllegalArgumentException if <code>g</code> is a <code>GeometryCollection</code> 1761 * but not one of its subclasses 1762 */ checkNotGeometryCollection(Geometry g)1763 static void checkNotGeometryCollection(Geometry g) { 1764 if (g.isGeometryCollection()) { 1765 throw new IllegalArgumentException("Operation does not support GeometryCollection arguments"); 1766 } 1767 } 1768 1769 /** 1770 * Tests whether this is an instance of a general {@link GeometryCollection}, 1771 * rather than a homogeneous subclass. 1772 * 1773 * @return true if this is a heterogeneous GeometryCollection 1774 */ isGeometryCollection()1775 protected boolean isGeometryCollection() 1776 { 1777 return getTypeCode() == TYPECODE_GEOMETRYCOLLECTION; 1778 } 1779 1780 /** 1781 * Returns the minimum and maximum x and y values in this <code>Geometry</code> 1782 * , or a null <code>Envelope</code> if this <code>Geometry</code> is empty. 1783 * Unlike <code>getEnvelopeInternal</code>, this method calculates the <code>Envelope</code> 1784 * each time it is called; <code>getEnvelopeInternal</code> caches the result 1785 * of this method. 1786 * 1787 *@return this <code>Geometry</code>s bounding box; if the <code>Geometry</code> 1788 * is empty, <code>Envelope#isNull</code> will return <code>true</code> 1789 */ computeEnvelopeInternal()1790 protected abstract Envelope computeEnvelopeInternal(); 1791 1792 /** 1793 * Returns whether this <code>Geometry</code> is greater than, equal to, 1794 * or less than another <code>Geometry</code> having the same class. 1795 * 1796 *@param o a <code>Geometry</code> having the same class as this <code>Geometry</code> 1797 *@return a positive number, 0, or a negative number, depending on whether 1798 * this object is greater than, equal to, or less than <code>o</code>, as 1799 * defined in "Normal Form For Geometry" in the JTS Technical 1800 * Specifications 1801 */ compareToSameClass(Object o)1802 protected abstract int compareToSameClass(Object o); 1803 1804 /** 1805 * Returns whether this <code>Geometry</code> is greater than, equal to, 1806 * or less than another <code>Geometry</code> of the same class. 1807 * using the given {@link CoordinateSequenceComparator}. 1808 * 1809 *@param o a <code>Geometry</code> having the same class as this <code>Geometry</code> 1810 *@param comp a <code>CoordinateSequenceComparator</code> 1811 *@return a positive number, 0, or a negative number, depending on whether 1812 * this object is greater than, equal to, or less than <code>o</code>, as 1813 * defined in "Normal Form For Geometry" in the JTS Technical 1814 * Specifications 1815 */ compareToSameClass(Object o, CoordinateSequenceComparator comp)1816 protected abstract int compareToSameClass(Object o, CoordinateSequenceComparator comp); 1817 1818 /** 1819 * Returns the first non-zero result of <code>compareTo</code> encountered as 1820 * the two <code>Collection</code>s are iterated over. If, by the time one of 1821 * the iterations is complete, no non-zero result has been encountered, 1822 * returns 0 if the other iteration is also complete. If <code>b</code> 1823 * completes before <code>a</code>, a positive number is returned; if a 1824 * before b, a negative number. 1825 * 1826 *@param a a <code>Collection</code> of <code>Comparable</code>s 1827 *@param b a <code>Collection</code> of <code>Comparable</code>s 1828 *@return the first non-zero <code>compareTo</code> result, if any; 1829 * otherwise, zero 1830 */ compare(Collection a, Collection b)1831 protected int compare(Collection a, Collection b) { 1832 Iterator i = a.iterator(); 1833 Iterator j = b.iterator(); 1834 while (i.hasNext() && j.hasNext()) { 1835 Comparable aElement = (Comparable) i.next(); 1836 Comparable bElement = (Comparable) j.next(); 1837 int comparison = aElement.compareTo(bElement); 1838 if (comparison != 0) { 1839 return comparison; 1840 } 1841 } 1842 if (i.hasNext()) { 1843 return 1; 1844 } 1845 if (j.hasNext()) { 1846 return -1; 1847 } 1848 return 0; 1849 } 1850 equal(Coordinate a, Coordinate b, double tolerance)1851 protected boolean equal(Coordinate a, Coordinate b, double tolerance) { 1852 if (tolerance == 0) { return a.equals(b); } 1853 return a.distance(b) <= tolerance; 1854 } 1855 getTypeCode()1856 abstract protected int getTypeCode(); 1857 createPointFromInternalCoord(Coordinate coord, Geometry exemplar)1858 private Point createPointFromInternalCoord(Coordinate coord, Geometry exemplar) 1859 { 1860 exemplar.getPrecisionModel().makePrecise(coord); 1861 return exemplar.getFactory().createPoint(coord); 1862 } 1863 1864 1865 } 1866 1867