Doc Classic

Class CoordinateSequences

  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.geom;
 13  
 14 import org.locationtech.jts.io.OrdinateFormat;
 15 import org.locationtech.jts.util.NumberUtil;
 16  
 17  
 18 /**
 19  * Utility functions for manipulating {@link CoordinateSequence}s
 20  *
 21  * @version 1.7
 22  */
 23 public class CoordinateSequences {
 24  
 25   /**
 26    * Reverses the coordinates in a sequence in-place.
 27    * 
 28    * @param seq the coordinate sequence to reverse
 29    */
 30   public static void reverse(CoordinateSequence seq)
 31   {
 32     int last = seq.size() - 1;
 33     int mid = last / 2;
 34     for (int i = 0; i <= mid; i++) {
 35       swap(seq, i, last - i);
 36     }
 37   }
 38  
 39   /**
 40    * Swaps two coordinates in a sequence.
 41    *
 42    * @param seq the sequence to modify
 43    * @param i the index of a coordinate to swap
 44    * @param j the index of a coordinate to swap
 45    */
 46   public static void swap(CoordinateSequence seq, int i, int j)
 47   {
 48     if (i == j) return;
 49     for (int dim = 0; dim < seq.getDimension(); dim++) {
 50       double tmp = seq.getOrdinate(i, dim);
 51       seq.setOrdinate(i, dim, seq.getOrdinate(j, dim));
 52       seq.setOrdinate(j, dim, tmp);
 53     }
 54   }
 55   
 56   /**
 57    * Copies a section of a {@link CoordinateSequence} to another {@link CoordinateSequence}.
 58    * The sequences may have different dimensions;
 59    * in this case only the common dimensions are copied.
 60    *
 61    * @param src the sequence to copy from
 62    * @param srcPos the position in the source sequence to start copying at
 63    * @param dest the sequence to copy to
 64    * @param destPos the position in the destination sequence to copy to
 65    * @param length the number of coordinates to copy
 66    */
 67   public static void copy(CoordinateSequence src, int srcPos, CoordinateSequence dest, int destPos, int length)
 68   {
 69       for (int i = 0; i < length; i++) {
 70           copyCoord(src, srcPos + i, dest, destPos + i);
 71       }
 72   }
 73  
 74   /**
 75    * Copies a coordinate of a {@link CoordinateSequence} to another {@link CoordinateSequence}.
 76    * The sequences may have different dimensions;
 77    * in this case only the common dimensions are copied.
 78    * 
 79    * @param src the sequence to copy from
 80    * @param srcPos the source coordinate to copy
 81    * @param dest the sequence to copy to
 82    * @param destPos the destination coordinate to copy to
 83    */
 84   public static void copyCoord(CoordinateSequence src, int srcPos, CoordinateSequence dest, int destPos)
 85   {
 86     int minDim = Math.min(src.getDimension(), dest.getDimension());
 87         for (int dim = 0; dim < minDim; dim++) {
 88             dest.setOrdinate(destPos, dim, src.getOrdinate(srcPos, dim));
 89         }
 90   }
 91   
 92   /**
 93    * Tests whether a {@link CoordinateSequence} forms a valid {@link LinearRing},
 94    * by checking the sequence length and closure
 95    * (whether the first and last points are identical in 2D). 
 96    * Self-intersection is not checked.
 97    * 
 98    * @param seq the sequence to test
 99    * @return true if the sequence is a ring
100    * @see LinearRing
101    */
102   public static boolean isRing(CoordinateSequence seq) 
103   {
104       int n = seq.size();
105       if (n == 0) return true;
106       // too few points
107       if (n <= 3) 
108           return false;
109       // test if closed
110       return seq.getOrdinate(0, CoordinateSequence.X) == seq.getOrdinate(n-1, CoordinateSequence.X)
111           && seq.getOrdinate(0, CoordinateSequence.Y) == seq.getOrdinate(n-1, CoordinateSequence.Y);
112   }
113   
114   /**
115    * Ensures that a CoordinateSequence forms a valid ring, 
116    * returning a new closed sequence of the correct length if required.
117    * If the input sequence is already a valid ring, it is returned 
118    * without modification.
119    * If the input sequence is too short or is not closed, 
120    * it is extended with one or more copies of the start point.
121    * 
122    * @param fact the CoordinateSequenceFactory to use to create the new sequence
123    * @param seq the sequence to test
124    * @return the original sequence, if it was a valid ring, or a new sequence which is valid.
125    */
126   public static CoordinateSequence ensureValidRing(CoordinateSequenceFactory fact, CoordinateSequence seq)
127   {
128       int n = seq.size();
129       // empty sequence is valid
130       if (n == 0) return seq; 
131       // too short - make a new one
132       if (n <= 3) 
133           return createClosedRing(fact, seq, 4);
134       
135       boolean isClosed = seq.getOrdinate(0, CoordinateSequence.X) == seq.getOrdinate(n-1, CoordinateSequence.X)
136         && seq.getOrdinate(0, CoordinateSequence.Y) == seq.getOrdinate(n-1, CoordinateSequence.Y);
137       if (isClosed) return seq;
138       // make a new closed ring
139       return createClosedRing(fact, seq, n+1);
140   }
141   
142   private static CoordinateSequence createClosedRing(CoordinateSequenceFactory fact, CoordinateSequence seq, int size)
143   {
144     CoordinateSequence newseq = fact.create(size, seq.getDimension());
145     int n = seq.size();
146     copy(seq, 0, newseq, 0, n);
147     // fill remaining coordinates with start point
148     for (int i = n; i < size; i++)
149       copy(seq, 0, newseq, i, 1);
150     return newseq;
151   }
152   
153   public static CoordinateSequence extend(CoordinateSequenceFactory fact, CoordinateSequence seq, int size)
154   {
155     CoordinateSequence newseq = fact.create(size, seq.getDimension());
156     int n = seq.size();
157     copy(seq, 0, newseq, 0, n);
158     // fill remaining coordinates with end point, if it exists
159     if (n > 0) {
160       for (int i = n; i < size; i++)
161         copy(seq, n-1, newseq, i, 1);
162     }
163     return newseq;
164   }
165  
166   /**
167    * Tests whether two {@link CoordinateSequence}s are equal.
168    * To be equal, the sequences must be the same length.
169    * They do not need to be of the same dimension, 
170    * but the ordinate values for the smallest dimension of the two
171    * must be equal.
172    * Two <code>NaN</code> ordinates values are considered to be equal. 
173    * 
174    * @param cs1 a CoordinateSequence
175    * @param cs2 a CoordinateSequence
176    * @return true if the sequences are equal in the common dimensions
177    */
178   public static boolean isEqual(CoordinateSequence cs1, CoordinateSequence cs2) {
179     int cs1Size = cs1.size();
180     int cs2Size = cs2.size();
181     if (cs1Size != cs2Size) return false;
182     int dim = Math.min(cs1.getDimension(), cs2.getDimension());
183     for (int i = 0; i < cs1Size; i++) {
184       for (int d = 0; d < dim; d++) {
185         double v1 = cs1.getOrdinate(i, d);
186         double v2 = cs2.getOrdinate(i, d);
187         if (cs1.getOrdinate(i, d) == cs2.getOrdinate(i, d))
188           continue;
189         // special check for NaNs
190         if (Double.isNaN(v1) && Double.isNaN(v2))
191           continue;
192         return false;
193       }
194     }
195     return true;
196   }
197   
198   /**
199    * Creates a string representation of a {@link CoordinateSequence}.
200    * The format is:
201    * <pre>
202    *   ( ord0,ord1.. ord0,ord1,...  ... )
203    * </pre>
204    * 
205    * @param cs the sequence to output
206    * @return the string representation of the sequence
207    */
208   public static String toString(CoordinateSequence cs)
209   {
210     int size = cs.size();
211     if (size == 0) 
212       return "()";
213     int dim = cs.getDimension();
214     StringBuilder builder = new StringBuilder();
215     builder.append('(');
216     for (int i = 0; i < size; i++) {
217       if (i > 0) builder.append(" ");
218       for (int d = 0; d < dim; d++) {
219         if (d > 0) builder.append(",");
220         builder.append( OrdinateFormat.DEFAULT.format(cs.getOrdinate(i, d)) );
221       }
222     }
223     builder.append(')');
224     return builder.toString();
225   }
226  
227   /**
228    *  Returns the minimum coordinate, using the usual lexicographic comparison.
229    *
230    *@param  seq  the coordinate sequence to search
231    *@return  the minimum coordinate in the sequence, found using <code>compareTo</code>
232    *@see Coordinate#compareTo(Object)
233    */
234   public static Coordinate minCoordinate(CoordinateSequence seq)
235   {
236     Coordinate minCoord = null;
237     for (int i = 0; i < seq.size(); i++) {
238       Coordinate testCoord = seq.getCoordinate(i);
239       if (minCoord == null || minCoord.compareTo(testCoord) > 0) {
240         minCoord = testCoord;
241       }
242     }
243     return minCoord;
244   }
245   /**
246    *  Returns the index of the minimum coordinate of the whole
247    *  coordinate sequence, using the usual lexicographic comparison.
248    *
249    *@param  seq  the coordinate sequence to search
250    *@return  the index of the minimum coordinate in the sequence, found using <code>compareTo</code>
251    *@see Coordinate#compareTo(Object)
252    */
253   public static int minCoordinateIndex(CoordinateSequence seq) {
254     return minCoordinateIndex(seq, 0, seq.size() - 1);
255   }
256  
257   /**
258    *  Returns the index of the minimum coordinate of a part of
259    *  the coordinate sequence (defined by {@code from} and {@code to},
260    *  using the usual lexicographic comparison.
261    *
262    *@param  seq   the coordinate sequence to search
263    *@param  from  the lower search index
264    *@param  to    the upper search index
265    *@return  the index of the minimum coordinate in the sequence, found using <code>compareTo</code>
266    *@see Coordinate#compareTo(Object)
267    */
268   public static int minCoordinateIndex(CoordinateSequence seq, int from, int to)
269   {
270     int minCoordIndex = -1;
271     Coordinate minCoord = null;
272     for (int i = from; i <= to; i++) {
273       Coordinate testCoord = seq.getCoordinate(i);
274       if (minCoord == null || minCoord.compareTo(testCoord) > 0) {
275           minCoord = testCoord;
276           minCoordIndex = i;
277       }
278     }
279     return minCoordIndex;
280   }
281  
282   /**
283    *  Shifts the positions of the coordinates until <code>firstCoordinate</code>
284    *  is first.
285    *
286    *@param  seq      the coordinate sequence to rearrange
287    *@param  firstCoordinate  the coordinate to make first
288    */
289   public static void scroll(CoordinateSequence seq, Coordinate firstCoordinate) {
290     int i = indexOf(firstCoordinate, seq);
291     if (i <= 0) return;
292     scroll(seq, i);
293   }
294  
295   /**
296    *  Shifts the positions of the coordinates until the coordinate at  <code>firstCoordinateIndex</code>
297    *  is first.
298    *
299    *@param  seq      the coordinate sequence to rearrange
300    *@param  indexOfFirstCoordinate  the index of the coordinate to make first
301    */
302   public static void scroll(CoordinateSequence seq, int indexOfFirstCoordinate)
303   {
304     scroll(seq, indexOfFirstCoordinate, CoordinateSequences.isRing(seq));
305   }
306  
307   /**
308    *  Shifts the positions of the coordinates until the coordinate at  <code>firstCoordinateIndex</code>
309    *  is first.
310    *
311    *@param  seq      the coordinate sequence to rearrange
312    *@param  indexOfFirstCoordinate
313    *                 the index of the coordinate to make first
314    *@param  ensureRing
315    *                 makes sure that {@code} will be a closed ring upon exit
316    */
317     public static void scroll(CoordinateSequence seq, int indexOfFirstCoordinate, boolean ensureRing) {
318     int i = indexOfFirstCoordinate;
319     if (i <= 0) return;
320  
321     // make a copy of the sequence
322     CoordinateSequence copy = seq.copy();
323  
324     // test if ring, determine last index
325     int last = ensureRing ? seq.size() - 1: seq.size();
326  
327     // fill in values
328     for (int j = 0; j < last; j++)
329     {
330       for (int k = 0; k < seq.getDimension(); k++)
331         seq.setOrdinate(j, k, copy.getOrdinate((indexOfFirstCoordinate+j)%last, k));
332     }
333  
334     // Fix the ring (first == last)
335     if (ensureRing) {
336       for (int k = 0; k < seq.getDimension(); k++)
337         seq.setOrdinate(last, k, seq.getOrdinate(0, k));
338     }
339   }
340  
341   /**
342    *  Returns the index of <code>coordinate</code> in a {@link CoordinateSequence}
343    *  The first position is 0; the second, 1; etc.
344    *
345    *@param  coordinate   the <code>Coordinate</code> to search for
346    *@param  seq  the coordinate sequence to search
347    *@return              the position of <code>coordinate</code>, or -1 if it is
348    *      not found
349    */
350   public static int indexOf(Coordinate coordinate, CoordinateSequence seq) {
351     for (int i = 0; i < seq.size(); i++) {
352       if (coordinate.x == seq.getOrdinate(i, CoordinateSequence.X) &&
353           coordinate.y == seq.getOrdinate(i, CoordinateSequence.Y)) {
354         return i;
355       }
356     }
357     return -1;
358   }}
359