Class SimpleSnapRounder

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.noding.snapround;
14
15	import java.util.Collection;
16	import java.util.Iterator;
17	import java.util.List;
18
19	import org.locationtech.jts.algorithm.LineIntersector;
20	import org.locationtech.jts.algorithm.RobustLineIntersector;
21	import org.locationtech.jts.geom.Coordinate;
22	import org.locationtech.jts.geom.PrecisionModel;
23	import org.locationtech.jts.noding.InteriorIntersectionFinderAdder;
24	import org.locationtech.jts.noding.MCIndexNoder;
25	import org.locationtech.jts.noding.NodedSegmentString;
26	import org.locationtech.jts.noding.Noder;
27	import org.locationtech.jts.noding.NodingValidator;
28	import org.locationtech.jts.noding.SegmentString;
29	import org.locationtech.jts.noding.SinglePassNoder;
30
31	/**
32	* Uses Snap Rounding to compute a rounded,
33	* fully noded arrangement from a set of {@link SegmentString}s.
34	* Implements the Snap Rounding technique described in
35	* the papers by Hobby, Guibas & Marimont, and Goodrich et al.
36	* Snap Rounding assumes that all vertices lie on a uniform grid;
37	* hence the precision model of the input must be fixed precision,
38	* and all the input vertices must be rounded to that precision.
39	* <p>
40	* This implementation uses simple iteration over the line segments.
41	* This is not the most efficient approach for large sets of segments.
42	* <p>
43	* This implementation appears to be fully robust using an integer precision model.
44	* It will function with non-integer precision models, but the
45	* results are not 100% guaranteed to be correctly noded.
46	*
47	* @version 1.7
48	*/
49	public class SimpleSnapRounder
50	implements Noder
51	{
52	private final PrecisionModel pm;
53	private LineIntersector li;
54	private final double scaleFactor;
55	private Collection nodedSegStrings;
56
57	public SimpleSnapRounder(PrecisionModel pm) {
58	this.pm = pm;
59	li = new RobustLineIntersector();
60	li.setPrecisionModel(pm);
61	scaleFactor = pm.getScale();
62	}
63
64	/**
65	* @return a Collection of NodedSegmentStrings representing the substrings
66	*
67	*/
68	public Collection getNodedSubstrings()
69	{
70	return NodedSegmentString.getNodedSubstrings(nodedSegStrings);
71	}
72
73	/**
74	* @param inputSegmentStrings a Collection of NodedSegmentStrings
75	*/
76	public void computeNodes(Collection inputSegmentStrings)
77	{
78	this.nodedSegStrings = inputSegmentStrings;
79	snapRound(inputSegmentStrings, li);
80
81	// testing purposes only - remove in final version
82	//checkCorrectness(inputSegmentStrings);
83	}
84
85	private void checkCorrectness(Collection inputSegmentStrings)
86	{
87	Collection resultSegStrings = NodedSegmentString.getNodedSubstrings(inputSegmentStrings);
88	NodingValidator nv = new NodingValidator(resultSegStrings);
89	try {
90	nv.checkValid();
91	} catch (Exception ex) {
92	ex.printStackTrace();
93	}
94	}
95	private void snapRound(Collection segStrings, LineIntersector li)
96	{
97	List intersections = findInteriorIntersections(segStrings, li);
98	computeSnaps(segStrings, intersections);
99	computeVertexSnaps(segStrings);
100	}
101
102	/**
103	* Computes all interior intersections in the collection of {@link SegmentString}s,
104	* and returns their {@link Coordinate}s.
105	*
106	* Does NOT node the segStrings.
107	*
108	* @return a list of Coordinates for the intersections
109	*/
110	private List findInteriorIntersections(Collection segStrings, LineIntersector li)
111	{
112	InteriorIntersectionFinderAdder intFinderAdder = new InteriorIntersectionFinderAdder(li);
113	SinglePassNoder noder = new MCIndexNoder();
114	noder.setSegmentIntersector(intFinderAdder);
115	noder.computeNodes(segStrings);
116	return intFinderAdder.getInteriorIntersections();
117	}
118
119
120	/**
121	* Computes nodes introduced as a result of snapping segments to snap points (hot pixels)
122	* @param li
123	*/
124	private void computeSnaps(Collection segStrings, Collection snapPts)
125	{
126	for (Iterator i0 = segStrings.iterator(); i0.hasNext(); ) {
127	NodedSegmentString ss = (NodedSegmentString) i0.next();
128	computeSnaps(ss, snapPts);
129	}
130	}
131
132	private void computeSnaps(NodedSegmentString ss, Collection snapPts)
133	{
134	for (Iterator it = snapPts.iterator(); it.hasNext(); ) {
135	Coordinate snapPt = (Coordinate) it.next();
136	HotPixel hotPixel = new HotPixel(snapPt, scaleFactor, li);
137	for (int i = 0; i < ss.size() - 1; i++) {
138	hotPixel.addSnappedNode(ss, i);
139	}
140	}
141	}
142
143	/**
144	* Computes nodes introduced as a result of
145	* snapping segments to vertices of other segments
146	*
147	* @param edges the list of segment strings to snap together
148	*/
149	public void computeVertexSnaps(Collection edges)
150	{
151	for (Iterator i0 = edges.iterator(); i0.hasNext(); ) {
152	NodedSegmentString edge0 = (NodedSegmentString) i0.next();
153	for (Iterator i1 = edges.iterator(); i1.hasNext(); ) {
154	NodedSegmentString edge1 = (NodedSegmentString) i1.next();
155	computeVertexSnaps(edge0, edge1);
156	}
157	}
158	}
159
160	/**
161	* Performs a brute-force comparison of every segment in each {@link SegmentString}.
162	* This has n^2 performance.
163	*/
164	private void computeVertexSnaps(NodedSegmentString e0, NodedSegmentString e1)
165	{
166	Coordinate[] pts0 = e0.getCoordinates();
167	Coordinate[] pts1 = e1.getCoordinates();
168	for (int i0 = 0; i0 < pts0.length - 1; i0++) {
169	HotPixel hotPixel = new HotPixel(pts0[i0], scaleFactor, li);
170	for (int i1 = 0; i1 < pts1.length - 1; i1++) {
171	// don't snap a vertex to itself
172	if (e0 == e1) {
173	if (i0 == i1) continue;
174	}
175	//System.out.println("trying " + pts0[i0] + " against " + pts1[i1] + pts1[i1 + 1]);
176	boolean isNodeAdded = hotPixel.addSnappedNode(e1, i1);
177	// if a node is created for a vertex, that vertex must be noded too
178	if (isNodeAdded) {
179	e0.addIntersection(pts0[i0], i0);
180	}
181	}
182	}
183	}
184
185	}
186