Class MonotoneChainIndexer

1
2
3
4	/*
5	* Copyright (c) 2016 Vivid Solutions.
6	*
7	* All rights reserved. This program and the accompanying materials
8	* are made available under the terms of the Eclipse Public License 2.0
9	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
10	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
11	* and the Eclipse Distribution License is available at
12	*
13	* http://www.eclipse.org/org/documents/edl-v10.php.
14	*/
15	package org.locationtech.jts.geomgraph.index;
16
17	import java.util.ArrayList;
18	import java.util.List;
19
20	import org.locationtech.jts.geom.Coordinate;
21	import org.locationtech.jts.geomgraph.Quadrant;
22	import org.locationtech.jts.util.IntArrayList;
23
24
25	/**
26	* MonotoneChains are a way of partitioning the segments of an edge to
27	* allow for fast searching of intersections.
28	* Specifically, a sequence of contiguous line segments
29	* is a monotone chain iff all the vectors defined by the oriented segments
30	* lies in the same quadrant.
31	* <p>
32	* Monotone Chains have the following useful properties:
33	* <ol>
34	* <li>the segments within a monotone chain will never intersect each other
35	* <li>the envelope of any contiguous subset of the segments in a monotone chain
36	* is simply the envelope of the endpoints of the subset.
37	* </ol>
38	* Property 1 means that there is no need to test pairs of segments from within
39	* the same monotone chain for intersection.
40	* Property 2 allows
41	* binary search to be used to find the intersection points of two monotone chains.
42	* For many types of real-world data, these properties eliminate a large number of
43	* segment comparisons, producing substantial speed gains.
44	* <p>
45	* Note that due to the efficient intersection test, there is no need to limit the size
46	* of chains to obtain fast performance.
47	*
48	* @version 1.7
49	*/
50	public class MonotoneChainIndexer {
51
52	public static int[] toIntArray(List list)
53	{
54	int[] array = new int[list.size()];
55	for (int i = 0; i < array.length; i++) {
56	array[i] = ((Integer) list.get(i)).intValue();
57	}
58	return array;
59	}
60
61	public MonotoneChainIndexer() {
62	}
63
64	public int[] getChainStartIndices(Coordinate[] pts)
65	{
66	// find the startpoint (and endpoints) of all monotone chains in this edge
67	int start = 0;
68	IntArrayList startIndexList = new IntArrayList(pts.length / 2);
69	// use heuristic to size initial array
70	//startIndexList.ensureCapacity(pts.length / 4);
71	startIndexList.add(start);
72	do {
73	int last = findChainEnd(pts, start);
74	startIndexList.add(last);
75	start = last;
76	} while (start < pts.length - 1);
77	// copy list to an array of ints, for efficiency
78	return startIndexList.toArray();
79	}
80
81	public int[] OLDgetChainStartIndices(Coordinate[] pts)
82	{
83	// find the startpoint (and endpoints) of all monotone chains in this edge
84	int start = 0;
85	List startIndexList = new ArrayList();
86	startIndexList.add(start);
87	do {
88	int last = findChainEnd(pts, start);
89	startIndexList.add(last);
90	start = last;
91	} while (start < pts.length - 1);
92	// copy list to an array of ints, for efficiency
93	int[] startIndex = toIntArray(startIndexList);
94	return startIndex;
95	}
96
97	/**
98	* @return the index of the last point in the monotone chain
99	*/
100	private int findChainEnd(Coordinate[] pts, int start)
101	{
102	// determine quadrant for chain
103	int chainQuad = Quadrant.quadrant(pts[start], pts[start + 1]);
104	int last = start + 1;
105	while (last < pts.length ) {
106	//if (last - start > 100) break;
107	// compute quadrant for next possible segment in chain
108	int quad = Quadrant.quadrant(pts[last - 1], pts[last]);
109	if (quad != chainQuad) break;
110	last++;
111	}
112	return last - 1;
113	}
114
115
116
117	}
118