Class CoordinateArrays

1
2
3	/*
4	* Copyright (c) 2016 Vivid Solutions.
5	*
6	* All rights reserved. This program and the accompanying materials
7	* are made available under the terms of the Eclipse Public License 2.0
8	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
9	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
10	* and the Eclipse Distribution License is available at
11	*
12	* http://www.eclipse.org/org/documents/edl-v10.php.
13	*/
14	package org.locationtech.jts.geom;
15
16	import java.lang.reflect.Array;
17	import java.util.Collection;
18	import java.util.Comparator;
19
20	import org.locationtech.jts.math.MathUtil;
21
22
23	/**
24	* Useful utility functions for handling Coordinate arrays
25	*
26	* @version 1.7
27	*/
28	public class CoordinateArrays {
29	private final static Coordinate[] coordArrayType = new Coordinate[0];
30
31	private CoordinateArrays() {
32	}
33
34	/**
35	* Determine dimension based on subclass of {@link Coordinate}.
36	*
37	* @param pts supplied coordinates
38	* @return number of ordinates recorded
39	*/
40	public static int dimension(Coordinate[] pts) {
41	if (pts == null \|\| pts.length == 0) {
42	return 3; // unknown, assume default
43	}
44	int dimension = 0;
45	for (Coordinate coordinate : pts) {
46	dimension = Math.max(dimension, Coordinates.dimension(coordinate));
47	}
48	return dimension;
49	}
50
51	/**
52	* Determine number of measures based on subclass of {@link Coordinate}.
53	*
54	* @param pts supplied coordinates
55	* @return number of measures recorded
56	*/
57	public static int measures(Coordinate[] pts) {
58	if (pts == null \|\| pts.length == 0) {
59	return 0; // unknown, assume default
60	}
61	int measures = 0;
62	for (Coordinate coordinate : pts) {
63	measures = Math.max(measures, Coordinates.measures(coordinate));
64	}
65	return measures;
66	}
67
68
69	/**
70	* Utility method ensuring array contents are of consistent dimension and measures.
71	* <p>
72	* Array is modified in place if required, coordinates are replaced in the array as required
73	* to ensure all coordinates have the same dimension and measures. The final dimension and
74	* measures used are the maximum found when checking the array.
75	* </p>
76	*
77	* @param array Modified in place to coordinates of consistent dimension and measures.
78	*/
79	public static void enforceConsistency(Coordinate[] array)
80	{
81	if (array == null) {
82	return;
83	}
84	// step one check
85	int maxDimension = -1;
86	int maxMeasures = -1;
87	boolean isConsistent = true;
88	for (int i = 0; i < array.length; i++) {
89	Coordinate coordinate = array[i];
90	if (coordinate != null) {
91	int d = Coordinates.dimension(coordinate);
92	int m = Coordinates.measures(coordinate);
93	if( maxDimension == -1){
94	maxDimension = d;
95	maxMeasures = m;
96	continue;
97	}
98	if( d != maxDimension \|\| m != maxMeasures ){
99	isConsistent = false;
100	maxDimension = Math.max(maxDimension, d);
101	maxMeasures = Math.max(maxMeasures, m);
102	}
103	}
104	}
105	if (!isConsistent) {
106	// step two fix
107	Coordinate sample = Coordinates.create(maxDimension, maxMeasures);
108	Class<?> type = sample.getClass();
109
110	for (int i = 0; i < array.length; i++) {
111	Coordinate coordinate = array[i];
112	if (coordinate != null && !coordinate.getClass().equals(type)) {
113	Coordinate duplicate = Coordinates.create(maxDimension, maxMeasures);
114	duplicate.setCoordinate(coordinate);
115	array[i] = duplicate;
116	}
117	}
118	}
119	}
120
121	/**
122	* Utility method ensuring array contents are of the specified dimension and measures.
123	* <p>
124	* Array is returned unmodified if consistent, or a copy of the array is made with
125	* each inconsistent coordinate duplicated into an instance of the correct dimension and measures.
126	* </p></>
127	*
128	* @param array coordinate array
129	* @param dimension
130	* @param measures
131	* @return array returned, or copy created if required to enforce consistency.
132	*/
133	public static Coordinate[] enforceConsistency(Coordinate[] array,int dimension, int measures)
134	{
135	Coordinate sample = Coordinates.create(dimension,measures);
136	Class<?> type = sample.getClass();
137	boolean isConsistent = true;
138	for (int i = 0; i < array.length; i++) {
139	Coordinate coordinate = array[i];
140	if (coordinate != null && !coordinate.getClass().equals(type)) {
141	isConsistent = false;
142	break;
143	}
144	}
145	if (isConsistent) {
146	return array;
147	}
148	else {
149	Class<? extends Coordinate> coordinateType = sample.getClass();
150	Coordinate copy[] = (Coordinate[]) Array.newInstance(coordinateType, array.length);
151	for (int i = 0; i < copy.length; i++) {
152	Coordinate coordinate = array[i];
153	if (coordinate != null && !coordinate.getClass().equals(type)) {
154	Coordinate duplicate = Coordinates.create(dimension,measures);
155	duplicate.setCoordinate(coordinate);
156	copy[i] = duplicate;
157	}
158	else {
159	copy[i] = coordinate;
160	}
161	}
162	return copy;
163	}
164	}
165
166	/**
167	* Tests whether an array of {@link Coordinate}s forms a ring,
168	* by checking length and closure.
169	* Self-intersection is not checked.
170	*
171	* @param pts an array of Coordinates
172	* @return true if the coordinate form a ring.
173	*/
174	public static boolean isRing(Coordinate[] pts) {
175	if (pts.length < 4) return false;
176	if (!pts[0].equals2D(pts[pts.length - 1])) return false;
177	return true;
178	}
179
180	/**
181	* Finds a point in a list of points which is not contained in another list of points
182	*
183	* @param testPts the {@link Coordinate}s to test
184	* @param pts an array of {@link Coordinate}s to test the input points against
185	* @return a {@link Coordinate} from <code>testPts</code> which is not in <code>pts</code>, '
186	* or <code>null</code>
187	*/
188	public static Coordinate ptNotInList(Coordinate[] testPts, Coordinate[] pts) {
189	for (int i = 0; i < testPts.length; i++) {
190	Coordinate testPt = testPts[i];
191	if (CoordinateArrays.indexOf(testPt, pts) < 0)
192	return testPt;
193	}
194	return null;
195	}
196
197	/**
198	* Compares two {@link Coordinate} arrays
199	* in the forward direction of their coordinates,
200	* using lexicographic ordering.
201	*
202	* @param pts1
203	* @param pts2
204	* @return an integer indicating the order
205	*/
206	public static int compare(Coordinate[] pts1, Coordinate[] pts2) {
207	int i = 0;
208	while (i < pts1.length && i < pts2.length) {
209	int compare = pts1[i].compareTo(pts2[i]);
210	if (compare != 0)
211	return compare;
212	i++;
213	}
214	// handle situation when arrays are of different length
215	if (i < pts2.length) return -1;
216	if (i < pts1.length) return 1;
217
218	return 0;
219	}
220
221	/**
222	* A {@link Comparator} for {@link Coordinate} arrays
223	* in the forward direction of their coordinates,
224	* using lexicographic ordering.
225	*/
226	public static class ForwardComparator
227	implements Comparator {
228	public int compare(Object o1, Object o2) {
229	Coordinate[] pts1 = (Coordinate[]) o1;
230	Coordinate[] pts2 = (Coordinate[]) o2;
231
232	return CoordinateArrays.compare(pts1, pts2);
233	}
234	}
235
236
237	/**
238	* Determines which orientation of the {@link Coordinate} array
239	* is (overall) increasing.
240	* In other words, determines which end of the array is "smaller"
241	* (using the standard ordering on {@link Coordinate}).
242	* Returns an integer indicating the increasing direction.
243	* If the sequence is a palindrome, it is defined to be
244	* oriented in a positive direction.
245	*
246	* @param pts the array of Coordinates to test
247	* @return <code>1</code> if the array is smaller at the start
248	* or is a palindrome,
249	* <code>-1</code> if smaller at the end
250	*/
251	public static int increasingDirection(Coordinate[] pts) {
252	for (int i = 0; i < pts.length / 2; i++) {
253	int j = pts.length - 1 - i;
254	// skip equal points on both ends
255	int comp = pts[i].compareTo(pts[j]);
256	if (comp != 0)
257	return comp;
258	}
259	// array must be a palindrome - defined to be in positive direction
260	return 1;
261	}
262
263	/**
264	* Determines whether two {@link Coordinate} arrays of equal length
265	* are equal in opposite directions.
266	*
267	* @param pts1
268	* @param pts2
269	* @return <code>true</code> if the two arrays are equal in opposite directions.
270	*/
271	private static boolean isEqualReversed(Coordinate[] pts1, Coordinate[] pts2) {
272	for (int i = 0; i < pts1.length; i++) {
273	Coordinate p1 = pts1[i];
274	Coordinate p2 = pts2[pts1.length - i - 1];
275	if (p1.compareTo(p2) != 0)
276	return false;
277	}
278	return true;
279	}
280
281	/**
282	* A {@link Comparator} for {@link Coordinate} arrays
283	* modulo their directionality.
284	* E.g. if two coordinate arrays are identical but reversed
285	* they will compare as equal under this ordering.
286	* If the arrays are not equal, the ordering returned
287	* is the ordering in the forward direction.
288	*/
289	public static class BidirectionalComparator
290	implements Comparator {
291	public int compare(Object o1, Object o2) {
292	Coordinate[] pts1 = (Coordinate[]) o1;
293	Coordinate[] pts2 = (Coordinate[]) o2;
294
295	if (pts1.length < pts2.length) return -1;
296	if (pts1.length > pts2.length) return 1;
297
298	if (pts1.length == 0) return 0;
299
300	int forwardComp = CoordinateArrays.compare(pts1, pts2);
301	boolean isEqualRev = isEqualReversed(pts1, pts2);
302	if (isEqualRev)
303	return 0;
304	return forwardComp;
305	}
306
307	public int OLDcompare(Object o1, Object o2) {
308	Coordinate[] pts1 = (Coordinate[]) o1;
309	Coordinate[] pts2 = (Coordinate[]) o2;
310
311	if (pts1.length < pts2.length) return -1;
312	if (pts1.length > pts2.length) return 1;
313
314	if (pts1.length == 0) return 0;
315
316	int dir1 = increasingDirection(pts1);
317	int dir2 = increasingDirection(pts2);
318
319	int i1 = dir1 > 0 ? 0 : pts1.length - 1;
320	int i2 = dir2 > 0 ? 0 : pts1.length - 1;
321
322	for (int i = 0; i < pts1.length; i++) {
323	int comparePt = pts1[i1].compareTo(pts2[i2]);
324	if (comparePt != 0)
325	return comparePt;
326	i1 += dir1;
327	i2 += dir2;
328	}
329	return 0;
330	}
331
332	}
333
334	/**
335	* Creates a deep copy of the argument {@link Coordinate} array.
336	*
337	* @param coordinates an array of Coordinates
338	* @return a deep copy of the input
339	*/
340	public static Coordinate[] copyDeep(Coordinate[] coordinates) {
341	Coordinate[] copy = new Coordinate[coordinates.length];
342	for (int i = 0; i < coordinates.length; i++) {
343	copy[i] = coordinates[i].copy();
344	}
345	return copy;
346	}
347
348	/**
349	* Creates a deep copy of a given section of a source {@link Coordinate} array
350	* into a destination Coordinate array.
351	* The destination array must be an appropriate size to receive
352	* the copied coordinates.
353	*
354	* @param src an array of Coordinates
355	* @param srcStart the index to start copying from
356	* @param dest the
357	* @param destStart the destination index to start copying to
358	* @param length the number of items to copy
359	*/
360	public static void copyDeep(Coordinate[] src, int srcStart, Coordinate[] dest, int destStart, int length) {
361	for (int i = 0; i < length; i++) {
362	dest[destStart + i] = src[srcStart + i].copy();
363	}
364	}
365
366	/**
367	* Converts the given Collection of Coordinates into a Coordinate array.
368	*/
369	public static Coordinate[] toCoordinateArray(Collection coordList) {
370	return (Coordinate[]) coordList.toArray(coordArrayType);
371	}
372
373	/**
374	* Returns whether #equals returns true for any two consecutive Coordinates
375	* in the given array.
376	*/
377	public static boolean hasRepeatedPoints(Coordinate[] coord) {
378	for (int i = 1; i < coord.length; i++) {
379	if (coord[i - 1].equals(coord[i])) {
380	return true;
381	}
382	}
383	return false;
384	}
385
386	/**
387	* Returns either the given coordinate array if its length is greater than the
388	* given amount, or an empty coordinate array.
389	*/
390	public static Coordinate[] atLeastNCoordinatesOrNothing(int n, Coordinate[] c) {
391	return c.length >= n ? c : new Coordinate[]{};
392	}
393
394	/**
395	* If the coordinate array argument has repeated points,
396	* constructs a new array containing no repeated points.
397	* Otherwise, returns the argument.
398	*
399	* @see #hasRepeatedPoints(Coordinate[])
400	*/
401	public static Coordinate[] removeRepeatedPoints(Coordinate[] coord) {
402	if (!hasRepeatedPoints(coord)) return coord;
403	CoordinateList coordList = new CoordinateList(coord, false);
404	return coordList.toCoordinateArray();
405	}
406
407	/**
408	* Collapses a coordinate array to remove all null elements.
409	*
410	* @param coord the coordinate array to collapse
411	* @return an array containing only non-null elements
412	*/
413	public static Coordinate[] removeNull(Coordinate[] coord) {
414	int nonNull = 0;
415	for (int i = 0; i < coord.length; i++) {
416	if (coord[i] != null) nonNull++;
417	}
418	Coordinate[] newCoord = new Coordinate[nonNull];
419	// empty case
420	if (nonNull == 0) return newCoord;
421
422	int j = 0;
423	for (int i = 0; i < coord.length; i++) {
424	if (coord[i] != null) newCoord[j++] = coord[i];
425	}
426	return newCoord;
427	}
428
429	/**
430	* Reverses the coordinates in an array in-place.
431	*/
432	public static void reverse(Coordinate[] coord) {
433	int last = coord.length - 1;
434	int mid = last / 2;
435	for (int i = 0; i <= mid; i++) {
436	Coordinate tmp = coord[i];
437	coord[i] = coord[last - i];
438	coord[last - i] = tmp;
439	}
440	}
441
442	/**
443	* Returns true if the two arrays are identical, both null, or pointwise
444	* equal (as compared using Coordinate#equals)
445	*
446	* @see Coordinate#equals(Object)
447	*/
448	public static boolean equals(
449	Coordinate[] coord1,
450	Coordinate[] coord2) {
451	if (coord1 == coord2) return true;
452	if (coord1 == null \|\| coord2 == null) return false;
453	if (coord1.length != coord2.length) return false;
454	for (int i = 0; i < coord1.length; i++) {
455	if (!coord1[i].equals(coord2[i])) return false;
456	}
457	return true;
458	}
459
460	/**
461	* Returns true if the two arrays are identical, both null, or pointwise
462	* equal, using a user-defined {@link Comparator} for {@link Coordinate} s
463	*
464	* @param coord1 an array of Coordinates
465	* @param coord2 an array of Coordinates
466	* @param coordinateComparator a Comparator for Coordinates
467	*/
468	public static boolean equals(
469	Coordinate[] coord1,
470	Coordinate[] coord2,
471	Comparator coordinateComparator) {
472	if (coord1 == coord2) return true;
473	if (coord1 == null \|\| coord2 == null) return false;
474	if (coord1.length != coord2.length) return false;
475	for (int i = 0; i < coord1.length; i++) {
476	if (coordinateComparator.compare(coord1[i], coord2[i]) != 0)
477	return false;
478	}
479	return true;
480	}
481
482	/**
483	* Returns the minimum coordinate, using the usual lexicographic comparison.
484	*
485	* @param coordinates the array to search
486	* @return the minimum coordinate in the array, found using <code>compareTo</code>
487	* @see Coordinate#compareTo(Coordinate)
488	*/
489	public static Coordinate minCoordinate(Coordinate[] coordinates) {
490	Coordinate minCoord = null;
491	for (int i = 0; i < coordinates.length; i++) {
492	if (minCoord == null \|\| minCoord.compareTo(coordinates[i]) > 0) {
493	minCoord = coordinates[i];
494	}
495	}
496	return minCoord;
497	}
498
499	/**
500	* Shifts the positions of the coordinates until <code>firstCoordinate</code>
501	* is first.
502	*
503	* @param coordinates the array to rearrange
504	* @param firstCoordinate the coordinate to make first
505	*/
506	public static void scroll(Coordinate[] coordinates, Coordinate firstCoordinate) {
507	int i = indexOf(firstCoordinate, coordinates);
508	scroll(coordinates, i);
509	}
510
511	/**
512	* Shifts the positions of the coordinates until the coordinate
513	* at <code>firstCoordinate</code> is first.
514	*
515	* @param coordinates the array to rearrange
516	* @param indexOfFirstCoordinate the index of the coordinate to make first
517	*/
518	public static void scroll(Coordinate[] coordinates, int indexOfFirstCoordinate) {
519	scroll(coordinates, indexOfFirstCoordinate, CoordinateArrays.isRing(coordinates));
520	}
521
522	/**
523	* Shifts the positions of the coordinates until the coordinate
524	* at <code>indexOfFirstCoordinate</code> is first.
525	* <p/>
526	* If {@code ensureRing} is {@code true}, first and last
527	* coordinate of the returned array are equal.
528	*
529	* @param coordinates the array to rearrange
530	* @param indexOfFirstCoordinate the index of the coordinate to make first
531	* @param ensureRing flag indicating if returned array should form a ring.
532	*/
533	public static void scroll(Coordinate[] coordinates, int indexOfFirstCoordinate, boolean ensureRing) {
534	int i = indexOfFirstCoordinate;
535	if (i <= 0) return;
536
537	Coordinate[] newCoordinates = new Coordinate[coordinates.length];
538	if (!ensureRing) {
539	System.arraycopy(coordinates, i, newCoordinates, 0, coordinates.length - i);
540	System.arraycopy(coordinates, 0, newCoordinates, coordinates.length - i, i);
541	} else {
542	int last = coordinates.length - 1;
543
544	// fill in values
545	int j;
546	for (j = 0; j < last; j++)
547	newCoordinates[j] = coordinates[(i + j) % last];
548
549	// Fix the ring (first == last)
550	newCoordinates[j] = newCoordinates[0].copy();
551	}
552	System.arraycopy(newCoordinates, 0, coordinates, 0, coordinates.length);
553	}
554
555	/**
556	* Returns the index of <code>coordinate</code> in <code>coordinates</code>.
557	* The first position is 0; the second, 1; etc.
558	*
559	* @param coordinate the <code>Coordinate</code> to search for
560	* @param coordinates the array to search
561	* @return the position of <code>coordinate</code>, or -1 if it is
562	* not found
563	*/
564	public static int indexOf(Coordinate coordinate, Coordinate[] coordinates) {
565	for (int i = 0; i < coordinates.length; i++) {
566	if (coordinate.equals(coordinates[i])) {
567	return i;
568	}
569	}
570	return -1;
571	}
572
573	/**
574	* Extracts a subsequence of the input {@link Coordinate} array
575	* from indices <code>start</code> to
576	* <code>end</code> (inclusive).
577	* The input indices are clamped to the array size;
578	* If the end index is less than the start index,
579	* the extracted array will be empty.
580	*
581	* @param pts the input array
582	* @param start the index of the start of the subsequence to extract
583	* @param end the index of the end of the subsequence to extract
584	* @return a subsequence of the input array
585	*/
586	public static Coordinate[] extract(Coordinate[] pts, int start, int end) {
587	start = MathUtil.clamp(start, 0, pts.length);
588	end = MathUtil.clamp(end, -1, pts.length);
589
590	int npts = end - start + 1;
591	if (end < 0) npts = 0;
592	if (start >= pts.length) npts = 0;
593	if (end < start) npts = 0;
594
595	Coordinate[] extractPts = new Coordinate[npts];
596	if (npts == 0) return extractPts;
597
598	int iPts = 0;
599	for (int i = start; i <= end; i++) {
600	extractPts[iPts++] = pts[i];
601	}
602	return extractPts;
603	}
604
605	/**
606	* Computes the envelope of the coordinates.
607	*
608	* @param coordinates the coordinates to scan
609	* @return the envelope of the coordinates
610	*/
611	public static Envelope envelope(Coordinate[] coordinates) {
612	Envelope env = new Envelope();
613	for (int i = 0; i < coordinates.length; i++) {
614	env.expandToInclude(coordinates[i]);
615	}
616	return env;
617	}
618
619	/**
620	* Extracts the coordinates which intersect an {@link Envelope}.
621	*
622	* @param coordinates the coordinates to scan
623	* @param env the envelope to intersect with
624	* @return an array of the coordinates which intersect the envelope
625	*/
626	public static Coordinate[] intersection(Coordinate[] coordinates, Envelope env) {
627	CoordinateList coordList = new CoordinateList();
628	for (int i = 0; i < coordinates.length; i++) {
629	if (env.intersects(coordinates[i]))
630	coordList.add(coordinates[i], true);
631	}
632	return coordList.toCoordinateArray();
633	}
634	}
635