Class Geometry

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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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, maxx miny,
594	* maxx maxy, minx maxy, minx miny).
595	* </ul>
596	*
597	*@return a Geometry representing the envelope of this Geometry
598	*
599	* @see GeometryFactory#toGeometry(Envelope)
600	*/
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	*/
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	*/
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	*/
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>[FFFF***]</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	*/
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>[FT***]</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	*/
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	*/
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>[TT*****]</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	*/
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>[TFF**]</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	*/
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	*/
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>[TTT]</code> (for two points or two surfaces)
893	* or <code>[1TT]</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	*/
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>[*TFF*]</code>
921	* <li><code>[***TFF*]</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	*/
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>[TFF**]</code>
974	* <li><code>[TFF**]</code>
975	* <li><code>[*FTF***]</code>
976	* <li><code>[*FTF***]</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	*/
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	*/
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	*/
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	*/
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>TFFFF</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	*/
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	*/
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	*/
1131	public int hashCode()
1132	{
1133	return getEnvelopeInternal().hashCode();
1134	}
1135
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	*/
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	*/
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	*/
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	*/
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	*/
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	*/
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
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	*/
1326	public Geometry intersection(Geometry other)
1327	{
1328	/**
1329	* TODO: MD - add optimization for P-A case using Point-In-Polygon
1330	*/
1331	// special case: if one input is empty ==> empty
1332	if (this.isEmpty() \|\| other.isEmpty())
1333	return OverlayOp.createEmptyResult(OverlayOp.INTERSECTION, this, other, factory);
1334
1335	// compute for GCs
1336	// (An inefficient algorithm, but will work)
1337	// TODO: improve efficiency of computation for GCs
1338	if (this.isGeometryCollection()) {
1339	final Geometry g2 = other;
1340	return GeometryCollectionMapper.map(
1341	(GeometryCollection) this,
1342	new GeometryMapper.MapOp() {
1343	public Geometry map(Geometry g) {
1344	return g.intersection(g2);
1345	}
1346	});
1347	}
1348
1349	// No longer needed since GCs are handled by previous code
1350	//checkNotGeometryCollection(this);
1351	//checkNotGeometryCollection(other);
1352	return SnapIfNeededOverlayOp.overlayOp(this, other, OverlayOp.INTERSECTION);
1353	}
1354
1355	/**
1356	* Computes a <code>Geometry</code> representing the point-set
1357	* which is contained in both this
1358	* <code>Geometry</code> and the <code>other</code> Geometry.
1359	* <p>
1360	* The union of two geometries of different dimension produces a result
1361	* geometry of dimension equal to the maximum dimension of the input
1362	* geometries.
1363	* The result geometry may be a heterogeneous
1364	* {@link GeometryCollection}.
1365	* If the result is empty, it is an atomic geometry
1366	* with the dimension of the highest input dimension.
1367	* <p>
1368	* Unioning {@link LineString}s has the effect of
1369	* <b>noding</b> and <b>dissolving</b> the input linework. In this context
1370	* "noding" means that there will be a node or endpoint in the result for
1371	* every endpoint or line segment crossing in the input. "Dissolving" means
1372	* that any duplicate (i.e. coincident) line segments or portions of line
1373	* segments will be reduced to a single line segment in the result.
1374	* If <b>merged</b> linework is required, the {@link LineMerger}
1375	* class can be used.
1376	* <p>
1377	* Non-empty {@link GeometryCollection} arguments are not supported.
1378	*
1379	* @param other
1380	* the <code>Geometry</code> with which to compute the union
1381	* @return a point-set combining the points of this <code>Geometry</code> and the
1382	* points of <code>other</code>
1383	* @throws TopologyException
1384	* if a robustness error occurs
1385	* @throws IllegalArgumentException
1386	* if either input is a non-empty GeometryCollection
1387	* @see LineMerger
1388	*/
1389	public Geometry union(Geometry other)
1390	{
1391	// handle empty geometry cases
1392	if (this.isEmpty() \|\| other.isEmpty()) {
1393	if (this.isEmpty() && other.isEmpty())
1394	return OverlayOp.createEmptyResult(OverlayOp.UNION, this, other, factory);
1395
1396	// special case: if either input is empty ==> other input
1397	if (this.isEmpty()) return other.copy();
1398	if (other.isEmpty()) return copy();
1399	}
1400
1401	// TODO: optimize if envelopes of geometries do not intersect
1402
1403	checkNotGeometryCollection(this);
1404	checkNotGeometryCollection(other);
1405	return SnapIfNeededOverlayOp.overlayOp(this, other, OverlayOp.UNION);
1406	}
1407
1408	/**
1409	* Computes a <code>Geometry</code> representing the closure of the point-set
1410	* of the points contained in this <code>Geometry</code> that are not contained in
1411	* the <code>other</code> Geometry.
1412	* <p>
1413	* If the result is empty, it is an atomic geometry
1414	* with the dimension of the left-hand input.
1415	* <p>
1416	* Non-empty {@link GeometryCollection} arguments are not supported.
1417	*
1418	*@param other the <code>Geometry</code> with which to compute the
1419	* difference
1420	*@return a Geometry representing the point-set difference of this <code>Geometry</code> with
1421	* <code>other</code>
1422	* @throws TopologyException if a robustness error occurs
1423	* @throws IllegalArgumentException if either input is a non-empty GeometryCollection
1424	*/
1425	public Geometry difference(Geometry other)
1426	{
1427	// special case: if A.isEmpty ==> empty; if B.isEmpty ==> A
1428	if (this.isEmpty()) return OverlayOp.createEmptyResult(OverlayOp.DIFFERENCE, this, other, factory);
1429	if (other.isEmpty()) return copy();
1430
1431	checkNotGeometryCollection(this);
1432	checkNotGeometryCollection(other);
1433	return SnapIfNeededOverlayOp.overlayOp(this, other, OverlayOp.DIFFERENCE);
1434	}
1435
1436	/**
1437	* Computes a <code>Geometry </code> representing the closure of the point-set
1438	* which is the union of the points in this <code>Geometry</code> which are not
1439	* contained in the <code>other</code> Geometry,
1440	* with the points in the <code>other</code> Geometry not contained in this
1441	* <code>Geometry</code>.
1442	* If the result is empty, it is an atomic geometry
1443	* with the dimension of the highest input dimension.
1444	* <p>
1445	* Non-empty {@link GeometryCollection} arguments are not supported.
1446	*
1447	*@param other the <code>Geometry</code> with which to compute the symmetric
1448	* difference
1449	*@return a Geometry representing the point-set symmetric difference of this <code>Geometry</code>
1450	* with <code>other</code>
1451	* @throws TopologyException if a robustness error occurs
1452	* @throws IllegalArgumentException if either input is a non-empty GeometryCollection
1453	*/
1454	public Geometry symDifference(Geometry other)
1455	{
1456	// handle empty geometry cases
1457	if (this.isEmpty() \|\| other.isEmpty()) {
1458	// both empty - check dimensions
1459	if (this.isEmpty() && other.isEmpty())
1460	return OverlayOp.createEmptyResult(OverlayOp.SYMDIFFERENCE, this, other, factory);
1461
1462	// special case: if either input is empty ==> result = other arg
1463	if (this.isEmpty()) return other.copy();
1464	if (other.isEmpty()) return copy();
1465	}
1466
1467	checkNotGeometryCollection(this);
1468	checkNotGeometryCollection(other);
1469	return SnapIfNeededOverlayOp.overlayOp(this, other, OverlayOp.SYMDIFFERENCE);
1470	}
1471
1472	/**
1473	* Computes the union of all the elements of this geometry.
1474	* <p>
1475	* This method supports
1476	* {@link GeometryCollection}s
1477	* (which the other overlay operations currently do not).
1478	* <p>
1479	* The result obeys the following contract:
1480	* <ul>
1481	* <li>Unioning a set of {@link LineString}s has the effect of fully noding
1482	* and dissolving the linework.
1483	* <li>Unioning a set of {@link Polygon}s always
1484	* returns a {@link Polygonal} geometry (unlike {@link #union(Geometry)},
1485	* which may return geometries of lower dimension if a topology collapse occurred).
1486	* </ul>
1487	*
1488	* @return the union geometry
1489	* @throws TopologyException if a robustness error occurs
1490	*
1491	* @see UnaryUnionOp
1492	*/
1493	public Geometry union() {
1494	return UnaryUnionOp.union(this);
1495	}
1496
1497	/**
1498	* Returns true if the two <code>Geometry</code>s are exactly equal,
1499	* up to a specified distance tolerance.
1500	* Two Geometries are exactly equal within a distance tolerance
1501	* if and only if:
1502	* <ul>
1503	* <li>they have the same structure
1504	* <li>they have the same values for their vertices,
1505	* within the given tolerance distance, in exactly the same order.
1506	* </ul>
1507	* This method does <i>not</i>
1508	* test the values of the <code>GeometryFactory</code>, the <code>SRID</code>,
1509	* or the <code>userData</code> fields.
1510	* <p>
1511	* To properly test equality between different geometries,
1512	* it is usually necessary to {@link #normalize()} them first.
1513	*
1514	* @param other the <code>Geometry</code> with which to compare this <code>Geometry</code>
1515	* @param tolerance distance at or below which two <code>Coordinate</code>s
1516	* are considered equal
1517	* @return <code>true</code> if this and the other <code>Geometry</code>
1518	* have identical structure and point values, up to the distance tolerance.
1519	*
1520	* @see #equalsExact(Geometry)
1521	* @see #normalize()
1522	* @see #norm()
1523	*/
1524	public abstract boolean equalsExact(Geometry other, double tolerance);
1525
1526	/**
1527	* Returns true if the two <code>Geometry</code>s are exactly equal.
1528	* Two Geometries are exactly equal iff:
1529	* <ul>
1530	* <li>they have the same structure
1531	* <li>they have the same values for their vertices,
1532	* in exactly the same order.
1533	* </ul>
1534	* This provides a stricter test of equality than
1535	* {@link #equalsTopo(Geometry)}, which is more useful
1536	* in certain situations
1537	* (such as using geometries as keys in collections).
1538	* <p>
1539	* This method does <i>not</i>
1540	* test the values of the <code>GeometryFactory</code>, the <code>SRID</code>,
1541	* or the <code>userData</code> fields.
1542	* <p>
1543	* To properly test equality between different geometries,
1544	* it is usually necessary to {@link #normalize()} them first.
1545	*
1546	*@param other the <code>Geometry</code> with which to compare this <code>Geometry</code>
1547	*@return <code>true</code> if this and the other <code>Geometry</code>
1548	* have identical structure and point values.
1549	*
1550	* @see #equalsExact(Geometry, double)
1551	* @see #normalize()
1552	* @see #norm()
1553	*/
1554	public boolean equalsExact(Geometry other)
1555	{
1556	return this == other \|\| equalsExact(other, 0);
1557	}
1558
1559	/**
1560	* Tests whether two geometries are exactly equal
1561	* in their normalized forms.
1562	* This is a convenience method which creates normalized
1563	* versions of both geometries before computing
1564	* {@link #equalsExact(Geometry)}.
1565	* <p>
1566	* This method is relatively expensive to compute.
1567	* For maximum performance, the client
1568	* should instead perform normalization on the individual geometries
1569	* at an appropriate point during processing.
1570	*
1571	* @param g a Geometry
1572	* @return true if the input geometries are exactly equal in their normalized form
1573	*/
1574	public boolean equalsNorm(Geometry g)
1575	{
1576	if (g == null) return false;
1577	return norm().equalsExact(g.norm());
1578	}
1579
1580
1581	/**
1582	* Performs an operation with or on this <code>Geometry</code>'s
1583	* coordinates.
1584	* If this method modifies any coordinate values,
1585	* {@link #geometryChanged} must be called to update the geometry state.
1586	* Note that you cannot use this method to
1587	* modify this Geometry if its underlying CoordinateSequence's #get method
1588	* returns a copy of the Coordinate, rather than the actual Coordinate stored
1589	* (if it even stores Coordinate objects at all).
1590	*
1591	*@param filter the filter to apply to this <code>Geometry</code>'s
1592	* coordinates
1593	*/
1594	public abstract void apply(CoordinateFilter filter);
1595
1596	/**
1597	* Performs an operation on the coordinates in this <code>Geometry</code>'s
1598	* {@link CoordinateSequence}s.
1599	* If the filter reports that a coordinate value has been changed,
1600	* {@link #geometryChanged} will be called automatically.
1601	*
1602	*@param filter the filter to apply
1603	*/
1604	public abstract void apply(CoordinateSequenceFilter filter);
1605
1606	/**
1607	* Performs an operation with or on this <code>Geometry</code> and its
1608	* subelement <code>Geometry</code>s (if any).
1609	* Only GeometryCollections and subclasses
1610	* have subelement Geometry's.
1611	*
1612	*@param filter the filter to apply to this <code>Geometry</code> (and
1613	* its children, if it is a <code>GeometryCollection</code>).
1614	*/
1615	public abstract void apply(GeometryFilter filter);
1616
1617	/**
1618	* Performs an operation with or on this Geometry and its
1619	* component Geometry's. Only GeometryCollections and
1620	* Polygons have component Geometry's; for Polygons they are the LinearRings
1621	* of the shell and holes.
1622	*
1623	*@param filter the filter to apply to this <code>Geometry</code>.
1624	*/
1625	public abstract void apply(GeometryComponentFilter filter);
1626
1627	/**
1628	* Creates and returns a full copy of this {@link Geometry} object
1629	* (including all coordinates contained by it).
1630	* Subclasses are responsible for overriding this method and copying
1631	* their internal data. Overrides should call this method first.
1632	*
1633	* @return a clone of this instance
1634	* @deprecated
1635	*/
1636	public Object clone() {
1637	try {
1638	Geometry clone = (Geometry) super.clone();
1639	if (clone.envelope != null) { clone.envelope = new Envelope(clone.envelope); }
1640	return clone;
1641	}
1642	catch (CloneNotSupportedException e) {
1643	Assert.shouldNeverReachHere();
1644	return null;
1645	}
1646	}
1647
1648	/**
1649	* Creates a deep copy of this {@link Geometry} object.
1650	* Coordinate sequences contained in it are copied.
1651	* All instance fields are copied
1652	* (i.e. <code>envelope</code>, <tt>SRID</tt> and <tt>userData</tt>).
1653	* <p>
1654	* <b>NOTE:</b> the userData object reference (if present) is copied,
1655	* but the value itself is not copied.
1656	* If a deep copy is required this must be performed by the caller.
1657	*
1658	* @return a deep copy of this geometry
1659	*/
1660	public Geometry copy() {
1661	Geometry copy = copyInternal();
1662	copy.envelope = envelope == null ? null : envelope.copy();
1663	copy.SRID = this.SRID;
1664	copy.userData = this.userData;
1665	return copy;
1666	}
1667
1668	/**
1669	* An internal method to copy subclass-specific geometry data.
1670	*
1671	* @return a copy of the target geometry object.
1672	*/
1673	protected abstract Geometry copyInternal();
1674
1675	/**
1676	* Converts this <code>Geometry</code> to <b>normal form</b> (or <b>
1677	* canonical form</b> ). Normal form is a unique representation for <code>Geometry</code>
1678	* s. It can be used to test whether two <code>Geometry</code>s are equal
1679	* in a way that is independent of the ordering of the coordinates within
1680	* them. Normal form equality is a stronger condition than topological
1681	* equality, but weaker than pointwise equality. The definitions for normal
1682	* form use the standard lexicographical ordering for coordinates. "Sorted in
1683	* order of coordinates" means the obvious extension of this ordering to
1684	* sequences of coordinates.
1685	* <p>
1686	* NOTE that this method mutates the value of this geometry in-place.
1687	* If this is not safe and/or wanted, the geometry should be
1688	* cloned prior to normalization.
1689	*/
1690	public abstract void normalize();
1691
1692	/**
1693	* Creates a new Geometry which is a normalized
1694	* copy of this Geometry.
1695	*
1696	* @return a normalized copy of this geometry.
1697	* @see #normalize()
1698	*/
1699	public Geometry norm()
1700	{
1701	Geometry copy = copy();
1702	copy.normalize();
1703	return copy;
1704	}
1705
1706	/**
1707	* Returns whether this <code>Geometry</code> is greater than, equal to,
1708	* or less than another <code>Geometry</code>. <P>
1709	*
1710	* If their classes are different, they are compared using the following
1711	* ordering:
1712	* <UL>
1713	* <LI> Point (lowest)
1714	* <LI> MultiPoint
1715	* <LI> LineString
1716	* <LI> LinearRing
1717	* <LI> MultiLineString
1718	* <LI> Polygon
1719	* <LI> MultiPolygon
1720	* <LI> GeometryCollection (highest)
1721	* </UL>
1722	* If the two <code>Geometry</code>s have the same class, their first
1723	* elements are compared. If those are the same, the second elements are
1724	* compared, etc.
1725	*
1726	*@param o a <code>Geometry</code> with which to compare this <code>Geometry</code>
1727	*@return a positive number, 0, or a negative number, depending on whether
1728	* this object is greater than, equal to, or less than <code>o</code>, as
1729	* defined in "Normal Form For Geometry" in the JTS Technical
1730	* Specifications
1731	*/
1732	public int compareTo(Object o) {
1733	Geometry other = (Geometry) o;
1734	if (getTypeCode() != other.getTypeCode()) {
1735	return getTypeCode() - other.getTypeCode();
1736	}
1737	if (isEmpty() && other.isEmpty()) {
1738	return 0;
1739	}
1740	if (isEmpty()) {
1741	return -1;
1742	}
1743	if (other.isEmpty()) {
1744	return 1;
1745	}
1746	return compareToSameClass(o);
1747	}
1748
1749	/**
1750	* Returns whether this <code>Geometry</code> is greater than, equal to,
1751	* or less than another <code>Geometry</code>,
1752	* using the given {@link CoordinateSequenceComparator}.
1753	* <P>
1754	*
1755	* If their classes are different, they are compared using the following
1756	* ordering:
1757	* <UL>
1758	* <LI> Point (lowest)
1759	* <LI> MultiPoint
1760	* <LI> LineString
1761	* <LI> LinearRing
1762	* <LI> MultiLineString
1763	* <LI> Polygon
1764	* <LI> MultiPolygon
1765	* <LI> GeometryCollection (highest)
1766	* </UL>
1767	* If the two <code>Geometry</code>s have the same class, their first
1768	* elements are compared. If those are the same, the second elements are
1769	* compared, etc.
1770	*
1771	*@param o a <code>Geometry</code> with which to compare this <code>Geometry</code>
1772	*@param comp a <code>CoordinateSequenceComparator</code>
1773	*
1774	*@return a positive number, 0, or a negative number, depending on whether
1775	* this object is greater than, equal to, or less than <code>o</code>, as
1776	* defined in "Normal Form For Geometry" in the JTS Technical
1777	* Specifications
1778	*/
1779	public int compareTo(Object o, CoordinateSequenceComparator comp) {
1780	Geometry other = (Geometry) o;
1781	if (getTypeCode() != other.getTypeCode()) {
1782	return getTypeCode() - other.getTypeCode();
1783	}
1784	if (isEmpty() && other.isEmpty()) {
1785	return 0;
1786	}
1787	if (isEmpty()) {
1788	return -1;
1789	}
1790	if (other.isEmpty()) {
1791	return 1;
1792	}
1793	return compareToSameClass(o, comp);
1794	}
1795
1796	/**
1797	* Returns whether the two <code>Geometry</code>s are equal, from the point
1798	* of view of the <code>equalsExact</code> method. Called by <code>equalsExact</code>
1799	* . In general, two <code>Geometry</code> classes are considered to be
1800	* "equivalent" only if they are the same class. An exception is <code>LineString</code>
1801	* , which is considered to be equivalent to its subclasses.
1802	*
1803	*@param other the <code>Geometry</code> with which to compare this <code>Geometry</code>
1804	* for equality
1805	*@return <code>true</code> if the classes of the two <code>Geometry</code>
1806	* s are considered to be equal by the <code>equalsExact</code> method.
1807	*/
1808	protected boolean isEquivalentClass(Geometry other) {
1809	return this.getClass().getName().equals(other.getClass().getName());
1810	}
1811
1812	/**
1813	* Throws an exception if <code>g</code>'s type is a <code>GeometryCollection</code>.
1814	* (Its subclasses do not trigger an exception).
1815	*
1816	*@param g the <code>Geometry</code> to check
1817	*@throws IllegalArgumentException if <code>g</code> is a <code>GeometryCollection</code>
1818	* but not one of its subclasses
1819	*/
1820	protected static void checkNotGeometryCollection(Geometry g) {
1821	if (g.isGeometryCollection()) {
1822	throw new IllegalArgumentException("Operation does not support GeometryCollection arguments");
1823	}
1824	}
1825
1826	/**
1827	* Tests whether this is an instance of a general {@link GeometryCollection},
1828	* rather than a homogeneous subclass.
1829	*
1830	* @return true if this is a heterogeneous GeometryCollection
1831	*/
1832	protected boolean isGeometryCollection()
1833	{
1834	return getTypeCode() == TYPECODE_GEOMETRYCOLLECTION;
1835	}
1836
1837	/**
1838	* Returns the minimum and maximum x and y values in this <code>Geometry</code>
1839	* , or a null <code>Envelope</code> if this <code>Geometry</code> is empty.
1840	* Unlike <code>getEnvelopeInternal</code>, this method calculates the <code>Envelope</code>
1841	* each time it is called; <code>getEnvelopeInternal</code> caches the result
1842	* of this method.
1843	*
1844	*@return this <code>Geometry</code>s bounding box; if the <code>Geometry</code>
1845	* is empty, <code>Envelope#isNull</code> will return <code>true</code>
1846	*/
1847	protected abstract Envelope computeEnvelopeInternal();
1848
1849	/**
1850	* Returns whether this <code>Geometry</code> is greater than, equal to,
1851	* or less than another <code>Geometry</code> having the same class.
1852	*
1853	*@param o a <code>Geometry</code> having the same class as this <code>Geometry</code>
1854	*@return a positive number, 0, or a negative number, depending on whether
1855	* this object is greater than, equal to, or less than <code>o</code>, as
1856	* defined in "Normal Form For Geometry" in the JTS Technical
1857	* Specifications
1858	*/
1859	protected abstract int compareToSameClass(Object o);
1860
1861	/**
1862	* Returns whether this <code>Geometry</code> is greater than, equal to,
1863	* or less than another <code>Geometry</code> of the same class.
1864	* using the given {@link CoordinateSequenceComparator}.
1865	*
1866	*@param o a <code>Geometry</code> having the same class as this <code>Geometry</code>
1867	*@param comp a <code>CoordinateSequenceComparator</code>
1868	*@return a positive number, 0, or a negative number, depending on whether
1869	* this object is greater than, equal to, or less than <code>o</code>, as
1870	* defined in "Normal Form For Geometry" in the JTS Technical
1871	* Specifications
1872	*/
1873	protected abstract int compareToSameClass(Object o, CoordinateSequenceComparator comp);
1874
1875	/**
1876	* Returns the first non-zero result of <code>compareTo</code> encountered as
1877	* the two <code>Collection</code>s are iterated over. If, by the time one of
1878	* the iterations is complete, no non-zero result has been encountered,
1879	* returns 0 if the other iteration is also complete. If <code>b</code>
1880	* completes before <code>a</code>, a positive number is returned; if a
1881	* before b, a negative number.
1882	*
1883	*@param a a <code>Collection</code> of <code>Comparable</code>s
1884	*@param b a <code>Collection</code> of <code>Comparable</code>s
1885	*@return the first non-zero <code>compareTo</code> result, if any;
1886	* otherwise, zero
1887	*/
1888	protected int compare(Collection a, Collection b) {
1889	Iterator i = a.iterator();
1890	Iterator j = b.iterator();
1891	while (i.hasNext() && j.hasNext()) {
1892	Comparable aElement = (Comparable) i.next();
1893	Comparable bElement = (Comparable) j.next();
1894	int comparison = aElement.compareTo(bElement);
1895	if (comparison != 0) {
1896	return comparison;
1897	}
1898	}
1899	if (i.hasNext()) {
1900	return 1;
1901	}
1902	if (j.hasNext()) {
1903	return -1;
1904	}
1905	return 0;
1906	}
1907
1908	protected boolean equal(Coordinate a, Coordinate b, double tolerance) {
1909	if (tolerance == 0) { return a.equals(b); }
1910	return a.distance(b) <= tolerance;
1911	}
1912
1913	abstract protected int getTypeCode();
1914
1915	private Point createPointFromInternalCoord(Coordinate coord, Geometry exemplar)
1916	{
1917	exemplar.getPrecisionModel().makePrecise(coord);
1918	return exemplar.getFactory().createPoint(coord);
1919	}
1920
1921
1922	}
1923
1924