Class MCIndexSnapRounder

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
30	/**
31	* Uses Snap Rounding to compute a rounded,
32	* fully noded arrangement from a set of {@link SegmentString}s.
33	* Implements the Snap Rounding technique described in
34	* papers by Hobby, Guibas & Marimont, and Goodrich et al.
35	* Snap Rounding assumes that all vertices lie on a uniform grid;
36	* hence the precision model of the input must be fixed precision,
37	* and all the input vertices must be rounded to that precision.
38	* <p>
39	* This implementation uses a monotone chains and a spatial index to
40	* speed up the intersection tests.
41	* <p>
42	* This implementation appears to be fully robust using an integer precision model.
43	* It will function with non-integer precision models, but the
44	* results are not 100% guaranteed to be correctly noded.
45	*
46	* @version 1.7
47	*/
48	public class MCIndexSnapRounder
49	implements Noder
50	{
51	private final PrecisionModel pm;
52	private LineIntersector li;
53	private final double scaleFactor;
54	private MCIndexNoder noder;
55	private MCIndexPointSnapper pointSnapper;
56	private Collection nodedSegStrings;
57
58	public MCIndexSnapRounder(PrecisionModel pm) {
59	this.pm = pm;
60	li = new RobustLineIntersector();
61	li.setPrecisionModel(pm);
62	scaleFactor = pm.getScale();
63	}
64
65	public Collection getNodedSubstrings()
66	{
67	return NodedSegmentString.getNodedSubstrings(nodedSegStrings);
68	}
69
70	public void computeNodes(Collection inputSegmentStrings)
71	{
72	this.nodedSegStrings = inputSegmentStrings;
73	noder = new MCIndexNoder();
74	pointSnapper = new MCIndexPointSnapper(noder.getIndex());
75	snapRound(inputSegmentStrings, li);
76
77	// testing purposes only - remove in final version
78	//checkCorrectness(inputSegmentStrings);
79	}
80
81	private void checkCorrectness(Collection inputSegmentStrings)
82	{
83	Collection resultSegStrings = NodedSegmentString.getNodedSubstrings(inputSegmentStrings);
84	NodingValidator nv = new NodingValidator(resultSegStrings);
85	try {
86	nv.checkValid();
87	} catch (Exception ex) {
88	ex.printStackTrace();
89	}
90	}
91
92	private void snapRound(Collection segStrings, LineIntersector li)
93	{
94	List intersections = findInteriorIntersections(segStrings, li);
95	computeIntersectionSnaps(intersections);
96	computeVertexSnaps(segStrings);
97	}
98
99	/**
100	* Computes all interior intersections in the collection of {@link SegmentString}s,
101	* and returns their {@link Coordinate}s.
102	*
103	* Does NOT node the segStrings.
104	*
105	* @return a list of Coordinates for the intersections
106	*/
107	private List findInteriorIntersections(Collection segStrings, LineIntersector li)
108	{
109	InteriorIntersectionFinderAdder intFinderAdder = new InteriorIntersectionFinderAdder(li);
110	noder.setSegmentIntersector(intFinderAdder);
111	noder.computeNodes(segStrings);
112	return intFinderAdder.getInteriorIntersections();
113	}
114
115	/**
116	* Snaps segments to nodes created by segment intersections.
117	*/
118	private void computeIntersectionSnaps(Collection snapPts)
119	{
120	for (Iterator it = snapPts.iterator(); it.hasNext(); ) {
121	Coordinate snapPt = (Coordinate) it.next();
122	HotPixel hotPixel = new HotPixel(snapPt, scaleFactor, li);
123	pointSnapper.snap(hotPixel);
124	}
125	}
126
127	/**
128	* Snaps segments to all vertices.
129	*
130	* @param edges the list of segment strings to snap together
131	*/
132	public void computeVertexSnaps(Collection edges)
133	{
134	for (Iterator i0 = edges.iterator(); i0.hasNext(); ) {
135	NodedSegmentString edge0 = (NodedSegmentString) i0.next();
136	computeVertexSnaps(edge0);
137	}
138	}
139
140	/**
141	* Snaps segments to the vertices of a Segment String.
142	*/
143	private void computeVertexSnaps(NodedSegmentString e)
144	{
145	Coordinate[] pts0 = e.getCoordinates();
146	for (int i = 0; i < pts0.length ; i++) {
147	HotPixel hotPixel = new HotPixel(pts0[i], scaleFactor, li);
148	boolean isNodeAdded = pointSnapper.snap(hotPixel, e, i);
149	// if a node is created for a vertex, that vertex must be noded too
150	if (isNodeAdded) {
151	e.addIntersection(pts0[i], i);
152	}
153	}
154	}
155
156	}
157