Class GeometrySnapper

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
13	package org.locationtech.jts.operation.overlay.snap;
14
15	import java.util.Set;
16	import java.util.TreeSet;
17
18	import org.locationtech.jts.geom.Coordinate;
19	import org.locationtech.jts.geom.CoordinateSequence;
20	import org.locationtech.jts.geom.Envelope;
21	import org.locationtech.jts.geom.Geometry;
22	import org.locationtech.jts.geom.LineString;
23	import org.locationtech.jts.geom.Polygonal;
24	import org.locationtech.jts.geom.PrecisionModel;
25	import org.locationtech.jts.geom.util.GeometryTransformer;
26
27	/**
28	* Snaps the vertices and segments of a {@link Geometry}
29	* to another Geometry's vertices.
30	* A snap distance tolerance is used to control where snapping is performed.
31	* Snapping one geometry to another can improve
32	* robustness for overlay operations by eliminating
33	* nearly-coincident edges
34	* (which cause problems during noding and intersection calculation).
35	* It can also be used to eliminate artifacts such as narrow slivers, spikes and gores.
36	* <p>
37	* Too much snapping can result in invalid topology
38	* being created, so the number and location of snapped vertices
39	* is decided using heuristics to determine when it
40	* is safe to snap.
41	* This can result in some potential snaps being omitted, however.
42	*
43	* @author Martin Davis
44	* @version 1.7
45	*/
46	public class GeometrySnapper
47	{
48	private static final double SNAP_PRECISION_FACTOR = 1e-9;
49
50	/**
51	* Estimates the snap tolerance for a Geometry, taking into account its precision model.
52	*
53	* @param g a Geometry
54	* @return the estimated snap tolerance
55	*/
56	public static double computeOverlaySnapTolerance(Geometry g)
57	{
58	double snapTolerance = computeSizeBasedSnapTolerance(g);
59
60	/**
61	* Overlay is carried out in the precision model
62	* of the two inputs.
63	* If this precision model is of type FIXED, then the snap tolerance
64	* must reflect the precision grid size.
65	* Specifically, the snap tolerance should be at least
66	* the distance from a corner of a precision grid cell
67	* to the centre point of the cell.
68	*/
69	PrecisionModel pm = g.getPrecisionModel();
70	if (pm.getType() == PrecisionModel.FIXED) {
71	double fixedSnapTol = (1 / pm.getScale()) * 2 / 1.415;
72	if (fixedSnapTol > snapTolerance)
73	snapTolerance = fixedSnapTol;
74	}
75	return snapTolerance;
76	}
77
78	public static double computeSizeBasedSnapTolerance(Geometry g)
79	{
80	Envelope env = g.getEnvelopeInternal();
81	double minDimension = Math.min(env.getHeight(), env.getWidth());
82	double snapTol = minDimension * SNAP_PRECISION_FACTOR;
83	return snapTol;
84	}
85
86	public static double computeOverlaySnapTolerance(Geometry g0, Geometry g1)
87	{
88	return Math.min(computeOverlaySnapTolerance(g0), computeOverlaySnapTolerance(g1));
89	}
90
91	/**
92	* Snaps two geometries together with a given tolerance.
93	*
94	* @param g0 a geometry to snap
95	* @param g1 a geometry to snap
96	* @param snapTolerance the tolerance to use
97	* @return the snapped geometries
98	*/
99	public static Geometry[] snap(Geometry g0, Geometry g1, double snapTolerance)
100	{
101	Geometry[] snapGeom = new Geometry[2];
102	GeometrySnapper snapper0 = new GeometrySnapper(g0);
103	snapGeom[0] = snapper0.snapTo(g1, snapTolerance);
104
105	/**
106	* Snap the second geometry to the snapped first geometry
107	* (this strategy minimizes the number of possible different points in the result)
108	*/
109	GeometrySnapper snapper1 = new GeometrySnapper(g1);
110	snapGeom[1] = snapper1.snapTo(snapGeom[0], snapTolerance);
111
112	// System.out.println(snap[0]);
113	// System.out.println(snap[1]);
114	return snapGeom;
115	}
116	/**
117	* Snaps a geometry to itself.
118	* Allows optionally cleaning the result to ensure it is
119	* topologically valid
120	* (which fixes issues such as topology collapses in polygonal inputs).
121	* <p>
122	* Snapping a geometry to itself can remove artifacts such as very narrow slivers, gores and spikes.
123	*
124	*@param geom the geometry to snap
125	*@param snapTolerance the snapping tolerance
126	*@param cleanResult whether the result should be made valid
127	* @return a new snapped Geometry
128	*/
129	public static Geometry snapToSelf(Geometry geom, double snapTolerance, boolean cleanResult)
130	{
131	GeometrySnapper snapper0 = new GeometrySnapper(geom);
132	return snapper0.snapToSelf(snapTolerance, cleanResult);
133	}
134
135	private Geometry srcGeom;
136
137	/**
138	* Creates a new snapper acting on the given geometry
139	*
140	* @param srcGeom the geometry to snap
141	*/
142	public GeometrySnapper(Geometry srcGeom)
143	{
144	this.srcGeom = srcGeom;
145	}
146
147
148	/**
149	* Snaps the vertices in the component {@link LineString}s
150	* of the source geometry
151	* to the vertices of the given snap geometry.
152	*
153	* @param snapGeom a geometry to snap the source to
154	* @return a new snapped Geometry
155	*/
156	public Geometry snapTo(Geometry snapGeom, double snapTolerance)
157	{
158	Coordinate[] snapPts = extractTargetCoordinates(snapGeom);
159
160	SnapTransformer snapTrans = new SnapTransformer(snapTolerance, snapPts);
161	return snapTrans.transform(srcGeom);
162	}
163
164	/**
165	* Snaps the vertices in the component {@link LineString}s
166	* of the source geometry
167	* to the vertices of the same geometry.
168	* Allows optionally cleaning the result to ensure it is
169	* topologically valid
170	* (which fixes issues such as topology collapses in polygonal inputs).
171	*
172	*@param snapTolerance the snapping tolerance
173	*@param cleanResult whether the result should be made valid
174	* @return a new snapped Geometry
175	*/
176	public Geometry snapToSelf(double snapTolerance, boolean cleanResult)
177	{
178	Coordinate[] snapPts = extractTargetCoordinates(srcGeom);
179
180	SnapTransformer snapTrans = new SnapTransformer(snapTolerance, snapPts, true);
181	Geometry snappedGeom = snapTrans.transform(srcGeom);
182	Geometry result = snappedGeom;
183	if (cleanResult && result instanceof Polygonal) {
184	// TODO: use better cleaning approach
185	result = snappedGeom.buffer(0);
186	}
187	return result;
188	}
189
190	private Coordinate[] extractTargetCoordinates(Geometry g)
191	{
192	// TODO: should do this more efficiently. Use CoordSeq filter to get points, KDTree for uniqueness & queries
193	Set ptSet = new TreeSet();
194	Coordinate[] pts = g.getCoordinates();
195	for (int i = 0; i < pts.length; i++) {
196	ptSet.add(pts[i]);
197	}
198	return (Coordinate[]) ptSet.toArray(new Coordinate[0]);
199	}
200
201	/**
202	* Computes the snap tolerance based on the input geometries.
203	*
204	* @param ringPts
205	* @return
206	*/
207	private double computeSnapTolerance(Coordinate[] ringPts)
208	{
209	double minSegLen = computeMinimumSegmentLength(ringPts);
210	// use a small percentage of this to be safe
211	double snapTol = minSegLen / 10;
212	return snapTol;
213	}
214
215	private double computeMinimumSegmentLength(Coordinate[] pts)
216	{
217	double minSegLen = Double.MAX_VALUE;
218	for (int i = 0; i < pts.length - 1; i++) {
219	double segLen = pts[i].distance(pts[i + 1]);
220	if (segLen < minSegLen)
221	minSegLen = segLen;
222	}
223	return minSegLen;
224	}
225
226	}
227
228	class SnapTransformer
229	extends GeometryTransformer
230	{
231	private double snapTolerance;
232	private Coordinate[] snapPts;
233	private boolean isSelfSnap = false;
234
235	SnapTransformer(double snapTolerance, Coordinate[] snapPts)
236	{
237	this.snapTolerance = snapTolerance;
238	this.snapPts = snapPts;
239	}
240
241	SnapTransformer(double snapTolerance, Coordinate[] snapPts, boolean isSelfSnap)
242	{
243	this.snapTolerance = snapTolerance;
244	this.snapPts = snapPts;
245	this.isSelfSnap = isSelfSnap;
246	}
247
248	protected CoordinateSequence transformCoordinates(CoordinateSequence coords, Geometry parent)
249	{
250	Coordinate[] srcPts = coords.toCoordinateArray();
251	Coordinate[] newPts = snapLine(srcPts, snapPts);
252	return factory.getCoordinateSequenceFactory().create(newPts);
253	}
254
255	private Coordinate[] snapLine(Coordinate[] srcPts, Coordinate[] snapPts)
256	{
257	LineStringSnapper snapper = new LineStringSnapper(srcPts, snapTolerance);
258	snapper.setAllowSnappingToSourceVertices(isSelfSnap);
259	return snapper.snapTo(snapPts);
260	}
261	}
262
263
264