CoordinateSequences.java

/*
 * Copyright (c) 2016 Vivid Solutions.
 *
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * and Eclipse Distribution License v. 1.0 which accompanies this distribution.
 * The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
 * and the Eclipse Distribution License is available at
 *
 * http://www.eclipse.org/org/documents/edl-v10.php.
 */
package org.locationtech.jts.geom;

import org.locationtech.jts.io.OrdinateFormat;


/**
 * Utility functions for manipulating {@link CoordinateSequence}s
 *
 * @version 1.7
 */
public class CoordinateSequences {

  /**
   * Reverses the coordinates in a sequence in-place.
   * 
   * @param seq the coordinate sequence to reverse
   */
  public static void reverse(CoordinateSequence seq)
  {
    if (seq.size() <= 1) return;
    
    int last = seq.size() - 1;
    int mid = last / 2;
    for (int i = 0; i <= mid; i++) {
      swap(seq, i, last - i);
    }
  }

  /**
   * Swaps two coordinates in a sequence.
   *
   * @param seq the sequence to modify
   * @param i the index of a coordinate to swap
   * @param j the index of a coordinate to swap
   */
  public static void swap(CoordinateSequence seq, int i, int j)
  {
    if (i == j) return;
    for (int dim = 0; dim < seq.getDimension(); dim++) {
      double tmp = seq.getOrdinate(i, dim);
      seq.setOrdinate(i, dim, seq.getOrdinate(j, dim));
      seq.setOrdinate(j, dim, tmp);
    }
  }
  
  /**
   * Copies a section of a {@link CoordinateSequence} to another {@link CoordinateSequence}.
   * The sequences may have different dimensions;
   * in this case only the common dimensions are copied.
   *
   * @param src the sequence to copy from
   * @param srcPos the position in the source sequence to start copying at
   * @param dest the sequence to copy to
   * @param destPos the position in the destination sequence to copy to
   * @param length the number of coordinates to copy
   */
  public static void copy(CoordinateSequence src, int srcPos, CoordinateSequence dest, int destPos, int length)
  {
  	for (int i = 0; i < length; i++) {
  		copyCoord(src, srcPos + i, dest, destPos + i);
  	}
  }

  /**
   * Copies a coordinate of a {@link CoordinateSequence} to another {@link CoordinateSequence}.
   * The sequences may have different dimensions;
   * in this case only the common dimensions are copied.
   * 
   * @param src the sequence to copy from
   * @param srcPos the source coordinate to copy
   * @param dest the sequence to copy to
   * @param destPos the destination coordinate to copy to
   */
  public static void copyCoord(CoordinateSequence src, int srcPos, CoordinateSequence dest, int destPos)
  {
    int minDim = Math.min(src.getDimension(), dest.getDimension());
		for (int dim = 0; dim < minDim; dim++) {
			dest.setOrdinate(destPos, dim, src.getOrdinate(srcPos, dim));
		}
  }
  
  /**
   * Tests whether a {@link CoordinateSequence} forms a valid {@link LinearRing},
   * by checking the sequence length and closure
   * (whether the first and last points are identical in 2D). 
   * Self-intersection is not checked.
   * 
   * @param seq the sequence to test
   * @return true if the sequence is a ring
   * @see LinearRing
   */
  public static boolean isRing(CoordinateSequence seq) 
  {
  	int n = seq.size();
  	if (n == 0) return true;
  	// too few points
  	if (n <= 3) 
  		return false;
  	// test if closed
  	return seq.getOrdinate(0, CoordinateSequence.X) == seq.getOrdinate(n-1, CoordinateSequence.X)
  		&& seq.getOrdinate(0, CoordinateSequence.Y) == seq.getOrdinate(n-1, CoordinateSequence.Y);
  }
  
  /**
   * Ensures that a CoordinateSequence forms a valid ring, 
   * returning a new closed sequence of the correct length if required.
   * If the input sequence is already a valid ring, it is returned 
   * without modification.
   * If the input sequence is too short or is not closed, 
   * it is extended with one or more copies of the start point.
   * 
   * @param fact the CoordinateSequenceFactory to use to create the new sequence
   * @param seq the sequence to test
   * @return the original sequence, if it was a valid ring, or a new sequence which is valid.
   */
  public static CoordinateSequence ensureValidRing(CoordinateSequenceFactory fact, CoordinateSequence seq)
  {
  	int n = seq.size();
  	// empty sequence is valid
  	if (n == 0) return seq; 
  	// too short - make a new one
  	if (n <= 3) 
  		return createClosedRing(fact, seq, 4);
  	
  	boolean isClosed = seq.getOrdinate(0, CoordinateSequence.X) == seq.getOrdinate(n-1, CoordinateSequence.X)
		&& seq.getOrdinate(0, CoordinateSequence.Y) == seq.getOrdinate(n-1, CoordinateSequence.Y);
  	if (isClosed) return seq;
  	// make a new closed ring
  	return createClosedRing(fact, seq, n+1);
  }
  
  private static CoordinateSequence createClosedRing(CoordinateSequenceFactory fact, CoordinateSequence seq, int size)
  {
    CoordinateSequence newseq = fact.create(size, seq.getDimension());
    int n = seq.size();
    copy(seq, 0, newseq, 0, n);
    // fill remaining coordinates with start point
    for (int i = n; i < size; i++)
      copy(seq, 0, newseq, i, 1);
    return newseq;
  }
  
  public static CoordinateSequence extend(CoordinateSequenceFactory fact, CoordinateSequence seq, int size)
  {
    CoordinateSequence newseq = fact.create(size, seq.getDimension());
    int n = seq.size();
    copy(seq, 0, newseq, 0, n);
    // fill remaining coordinates with end point, if it exists
    if (n > 0) {
      for (int i = n; i < size; i++)
        copy(seq, n-1, newseq, i, 1);
    }
    return newseq;
  }

  /**
   * Tests whether two {@link CoordinateSequence}s are equal.
   * To be equal, the sequences must be the same length.
   * They do not need to be of the same dimension, 
   * but the ordinate values for the smallest dimension of the two
   * must be equal.
   * Two <code>NaN</code> ordinates values are considered to be equal. 
   * 
   * @param cs1 a CoordinateSequence
   * @param cs2 a CoordinateSequence
   * @return true if the sequences are equal in the common dimensions
   */
  public static boolean isEqual(CoordinateSequence cs1, CoordinateSequence cs2) {
    int cs1Size = cs1.size();
    int cs2Size = cs2.size();
    if (cs1Size != cs2Size) return false;
    int dim = Math.min(cs1.getDimension(), cs2.getDimension());
    for (int i = 0; i < cs1Size; i++) {
      for (int d = 0; d < dim; d++) {
        double v1 = cs1.getOrdinate(i, d);
        double v2 = cs2.getOrdinate(i, d);
        if (cs1.getOrdinate(i, d) == cs2.getOrdinate(i, d)) {
          continue;
        }
        else if (Double.isNaN(v1) && Double.isNaN(v2)) {
          // special check for NaNs
          continue;
        }
        else {
          return false;
        }
      }
    }
    return true;
  }
  
  /**
   * Creates a string representation of a {@link CoordinateSequence}.
   * The format is:
   * <pre>
   *   ( ord0,ord1.. ord0,ord1,...  ... )
   * </pre>
   * 
   * @param cs the sequence to output
   * @return the string representation of the sequence
   */
  public static String toString(CoordinateSequence cs)
  {
    int size = cs.size();
    if (size == 0) 
      return "()";
    int dim = cs.getDimension();
    StringBuilder builder = new StringBuilder();
    builder.append('(');
    for (int i = 0; i < size; i++) {
      if (i > 0) builder.append(" ");
      for (int d = 0; d < dim; d++) {
        if (d > 0) builder.append(",");
        builder.append( OrdinateFormat.DEFAULT.format(cs.getOrdinate(i, d)) );
      }
    }
    builder.append(')');
    return builder.toString();
  }

  /**
   *  Returns the minimum coordinate, using the usual lexicographic comparison.
   *
   *@param  seq  the coordinate sequence to search
   *@return  the minimum coordinate in the sequence, found using <code>compareTo</code>
   *@see Coordinate#compareTo(Object)
   */
  public static Coordinate minCoordinate(CoordinateSequence seq)
  {
    Coordinate minCoord = null;
    for (int i = 0; i < seq.size(); i++) {
      Coordinate testCoord = seq.getCoordinate(i);
      if (minCoord == null || minCoord.compareTo(testCoord) > 0) {
        minCoord = testCoord;
      }
    }
    return minCoord;
  }
  /**
   *  Returns the index of the minimum coordinate of the whole
   *  coordinate sequence, using the usual lexicographic comparison.
   *
   *@param  seq  the coordinate sequence to search
   *@return  the index of the minimum coordinate in the sequence, found using <code>compareTo</code>
   *@see Coordinate#compareTo(Object)
   */
  public static int minCoordinateIndex(CoordinateSequence seq) {
    return minCoordinateIndex(seq, 0, seq.size() - 1);
  }

  /**
   *  Returns the index of the minimum coordinate of a part of
   *  the coordinate sequence (defined by {@code from} and {@code to},
   *  using the usual lexicographic comparison.
   *
   *@param  seq   the coordinate sequence to search
   *@param  from  the lower search index
   *@param  to    the upper search index
   *@return  the index of the minimum coordinate in the sequence, found using <code>compareTo</code>
   *@see Coordinate#compareTo(Object)
   */
  public static int minCoordinateIndex(CoordinateSequence seq, int from, int to)
  {
    int minCoordIndex = -1;
    Coordinate minCoord = null;
    for (int i = from; i <= to; i++) {
      Coordinate testCoord = seq.getCoordinate(i);
      if (minCoord == null || minCoord.compareTo(testCoord) > 0) {
          minCoord = testCoord;
          minCoordIndex = i;
      }
    }
    return minCoordIndex;
  }

  /**
   *  Shifts the positions of the coordinates until <code>firstCoordinate</code>
   *  is first.
   *
   *@param  seq      the coordinate sequence to rearrange
   *@param  firstCoordinate  the coordinate to make first
   */
  public static void scroll(CoordinateSequence seq, Coordinate firstCoordinate) {
    int i = indexOf(firstCoordinate, seq);
    if (i <= 0) return;
    scroll(seq, i);
  }

  /**
   *  Shifts the positions of the coordinates until the coordinate at  <code>firstCoordinateIndex</code>
   *  is first.
   *
   *@param  seq      the coordinate sequence to rearrange
   *@param  indexOfFirstCoordinate  the index of the coordinate to make first
   */
  public static void scroll(CoordinateSequence seq, int indexOfFirstCoordinate)
  {
    scroll(seq, indexOfFirstCoordinate, CoordinateSequences.isRing(seq));
  }

  /**
   *  Shifts the positions of the coordinates until the coordinate at  <code>firstCoordinateIndex</code>
   *  is first.
   *
   *@param  seq      the coordinate sequence to rearrange
   *@param  indexOfFirstCoordinate
   *                 the index of the coordinate to make first
   *@param  ensureRing
   *                 makes sure that {@code} will be a closed ring upon exit
   */
    public static void scroll(CoordinateSequence seq, int indexOfFirstCoordinate, boolean ensureRing) {
    int i = indexOfFirstCoordinate;
    if (i <= 0) return;

    // make a copy of the sequence
    CoordinateSequence copy = seq.copy();

    // test if ring, determine last index
    int last = ensureRing ? seq.size() - 1: seq.size();

    // fill in values
    for (int j = 0; j < last; j++)
    {
      for (int k = 0; k < seq.getDimension(); k++)
        seq.setOrdinate(j, k, copy.getOrdinate((indexOfFirstCoordinate+j)%last, k));
    }

    // Fix the ring (first == last)
    if (ensureRing) {
      for (int k = 0; k < seq.getDimension(); k++)
        seq.setOrdinate(last, k, seq.getOrdinate(0, k));
    }
  }

  /**
   *  Returns the index of <code>coordinate</code> in a {@link CoordinateSequence}
   *  The first position is 0; the second, 1; etc.
   *
   *@param  coordinate   the <code>Coordinate</code> to search for
   *@param  seq  the coordinate sequence to search
   *@return              the position of <code>coordinate</code>, or -1 if it is
   *      not found
   */
  public static int indexOf(Coordinate coordinate, CoordinateSequence seq) {
    for (int i = 0; i < seq.size(); i++) {
      if (coordinate.x == seq.getOrdinate(i, CoordinateSequence.X) &&
          coordinate.y == seq.getOrdinate(i, CoordinateSequence.Y)) {
        return i;
      }
    }
    return -1;
  }}