Doc Classic

Class Orientation

  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.algorithm;
 13  
 14 import org.locationtech.jts.geom.Coordinate;
 15 import org.locationtech.jts.geom.CoordinateSequence;
 16  
 17 /**
 18  * Functions to compute the orientation of basic geometric structures
 19  * including point triplets (triangles) and rings.
 20  * Orientation is a fundamental property of planar geometries 
 21  * (and more generally geometry on two-dimensional manifolds).
 22  * <p>
 23  * Orientation is notoriously subject to numerical precision errors
 24  * in the case of collinear or nearly collinear points.  
 25  * JTS uses extended-precision arithmetic to increase
 26  * the robustness of the computation.
 27  * 
 28  * @author Martin Davis
 29  *
 30  */
 31 public class Orientation {
 32   /**
 33    * A value that indicates an orientation of clockwise, or a right turn.
 34    */
 35   public static final int CLOCKWISE = -1;
 36   /**
 37    * A value that indicates an orientation of clockwise, or a right turn.
 38    */
 39   public static final int RIGHT = CLOCKWISE;
 40   /**
 41    * A value that indicates an orientation of counterclockwise, or a left turn.
 42    */
 43   public static final int COUNTERCLOCKWISE = 1;
 44   /**
 45    * A value that indicates an orientation of counterclockwise, or a left turn.
 46    */
 47   public static final int LEFT = COUNTERCLOCKWISE;
 48   /**
 49    * A value that indicates an orientation of collinear, or no turn (straight).
 50    */
 51   public static final int COLLINEAR = 0;
 52   /**
 53    * A value that indicates an orientation of collinear, or no turn (straight).
 54    */
 55   public static final int STRAIGHT = COLLINEAR;
 56  
 57   /**
 58    * Returns the orientation index of the direction of the point <code>q</code> relative to
 59    * a directed infinite line specified by <code>p1-p2</code>.
 60    * The index indicates whether the point lies to the {@link #LEFT} or {@link #RIGHT}
 61    * of the line, or lies on it {@link #COLLINEAR}.
 62    * The index also indicates the orientation of the triangle formed by the three points
 63    * ( {@link #COUNTERCLOCKWISE}, {@link #CLOCKWISE}, or {@link #STRAIGHT} )
 64    * 
 65    * @param p1 the origin point of the line vector
 66    * @param p2 the final point of the line vector
 67    * @param q the point to compute the direction to
 68    * 
 69    * @return -1 ( {@link #CLOCKWISE} or {@link #RIGHT} ) if q is clockwise (right) from p1-p2;
 70    *         1 ( {@link #COUNTERCLOCKWISE} or {@link #LEFT} ) if q is counter-clockwise (left) from p1-p2;
 71    *         0 ( {@link #COLLINEAR} or {@link #STRAIGHT} ) if q is collinear with p1-p2
 72    */
 73   public static int index(Coordinate p1, Coordinate p2, Coordinate q)
 74   {
 75     /*
 76      * MD - 9 Aug 2010 It seems that the basic algorithm is slightly orientation
 77      * dependent, when computing the orientation of a point very close to a
 78      * line. This is possibly due to the arithmetic in the translation to the
 79      * origin.
 80      * 
 81      * For instance, the following situation produces identical results in spite
 82      * of the inverse orientation of the line segment:
 83      * 
 84      * Coordinate p0 = new Coordinate(219.3649559090992, 140.84159161824724);
 85      * Coordinate p1 = new Coordinate(168.9018919682399, -5.713787599646864);
 86      * 
 87      * Coordinate p = new Coordinate(186.80814046338352, 46.28973405831556); int
 88      * orient = orientationIndex(p0, p1, p); int orientInv =
 89      * orientationIndex(p1, p0, p);
 90      * 
 91      * A way to force consistent results is to normalize the orientation of the
 92      * vector using the following code. However, this may make the results of
 93      * orientationIndex inconsistent through the triangle of points, so it's not
 94      * clear this is an appropriate patch.
 95      * 
 96      */
 97     return CGAlgorithmsDD.orientationIndex(p1, p2, q);
 98  
 99     // testing only
100     //return ShewchuksDeterminant.orientationIndex(p1, p2, q);
101     // previous implementation - not quite fully robust
102     //return RobustDeterminant.orientationIndex(p1, p2, q);
103   }
104  
105   /**
106    * Computes whether a ring defined by an array of {@link Coordinate}s is
107    * oriented counter-clockwise.
108    * <ul>
109    * <li>The list of points is assumed to have the first and last points equal.
110    * <li>This will handle coordinate lists which contain repeated points.
111    * </ul>
112    * This algorithm is <b>only</b> guaranteed to work with valid rings. If the
113    * ring is invalid (e.g. self-crosses or touches), the computed result may not
114    * be correct.
115    * 
116    * @param ring
117    *          an array of Coordinates forming a ring
118    * @return true if the ring is oriented counter-clockwise.
119    * @throws IllegalArgumentException
120    *           if there are too few points to determine orientation (< 4)
121    */
122   public static boolean isCCW(Coordinate[] ring)
123   {
124     // # of points without closing endpoint
125     int nPts = ring.length - 1;
126     // sanity check
127     if (nPts < 3)
128       throw new IllegalArgumentException(
129           "Ring has fewer than 4 points, so orientation cannot be determined");
130   
131     // find highest point
132     Coordinate hiPt = ring[0];
133     int hiIndex = 0;
134     for (int i = 1; i <= nPts; i++) {
135       Coordinate p = ring[i];
136       if (p.y > hiPt.y) {
137         hiPt = p;
138         hiIndex = i;
139       }
140     }
141   
142     // find distinct point before highest point
143     int iPrev = hiIndex;
144     do {
145       iPrev = iPrev - 1;
146       if (iPrev < 0)
147         iPrev = nPts;
148     } while (ring[iPrev].equals2D(hiPt) && iPrev != hiIndex);
149   
150     // find distinct point after highest point
151     int iNext = hiIndex;
152     do {
153       iNext = (iNext + 1) % nPts;
154     } while (ring[iNext].equals2D(hiPt) && iNext != hiIndex);
155   
156     Coordinate prev = ring[iPrev];
157     Coordinate next = ring[iNext];
158   
159     /*
160      * This check catches cases where the ring contains an A-B-A configuration
161      * of points. This can happen if the ring does not contain 3 distinct points
162      * (including the case where the input array has fewer than 4 elements), or
163      * it contains coincident line segments.
164      */
165     if (prev.equals2D(hiPt) || next.equals2D(hiPt) || prev.equals2D(next))
166       return false;
167   
168     int disc = Orientation.index(prev, hiPt, next);
169   
170     /*
171      * If disc is exactly 0, lines are collinear. There are two possible cases:
172      * (1) the lines lie along the x axis in opposite directions (2) the lines
173      * lie on top of one another
174      * 
175      * (1) is handled by checking if next is left of prev ==> CCW (2) will never
176      * happen if the ring is valid, so don't check for it (Might want to assert
177      * this)
178      */
179     boolean isCCW;
180     if (disc == 0) {
181       // poly is CCW if prev x is right of next x
182       isCCW = (prev.x > next.x);
183     }
184     else {
185       // if area is positive, points are ordered CCW
186       isCCW = (disc > 0);
187     }
188     return isCCW;
189   }
190  
191   /**
192    * Computes whether a ring defined by an {@link CoordinateSequence} is
193    * oriented counter-clockwise.
194    * <ul>
195    * <li>The list of points is assumed to have the first and last points equal.
196    * <li>This will handle coordinate lists which contain repeated points.
197    * </ul>
198    * This algorithm is <b>only</b> guaranteed to work with valid rings. If the
199    * ring is invalid (e.g. self-crosses or touches), the computed result may not
200    * be correct.
201    *
202    * @param ring
203    *          a CoordinateSequence forming a ring
204    * @return true if the ring is oriented counter-clockwise.
205    * @throws IllegalArgumentException
206    *           if there are too few points to determine orientation (< 4)
207    */
208   public static boolean isCCW(CoordinateSequence ring)
209   {
210     // # of points without closing endpoint
211     int nPts = ring.size() - 1;
212     // sanity check
213     if (nPts < 3)
214       throw new IllegalArgumentException(
215               "Ring has fewer than 4 points, so orientation cannot be determined");
216  
217     // find highest point
218     Coordinate hiPt = ring.getCoordinate(0);
219     int hiIndex = 0;
220     for (int i = 1; i <= nPts; i++) {
221       Coordinate p = ring.getCoordinate(i);
222       if (p.y > hiPt.y) {
223         hiPt = p;
224         hiIndex = i;
225       }
226     }
227  
228     // find distinct point before highest point
229     Coordinate prev;
230     int iPrev = hiIndex;
231     do {
232       iPrev = iPrev - 1;
233       if (iPrev < 0)
234         iPrev = nPts;
235       prev = ring.getCoordinate(iPrev);
236     } while (prev.equals2D(hiPt) && iPrev != hiIndex);
237  
238     // find distinct point after highest point
239     Coordinate next;
240     int iNext = hiIndex;
241     do {
242       iNext = (iNext + 1) % nPts;
243       next = ring.getCoordinate(iNext);
244     } while (next.equals2D(hiPt) && iNext != hiIndex);
245  
246     /*
247      * This check catches cases where the ring contains an A-B-A configuration
248      * of points. This can happen if the ring does not contain 3 distinct points
249      * (including the case where the input array has fewer than 4 elements), or
250      * it contains coincident line segments.
251      */
252     if (prev.equals2D(hiPt) || next.equals2D(hiPt) || prev.equals2D(next))
253       return false;
254  
255     int disc = Orientation.index(prev, hiPt, next);
256  
257     /*
258      * If disc is exactly 0, lines are collinear. There are two possible cases:
259      * (1) the lines lie along the x axis in opposite directions (2) the lines
260      * lie on top of one another
261      *
262      * (1) is handled by checking if next is left of prev ==> CCW (2) will never
263      * happen if the ring is valid, so don't check for it (Might want to assert
264      * this)
265      */
266     boolean isCCW;
267     if (disc == 0) {
268       // poly is CCW if prev x is right of next x
269       isCCW = (prev.x > next.x);
270     }
271     else {
272       // if area is positive, points are ordered CCW
273       isCCW = (disc > 0);
274     }
275     return isCCW;
276   }
277  
278 }
279