Class IteratedNoder

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;
14
15	import java.util.Collection;
16
17	import org.locationtech.jts.algorithm.LineIntersector;
18	import org.locationtech.jts.algorithm.RobustLineIntersector;
19	import org.locationtech.jts.geom.PrecisionModel;
20	import org.locationtech.jts.geom.TopologyException;
21
22	/**
23	* Nodes a set of {@link NodedSegmentString}s completely.
24	* The set of segment strings is fully noded;
25	* i.e. noding is repeated until no further
26	* intersections are detected.
27	* <p>
28	* Iterated noding using a FLOATING precision model is not guaranteed to converge,
29	* due to roundoff error.
30	* This problem is detected and an exception is thrown.
31	* Clients can choose to rerun the noding using a lower precision model.
32	*
33	* @version 1.7
34	*/
35	public class IteratedNoder
36	implements Noder
37	{
38	public static final int MAX_ITER = 5;
39
40	private PrecisionModel pm;
41	private LineIntersector li;
42	private Collection nodedSegStrings;
43	private int maxIter = MAX_ITER;
44
45	public IteratedNoder(PrecisionModel pm)
46	{
47	li = new RobustLineIntersector();
48	this.pm = pm;
49	li.setPrecisionModel(pm);
50	}
51
52	/**
53	* Sets the maximum number of noding iterations performed before
54	* the noding is aborted.
55	* Experience suggests that this should rarely need to be changed
56	* from the default.
57	* The default is MAX_ITER.
58	*
59	* @param maxIter the maximum number of iterations to perform
60	*/
61	public void setMaximumIterations(int maxIter)
62	{
63	this.maxIter = maxIter;
64	}
65
66	public Collection getNodedSubstrings() { return nodedSegStrings; }
67
68	/**
69	* Fully nodes a list of {@link SegmentString}s, i.e. performs noding iteratively
70	* until no intersections are found between segments.
71	* Maintains labelling of edges correctly through
72	* the noding.
73	*
74	* @param segStrings a collection of SegmentStrings to be noded
75	* @throws TopologyException if the iterated noding fails to converge.
76	*/
77	public void computeNodes(Collection segStrings)
78	throws TopologyException
79	{
80	int[] numInteriorIntersections = new int[1];
81	nodedSegStrings = segStrings;
82	int nodingIterationCount = 0;
83	int lastNodesCreated = -1;
84	do {
85	node(nodedSegStrings, numInteriorIntersections);
86	nodingIterationCount++;
87	int nodesCreated = numInteriorIntersections[0];
88
89	/**
90	* Fail if the number of nodes created is not declining.
91	* However, allow a few iterations at least before doing this
92	*/
93	//System.out.println("# nodes created: " + nodesCreated);
94	if (lastNodesCreated > 0
95	&& nodesCreated >= lastNodesCreated
96	&& nodingIterationCount > maxIter) {
97	throw new TopologyException("Iterated noding failed to converge after "
98	+ nodingIterationCount + " iterations");
99	}
100	lastNodesCreated = nodesCreated;
101
102	} while (lastNodesCreated > 0);
103	//System.out.println("# nodings = " + nodingIterationCount);
104	}
105
106
107	/**
108	* Node the input segment strings once
109	* and create the split edges between the nodes
110	*/
111	private void node(Collection segStrings, int[] numInteriorIntersections)
112	{
113	IntersectionAdder si = new IntersectionAdder(li);
114	MCIndexNoder noder = new MCIndexNoder();
115	noder.setSegmentIntersector(si);
116	noder.computeNodes(segStrings);
117	nodedSegStrings = noder.getNodedSubstrings();
118	numInteriorIntersections[0] = si.numInteriorIntersections;
119	//System.out.println("# intersection tests: " + si.numTests);
120	}
121
122	}
123