Class MCIndexNoder

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.ArrayList;
16	import java.util.Collection;
17	import java.util.Iterator;
18	import java.util.List;
19
20	import org.locationtech.jts.index.SpatialIndex;
21	import org.locationtech.jts.index.chain.MonotoneChain;
22	import org.locationtech.jts.index.chain.MonotoneChainBuilder;
23	import org.locationtech.jts.index.chain.MonotoneChainOverlapAction;
24	import org.locationtech.jts.index.strtree.STRtree;
25
26	/**
27	* Nodes a set of {@link SegmentString}s using a index based
28	* on {@link MonotoneChain}s and a {@link SpatialIndex}.
29	* The {@link SpatialIndex} used should be something that supports
30	* envelope (range) queries efficiently (such as a <code>Quadtree</code>}
31	* or {@link STRtree} (which is the default index provided).
32	*
33	* @version 1.7
34	*/
35	public class MCIndexNoder
36	extends SinglePassNoder
37	{
38	private List monoChains = new ArrayList();
39	private SpatialIndex index= new STRtree();
40	private int idCounter = 0;
41	private Collection nodedSegStrings;
42	// statistics
43	private int nOverlaps = 0;
44
45	public MCIndexNoder()
46	{
47	}
48	public MCIndexNoder(SegmentIntersector si)
49	{
50	super(si);
51	}
52
53	public List getMonotoneChains() { return monoChains; }
54
55	public SpatialIndex getIndex() { return index; }
56
57	public Collection getNodedSubstrings()
58	{
59	return NodedSegmentString.getNodedSubstrings(nodedSegStrings);
60	}
61
62	public void computeNodes(Collection inputSegStrings)
63	{
64	this.nodedSegStrings = inputSegStrings;
65	for (Iterator i = inputSegStrings.iterator(); i.hasNext(); ) {
66	add((SegmentString) i.next());
67	}
68	intersectChains();
69	//System.out.println("MCIndexNoder: # chain overlaps = " + nOverlaps);
70	}
71
72	private void intersectChains()
73	{
74	MonotoneChainOverlapAction overlapAction = new SegmentOverlapAction(segInt);
75
76	for (Iterator i = monoChains.iterator(); i.hasNext(); ) {
77	MonotoneChain queryChain = (MonotoneChain) i.next();
78	List overlapChains = index.query(queryChain.getEnvelope());
79	for (Iterator j = overlapChains.iterator(); j.hasNext(); ) {
80	MonotoneChain testChain = (MonotoneChain) j.next();
81	/**
82	* following test makes sure we only compare each pair of chains once
83	* and that we don't compare a chain to itself
84	*/
85	if (testChain.getId() > queryChain.getId()) {
86	queryChain.computeOverlaps(testChain, overlapAction);
87	nOverlaps++;
88	}
89	// short-circuit if possible
90	if (segInt.isDone())
91	return;
92	}
93	}
94	}
95
96	private void add(SegmentString segStr)
97	{
98	List segChains = MonotoneChainBuilder.getChains(segStr.getCoordinates(), segStr);
99	for (Iterator i = segChains.iterator(); i.hasNext(); ) {
100	MonotoneChain mc = (MonotoneChain) i.next();
101	mc.setId(idCounter++);
102	index.insert(mc.getEnvelope(), mc);
103	monoChains.add(mc);
104	}
105	}
106
107	public static class SegmentOverlapAction
108	extends MonotoneChainOverlapAction
109	{
110	private SegmentIntersector si = null;
111
112	public SegmentOverlapAction(SegmentIntersector si)
113	{
114	this.si = si;
115	}
116
117	public void overlap(MonotoneChain mc1, int start1, MonotoneChain mc2, int start2)
118	{
119	SegmentString ss1 = (SegmentString) mc1.getContext();
120	SegmentString ss2 = (SegmentString) mc2.getContext();
121	si.processIntersections(ss1, start1, ss2, start2);
122	}
123
124	}
125	}
126