Orientation.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.algorithm;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.CoordinateSequence;
import org.locationtech.jts.geom.impl.CoordinateArraySequence;
/**
* Functions to compute the orientation of basic geometric structures
* including point triplets (triangles) and rings.
* Orientation is a fundamental property of planar geometries
* (and more generally geometry on two-dimensional manifolds).
* <p>
* Determining triangle orientation
* is notoriously subject to numerical precision errors
* in the case of collinear or nearly collinear points.
* JTS uses extended-precision arithmetic to increase
* the robustness of the computation.
*
* @author Martin Davis
*
*/
public class Orientation {
/**
* A value that indicates an orientation of clockwise, or a right turn.
*/
public static final int CLOCKWISE = -1;
/**
* A value that indicates an orientation of clockwise, or a right turn.
*/
public static final int RIGHT = CLOCKWISE;
/**
* A value that indicates an orientation of counterclockwise, or a left turn.
*/
public static final int COUNTERCLOCKWISE = 1;
/**
* A value that indicates an orientation of counterclockwise, or a left turn.
*/
public static final int LEFT = COUNTERCLOCKWISE;
/**
* A value that indicates an orientation of collinear, or no turn (straight).
*/
public static final int COLLINEAR = 0;
/**
* A value that indicates an orientation of collinear, or no turn (straight).
*/
public static final int STRAIGHT = COLLINEAR;
/**
* Returns the orientation index of the direction of the point <code>q</code> relative to
* a directed infinite line specified by <code>p1-p2</code>.
* The index indicates whether the point lies to the {@link #LEFT} or {@link #RIGHT}
* of the line, or lies on it {@link #COLLINEAR}.
* The index also indicates the orientation of the triangle formed by the three points
* ( {@link #COUNTERCLOCKWISE}, {@link #CLOCKWISE}, or {@link #STRAIGHT} )
*
* @param p1 the origin point of the line vector
* @param p2 the final point of the line vector
* @param q the point to compute the direction to
*
* @return -1 ( {@link #CLOCKWISE} or {@link #RIGHT} ) if q is clockwise (right) from p1-p2;
* 1 ( {@link #COUNTERCLOCKWISE} or {@link #LEFT} ) if q is counter-clockwise (left) from p1-p2;
* 0 ( {@link #COLLINEAR} or {@link #STRAIGHT} ) if q is collinear with p1-p2
*/
public static int index(Coordinate p1, Coordinate p2, Coordinate q)
{
/*
* MD - 9 Aug 2010 It seems that the basic algorithm is slightly orientation
* dependent, when computing the orientation of a point very close to a
* line. This is possibly due to the arithmetic in the translation to the
* origin.
*
* For instance, the following situation produces identical results in spite
* of the inverse orientation of the line segment:
*
* Coordinate p0 = new Coordinate(219.3649559090992, 140.84159161824724);
* Coordinate p1 = new Coordinate(168.9018919682399, -5.713787599646864);
*
* Coordinate p = new Coordinate(186.80814046338352, 46.28973405831556); int
* orient = orientationIndex(p0, p1, p); int orientInv =
* orientationIndex(p1, p0, p);
*
* A way to force consistent results is to normalize the orientation of the
* vector using the following code. However, this may make the results of
* orientationIndex inconsistent through the triangle of points, so it's not
* clear this is an appropriate patch.
*
*/
return CGAlgorithmsDD.orientationIndex(p1, p2, q);
// testing only
//return ShewchuksDeterminant.orientationIndex(p1, p2, q);
// previous implementation - not quite fully robust
//return RobustDeterminant.orientationIndex(p1, p2, q);
}
/**
* Tests if a ring defined by an array of {@link Coordinate}s is
* oriented counter-clockwise.
* <ul>
* <li>The list of points is assumed to have the first and last points equal.
* <li>This handles coordinate lists which contain repeated points.
* <li>This handles rings which contain collapsed segments
* (in particular, along the top of the ring).
* </ul>
* This algorithm is guaranteed to work with valid rings.
* It also works with "mildly invalid" rings
* which contain collapsed (coincident) flat segments along the top of the ring.
* If the ring is "more" invalid (e.g. self-crosses or touches),
* the computed result may not be correct.
*
* @param ring an array of Coordinates forming a ring (with first and last point identical)
* @return true if the ring is oriented counter-clockwise.
* @throws IllegalArgumentException if there are too few points to determine orientation (< 4)
*/
public static boolean isCCW(Coordinate[] ring)
{
// wrap with an XY CoordinateSequence
return isCCW(new CoordinateArraySequence(ring, 2, 0));
}
/**
* Tests if a ring defined by a {@link CoordinateSequence} is
* oriented counter-clockwise.
* <ul>
* <li>The list of points is assumed to have the first and last points equal.
* <li>This handles coordinate lists which contain repeated points.
* <li>This handles rings which contain collapsed segments
* (in particular, along the top of the ring).
* </ul>
* This algorithm is guaranteed to work with valid rings.
* It also works with "mildly invalid" rings
* which contain collapsed (coincident) flat segments along the top of the ring.
* If the ring is "more" invalid (e.g. self-crosses or touches),
* the computed result may not be correct.
*
* @param ring a CoordinateSequence forming a ring (with first and last point identical)
* @return true if the ring is oriented counter-clockwise.
*/
public static boolean isCCW(CoordinateSequence ring)
{
// # of points without closing endpoint
int nPts = ring.size() - 1;
// return default value if ring is flat
if (nPts < 3) return false;
/**
* Find first highest point after a lower point, if one exists
* (e.g. a rising segment)
* If one does not exist, hiIndex will remain 0
* and the ring must be flat.
* Note this relies on the convention that
* rings have the same start and end point.
*/
Coordinate upHiPt = ring.getCoordinate(0);
double prevY = upHiPt.y;
Coordinate upLowPt = null;
int iUpHi = 0;
for (int i = 1; i <= nPts; i++) {
double py = ring.getOrdinate(i, Coordinate.Y);
/**
* If segment is upwards and endpoint is higher, record it
*/
if (py > prevY && py >= upHiPt.y) {
upHiPt = ring.getCoordinate(i);
iUpHi = i;
upLowPt = ring.getCoordinate(i-1);
}
prevY = py;
}
/**
* Check if ring is flat and return default value if so
*/
if (iUpHi == 0) return false;
/**
* Find the next lower point after the high point
* (e.g. a falling segment).
* This must exist since ring is not flat.
*/
int iDownLow = iUpHi;
do {
iDownLow = (iDownLow + 1) % nPts;
} while (iDownLow != iUpHi && ring.getOrdinate(iDownLow, Coordinate.Y) == upHiPt.y );
Coordinate downLowPt = ring.getCoordinate(iDownLow);
int iDownHi = iDownLow > 0 ? iDownLow - 1 : nPts - 1;
Coordinate downHiPt = ring.getCoordinate(iDownHi);
/**
* Two cases can occur:
* 1) the hiPt and the downPrevPt are the same.
* This is the general position case of a "pointed cap".
* The ring orientation is determined by the orientation of the cap
* 2) The hiPt and the downPrevPt are different.
* In this case the top of the cap is flat.
* The ring orientation is given by the direction of the flat segment
*/
if (upHiPt.equals2D(downHiPt)) {
/**
* Check for the case where the cap has configuration A-B-A.
* This can happen if the ring does not contain 3 distinct points
* (including the case where the input array has fewer than 4 elements), or
* it contains coincident line segments.
*/
if (upLowPt.equals2D(upHiPt) || downLowPt.equals2D(upHiPt) || upLowPt.equals2D(downLowPt))
return false;
/**
* It can happen that the top segments are coincident.
* This is an invalid ring, which cannot be computed correctly.
* In this case the orientation is 0, and the result is false.
*/
int index = index(upLowPt, upHiPt, downLowPt);
return index == COUNTERCLOCKWISE;
}
else {
/**
* Flat cap - direction of flat top determines orientation
*/
double delX = downHiPt.x - upHiPt.x;
return delX < 0;
}
}
/**
* Tests if a ring defined by an array of {@link Coordinate}s is
* oriented counter-clockwise, using the signed area of the ring.
* <ul>
* <li>The list of points is assumed to have the first and last points equal.
* <li>This handles coordinate lists which contain repeated points.
* <li>This handles rings which contain collapsed segments
* (in particular, along the top of the ring).
* <li>This handles rings which are invalid due to self-intersection
* </ul>
* This algorithm is guaranteed to work with valid rings.
* For invalid rings (containing self-intersections),
* the algorithm determines the orientation of
* the largest enclosed area (including overlaps).
* This provides a more useful result in some situations, such as buffering.
* <p>
* However, this approach may be less accurate in the case of
* rings with almost zero area.
* (Note that the orientation of rings with zero area is essentially
* undefined, and hence non-deterministic.)
*
* @param ring an array of Coordinates forming a ring (with first and last point identical)
* @return true if the ring is oriented counter-clockwise.
*/
public static boolean isCCWArea(Coordinate[] ring) {
return Area.ofRingSigned(ring) < 0;
}
}