Class MonotoneChainBuilder

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12	package org.locationtech.jts.index.chain;
13
14	import java.util.ArrayList;
15	import java.util.List;
16
17	import org.locationtech.jts.geom.Coordinate;
18	import org.locationtech.jts.geomgraph.Quadrant;
19
20	/**
21	* Constructs {@link MonotoneChain}s
22	* for sequences of {@link Coordinate}s.
23	*
24	* @version 1.7
25	*/
26	public class MonotoneChainBuilder {
27
28	/**
29	* Computes a list of the {@link MonotoneChain}s
30	* for a list of coordinates.
31	*
32	* @param pts the list of points to compute chains for
33	* @return a list of the monotone chains for the points
34	*/
35	public static List getChains(Coordinate[] pts)
36	{
37	return getChains(pts, null);
38	}
39
40	/**
41	* Computes a list of the {@link MonotoneChain}s
42	* for a list of coordinates,
43	* attaching a context data object to each.
44	*
45	* @param pts the list of points to compute chains for
46	* @param context a data object to attach to each chain
47	* @return a list of the monotone chains for the points
48	*/
49	public static List getChains(Coordinate[] pts, Object context)
50	{
51	List mcList = new ArrayList();
52	int chainStart = 0;
53	do {
54	int chainEnd = findChainEnd(pts, chainStart);
55	MonotoneChain mc = new MonotoneChain(pts, chainStart, chainEnd, context);
56	mcList.add(mc);
57	chainStart = chainEnd;
58	} while (chainStart < pts.length -1);
59	return mcList;
60	}
61
62	/**
63	* Finds the index of the last point in a monotone chain
64	* starting at a given point.
65	* Repeated points (0-length segments) are included
66	* in the monotone chain returned.
67	*
68	* @param pts the points to scan
69	* @param start the index of the start of this chain
70	* @return the index of the last point in the monotone chain
71	* starting at <code>start</code>.
72	*/
73	private static int findChainEnd(Coordinate[] pts, int start)
74	{
75	int safeStart = start;
76	// skip any zero-length segments at the start of the sequence
77	// (since they cannot be used to establish a quadrant)
78	while (safeStart < pts.length - 1 && pts[safeStart].equals2D(pts[safeStart + 1])) {
79	safeStart++;
80	}
81	// check if there are NO non-zero-length segments
82	if (safeStart >= pts.length - 1) {
83	return pts.length - 1;
84	}
85	// determine overall quadrant for chain (which is the starting quadrant)
86	int chainQuad = Quadrant.quadrant(pts[safeStart], pts[safeStart + 1]);
87	int last = start + 1;
88	while (last < pts.length) {
89	// skip zero-length segments, but include them in the chain
90	if (! pts[last - 1].equals2D(pts[last])) {
91	// compute quadrant for next possible segment in chain
92	int quad = Quadrant.quadrant(pts[last - 1], pts[last]);
93	if (quad != chainQuad) break;
94	}
95	last++;
96	}
97	return last - 1;
98	}
99
100	}
101